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);
}