Anonymous user
Multiplicative order: Difference between revisions
Add Seed7 example
(→{{header|Julia}}: updated factors() function) |
(Add Seed7 example) |
||
Line 851:
puts 'Everything checks.'
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}}==
| |||