Re: modular square roots

[Phil Carmody <thefatphil@yahoo.co.uk>]

--- Bill Allombert <allomber@math.u-bordeaux.fr> wrote:
> 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).

OK, we though we had spotted a power-of-two connection. Few trailing 
zeroes implied greater chances of workingness in our tests.
 
> sqrt_Cipolla includes its own binary powering code and accessed the
> bits of the exponents without using the t_INT interfaces.

Are you sure you want to be doing Cipolla? For my own work I find 
Tonelli-Shanks to be superior speed-wise. Less pleasant for v_2 high, 
of course.

Of course, for roots of unity a simple randomised a^((p-1)/(2^i)) 
technique is even better still. 

> It should be fixed in CVS now. However a better fix might be to use
> leftright_pow() instead.

Each bug squashed is a bug squashed, that's what matters.

Phil

When inserting a CD, hold down shift to stop the AutoRun feature
In the Device Manager, disable the SbcpHid device.
http://www.cs.princeton.edu/~jhalderm/cd3/


		
__________________________________ 
Do you Yahoo!? 
Yahoo! Small Business - Try our new resources site!
http://smallbusiness.yahoo.com/resources/