|Bill Allombert on Sat, 14 Mar 2009 18:33:28 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Avoiding a znlog() computation|
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.