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

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,