Bill Allombert on Sat, 12 Mar 2005 16:25:20 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: modular square roots |
On Sat, Mar 12, 2005 at 04:41:06AM -0800, Phil Carmody wrote: > The following seems to give a non-zero result on various versions of GP, > including the latest nightly build. > > lift(sqrt(Mod(-1,73!+1))^2+1) > > For the ones that fail they fail for all larger n!+1 primes too, but not > smaller such primes. > > The only version I can find that works is 2.2.8 build 1.999. This was a GMP kernel specific problem in the implementation of Cipolla algorithm used for the squareroot (because v_2(p-1) is large for p=n!+1). sqrt_Cipolla includes its own binary powering code and accessed the bits of the exponents without using the t_INT interfaces. It should be fixed in CVS now. However a better fix might be to use leftright_pow() instead. Thanks for the report, Bill.