Re: modular square roots

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

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.