35 lines
880 B
Text
35 lines
880 B
Text
var BN =Import("zklBigNum");
|
|
var Sieve=Import("sieve");
|
|
|
|
// factor n into powers of primes
|
|
// eg 9090 == 2^1 * 3^2 * 5^1 * 101^1
|
|
fcn factor2PP(n){ // lazy factors using lazy primes --> (prime,power) ...
|
|
Utils.Generator(fcn(a){
|
|
primes:=Utils.Generator(Sieve.postponed_sieve);
|
|
foreach p in (primes){
|
|
e:=0; while(a%p == 0){ a /= p; e+=1; }
|
|
if (e) vm.yield(p,e);
|
|
if (a<p*p) break;
|
|
}
|
|
if (a>1) vm.yield(a,1);
|
|
},n)
|
|
}
|
|
|
|
fcn _multOrdr1(a,p,e){
|
|
m:=p.pow(e);
|
|
t:=m/p*(p - 1);
|
|
qs:=L(BN(1));
|
|
foreach p2,e2 in (factor2PP(t)){
|
|
qs=[[(e,q); [0..e2]; qs; '{ q*BN(p2).pow(e) }]];
|
|
}
|
|
qs.filter1('wrap(q){ a.powm(q,m)==1 });
|
|
}
|
|
|
|
fcn multiOrder(a,m){
|
|
if (m.gcd(a)!=1) throw(Exception.ValueError("Not co-prime"));
|
|
res:=BN(1);
|
|
foreach p,e in (factor2PP(m)){
|
|
res = res.lcm(_multOrdr1(BN(a),BN(p),e));
|
|
}
|
|
return(res);
|
|
}
|