Re: Avoiding a znlog() computation

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Sat, Mar 14, 2009 at 10:08:38AM -0600, Kurt Foster wrote:
> 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

Use znlog(b,alpha,n2).

Cheers,
Bill.