Anonymous user
Multiplicative order: Difference between revisions
→{{header|J}}
(→{{header|Perl 6}}: add entry) |
|||
Line 545:
2 mo _1+10^80x
190174169488577769580266953193403101748804183400400</lang>
=={{header|Julia}}==
(Uses the <code>factors</code> function from [[Factors of an integer#Julia]].)
<lang julia>function factors(p)
f = Array(typeof(p), 0)
n = one(p)
while n*n < p
if p % n == 0
push!(f, n)
push!(f, div(p, n))
end
n += one(p)
end
n*n == p && push!(f, n)
return sort!(f)
end
function multorder(a, m)
gcd(a,m) == 1 || error("$a and $m are not coprime")
res = one(m)
for (p,e) in factor(m)
m = p^e
t = div(m, p) * (p-1)
for f in factors(t)
if powermod(a, f, m) == 1
res = lcm(res, f)
break
end
end
end
res
end</lang>
Example output (using <code>big</code> to employ arbitrary-precision arithmetic where needed):
<pre>
julia> multorder(37, 1000)
100
julia> multorder(big(10)^100 + 1, 7919)
3959
julia> multorder(big(10)^1000 + 1, 15485863)
15485862
julia> multorder(big(10)^10000 - 1, 22801763489)
22801763488
</pre>
=={{header|Mathematica}}==
| |||