Re: Avoiding a znlog() computation

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Kurt Foster [2009-03-14 17:13]:
> 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))

l2 =znlog(b,g), I guess ?

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

Only in current svn: simply use

  znlog(b, alpha, n1)

e.g.

  ? a = Mod(4,13); b = Mod(3,13);
  ?  znlog(b, a, znorder(a))
  %1 = 2

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`