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)


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 let

g = 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?