118 lines
2.9 KiB
Text
118 lines
2.9 KiB
Text
$ 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;
|