Phil Carmody on Sat, 12 Mar 2005 23:34:35 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: modular square roots |
--- 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/