Multiplicative order: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 45: | Line 45: | ||
The total cost is dominated by<tt> O(k(lg p)<sup>3</sup>)</tt> ,<tt> </tt>which is<tt> O((lg p)<sup>4</sup>/(lg lg p))</tt>. |
The total cost is dominated by<tt> O(k(lg p)<sup>3</sup>)</tt> ,<tt> </tt>which is<tt> O((lg p)<sup>4</sup>/(lg lg p))</tt>. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|D}} |
|||
<lang 11l>T PExp |
|||
BigInt prime |
|||
Int exp |
|||
F (prime, exp) |
|||
.prime = prime |
|||
.exp = exp |
|||
F isqrt(self) |
|||
V b = self |
|||
L |
|||
V a = b |
|||
b = (self I/ a + a) I/ 2 |
|||
I b >= a |
|||
R a |
|||
F factor(BigInt n) |
|||
[PExp] pf |
|||
V nn = n |
|||
V b = 0 |
|||
L ((nn % 2) == 0) |
|||
nn I/= 2 |
|||
b++ |
|||
I b > 0 |
|||
pf [+]= PExp(BigInt(2), b) |
|||
V s = isqrt(nn) |
|||
V d = BigInt(3) |
|||
L nn > 1 |
|||
I d > s |
|||
d = nn |
|||
V e = 0 |
|||
L |
|||
V (div, rem) = divmod(nn, d) |
|||
I bit_length(rem) > 0 |
|||
L.break |
|||
nn = div |
|||
e++ |
|||
I e > 0 |
|||
pf [+]= PExp(d, e) |
|||
s = isqrt(nn) |
|||
d += 2 |
|||
R pf |
|||
F moBachShallit58(BigInt a, BigInt n; pf) |
|||
V n1 = n - 1 |
|||
V mo = BigInt(1) |
|||
L(pe) pf |
|||
V y = n1 I/ pow(pe.prime, BigInt(pe.exp)) |
|||
V o = 0 |
|||
V x = pow(a, y, n) |
|||
L x > 1 |
|||
x = pow(x, pe.prime, n) |
|||
o++ |
|||
V o1 = pow(pe.prime, BigInt(o)) |
|||
o1 I/= gcd(mo, o1) |
|||
mo *= o1 |
|||
R mo |
|||
F moTest(a, n) |
|||
I bit_length(a) < 100 |
|||
print(‘ord(’a‘)’, end' ‘’) |
|||
E |
|||
print(‘ord([big])’, end' ‘’) |
|||
print(‘ mod ’n‘ = ’moBachShallit58(a, n, factor(n - 1))) |
|||
moTest(37, 3343) |
|||
moTest(pow(BigInt(10), 100) + 1, 7919) |
|||
moTest(pow(BigInt(10), 1000) + 1, 15485863) |
|||
moTest(pow(BigInt(10), 10000) - 1, BigInt(22801763489)) |
|||
moTest(1511678068, 7379191741) |
|||
moTest(BigInt(‘3047753288’), BigInt(‘2257683301’))</lang> |
|||
{{out}} |
|||
<pre> |
|||
ord(37) mod 3343 = 1114 |
|||
ord([big]) mod 7919 = 3959 |
|||
ord([big]) mod 15485863 = 15485862 |
|||
ord([big]) mod 22801763489 = 22801763488 |
|||
ord(1511678068) mod 7379191741 = 614932645 |
|||
ord(3047753288) mod 2257683301 = 62713425 |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |