Multiplicative order: Difference between revisions
Content added Content deleted
(→{{header|Julia}}: updated factors() function) |
(Add Seed7 example) |
||
Line 851: | Line 851: | ||
puts 'Everything checks.' |
puts 'Everything checks.' |
||
end</lang> |
end</lang> |
||
=={{header|Seed7}}== |
|||
<lang seed7>$ include "seed7_05.s7i"; |
|||
include "bigint.s7i"; |
|||
const type: oneFactor is new struct |
|||
var bigInteger: prime is 0_; |
|||
var integer: exp is 0; |
|||
end struct; |
|||
const func oneFactor: oneFactor (in bigInteger: prime, in integer: exp) is func |
|||
result |
|||
var oneFactor: aFactor is oneFactor.value; |
|||
begin |
|||
aFactor.prime := prime; |
|||
aFactor.exp := exp; |
|||
end func; |
|||
const func array oneFactor: factor (in var bigInteger: n) is func |
|||
result |
|||
var array oneFactor: pf is 0 times oneFactor.value; |
|||
local |
|||
var integer: e is 0; |
|||
var bigInteger: d is 0_; |
|||
var bigInteger: s is 0_; |
|||
begin |
|||
e := lowestSetBit(n); |
|||
if e > 0 then |
|||
n >>:= e; |
|||
pf := [] (oneFactor(2_, e)); |
|||
end if; |
|||
s := sqrt(n); |
|||
d := 3_; |
|||
while n > 1_ do |
|||
if d > s then |
|||
d := n; |
|||
end if; |
|||
e := 0; |
|||
while n rem d = 0_ do |
|||
n := n div d; |
|||
incr(e); |
|||
end while; |
|||
if e > 0 then |
|||
pf &:= oneFactor(d, e); |
|||
s := sqrt(n); |
|||
end if; |
|||
d +:= 2_; |
|||
end while; |
|||
end func; |
|||
const func bigInteger: moBachShallit58(in bigInteger: a, in bigInteger: n, in array oneFactor: pf) is func |
|||
result |
|||
var bigInteger: mo is 0_; |
|||
local |
|||
var bigInteger: n1 is 0_; |
|||
var oneFactor: pe is oneFactor.value; |
|||
var bigInteger: x is 0_; |
|||
var bigInteger: y is 0_; |
|||
var integer: o is 0; |
|||
var bigInteger: o1 is 0_; |
|||
begin |
|||
n1 := n - 1_; |
|||
mo := 1_; |
|||
for pe range pf do |
|||
y := n1 div pe.prime ** pe.exp; |
|||
x := modPow(a, y, n); |
|||
o := 0; |
|||
while x > 1_ do |
|||
x := modPow(x, pe.prime, n); |
|||
incr(o); |
|||
end while; |
|||
o1 := pe.prime ** o; |
|||
mo *:= o1 div gcd(mo, o1); |
|||
end for; |
|||
end func; |
|||
const func boolean: isProbablyPrime (in bigInteger: primeCandidate, in var integer: count) is func |
|||
result |
|||
var boolean: isProbablyPrime is TRUE; |
|||
local |
|||
var bigInteger: aRandomNumber is 0_; |
|||
begin |
|||
while isProbablyPrime and count > 0 do |
|||
aRandomNumber := rand(1_, pred(primeCandidate)); |
|||
isProbablyPrime := modPow(aRandomNumber, pred(primeCandidate), primeCandidate) = 1_; |
|||
decr(count); |
|||
end while; |
|||
# writeln(count); |
|||
end func; |
|||
const proc: moTest (in bigInteger: a, in bigInteger: n) is func |
|||
begin |
|||
if bitLength(a) < 100 then |
|||
write("ord(" <& a <& ")"); |
|||
else |
|||
write("ord([big])"); |
|||
end if; |
|||
if bitLength(n) < 100 then |
|||
write(" mod " <& n <& " "); |
|||
else |
|||
write(" mod [big] "); |
|||
end if; |
|||
if not isProbablyPrime(n, 20) then |
|||
writeln("not computed. modulus must be prime for this algorithm.") |
|||
else |
|||
writeln("= " <& moBachShallit58(a, n, factor(n - 1_))); |
|||
end if; |
|||
end func; |
|||
const proc: main is func |
|||
local |
|||
var bigInteger: b is 100_; |
|||
begin |
|||
moTest(37_, 3343_); |
|||
moTest(10_ ** 100 + 1_, 7919_); |
|||
moTest(10_ ** 1000 + 1_, 15485863_); |
|||
moTest(10_ ** 10000 - 1_, 22801763489_); |
|||
moTest(1511678068_, 7379191741_); |
|||
moTest(3047753288_, 2257683301_); |
|||
end func;</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|Tcl}}== |
=={{header|Tcl}}== |