Kurt Foster on Sat, 14 Mar 2009 17:10:41 +0100

 Avoiding a znlog() computation

• To: Pari Users <pari-users@list.cr.yp.to>
• Subject: Avoiding a znlog() computation
• Date: Sat, 14 Mar 2009 10:08:38 -0600
• Delivery-date: Sat, 14 Mar 2009 17:10:41 +0100
• Mailing-list: contact pari-users-help@list.cr.yp.to; run by ezmlm

```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 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?
```
```