Multiplicative order: Difference between revisions

=={{header|zkl}}==

{{trans|Python}}

Using [[Extensible prime generator#zkl]] and the GMP library for lcm (least common multiple), pow and powm ((n^e)%m)

It would probably be nice to memoize the prime numbers but that isn't necessary for this task.

<lang zkl>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);

}</lang>

<lang zkl>multiOrder(37,1000).println();

b:=BN(10).pow(20)-1;

multiOrder(2,b).println();

multiOrder(17,b).println();

b=0d10_0001;

[BN(1)..multiOrder(54,b)-1].filter1('wrap(r,b54){b54.powm(r,b)==1},BN(54)) :

if (_) println("Exists a power r < 9090 where (54^r)%b)==1");

else println("Everything checks.");</lang>

{{out}}

<pre>

100

3748806900

1499522760

Everything checks.

</pre>