Multiplicative order: Difference between revisions
Added Wren
m (Phix/mpfr) |
(Added Wren) |
||
Line 2,243:
}
puts "OK, $n is the smallest n such that {$a $n $m} satisfies $lambda"</lang>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
<lang ecmascript>import "/big" for BigInt
class PExp {
construct new(prime, exp) {
_prime = prime
_exp = exp
}
prime { _prime }
exp { _exp }
}
var moBachShallit58 = Fn.new { |a, n, pf|
var n1 = n - BigInt.one
var mo = BigInt.one
for (pe in pf) {
var y = n1 / pe.prime.pow(pe.exp)
var o = 0
var x = a.modPow(y, n.abs)
while (x > BigInt.one) {
x = x.modPow(pe.prime, n.abs)
o = o + 1
}
var o1 = BigInt.new(o)
o1 = pe.prime.pow(o1)
o1 = o1 / BigInt.gcd(mo, o1)
mo = mo * o1
}
return mo
}
var factor = Fn.new { |n|
var pf = []
var nn = n.copy()
var e = 0
while (!nn.testBit(e)) e = e + 1
if (e > 0) {
nn = nn >> e
pf.add(PExp.new(BigInt.two, e))
}
var s = nn.isqrt
var d = BigInt.three
while (nn > BigInt.one) {
if (d > s) d = nn
e = 0
while (true) {
var dm = nn.divMod(d)
if (dm[1].bitLength > 0) break
nn = dm[0]
e = e + 1
}
if (e > 0) {
pf.add(PExp.new(d, e))
s = nn.isqrt
}
d = d + BigInt.two
}
return pf
}
var moTest = Fn.new { |a, n|
if (!n.isProbablePrime(10)) {
System.print("Not computed. Modulus must be prime for this algorithm.")
return
}
System.write((a.bitLength < 100) ? "ord(%(a))" : "ord([big])")
System.write((n.bitLength < 100) ? " mod %(n) " : "mod([big])")
var mob = moBachShallit58.call(a, n, factor.call(n - BigInt.one))
System.print("= %(mob)")
}
moTest.call(BigInt.new(37), BigInt.new(3343))
var b = BigInt.ten.pow(100) + BigInt.one
moTest.call(b, BigInt.new(7919))
b = BigInt.ten.pow(1000) + BigInt.one
moTest.call(b, BigInt.new(15485863))
b = BigInt.ten.pow(10000) - BigInt.one
moTest.call(b, BigInt.new(22801763489))
moTest.call(BigInt.new(1511678068), BigInt.new(7379191741))
moTest.call(BigInt.new(3047753288), BigInt.new(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|zkl}}==
| |||