Multiplicative order: Difference between revisions
Added 11l
Alextretyak (talk | contribs) (Added 11l) |
|||
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>.
<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}}==
| |||