|Kurt Foster on Sat, 14 Mar 2009 17:10:41 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Avoiding a znlog() computation|
Suppose that a and b are given, and for some prime p you know that n1 = znorder(Mod(a,p),p-1) and Mod(b,p)^n1 == Mod(1,p).Then the multiplicative order n2 of b (mod p) is automatically a divisor of n1, so we can compute it using n2 = znorder(Mod(b.p),n1).
Then alpha = Mod(a,p)^(n1/n2) has multiplicative order n2, so Mod(b,p) = alpha^k for a unique k in (0, n2) with gcd(k, n2) ==1. The problem is, how to determine k. One way is to letg = znprimroot(p); l1 = znlog(alpha,g);l2 =znlog(b,p);k=lift(Mod(l2/ l1,n2))
but this entails finding a primitive root and TWO znlog()s. Given that Mod(k,n2) is already known to be well defined, is there a more direct/faster way to compute it?