Bill Allombert on Fri, 17 Dec 2004 01:02:53 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: znprimroot wishlist


On Thu, Dec 16, 2004 at 06:23:39PM -0500, Ken T Takusagawa wrote:
> (1) znprimroot does a very large number of Miller-Rabin
> tests when given a large prime as input.  It would be nice
> if the number of tests could be limited to (say) 10.

Are you using the stable version ? I expect the development version to
be more efficient here.

> (2) znprimroot tries to factor P-1, a task that will take
> forever for large inputs.  It would be nice if the
> factorization (obtained by other means) could specified as
> one of the arguments to the command.

You can solve both problems using addprimes() by adding p
and the factors of p-1 so factor can easily find them:

if p is a large prime, and F is the list of prime factors of p-1,
you can do

addprimes(p)
addprimes(F)

then znprimroot(x,p) will be much faster.

Cheers,
Bill.