Re: modular square roots

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

On Sat, Mar 12, 2005 at 01:52:26PM -0800, Phil Carmody wrote:
> --- 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)
>  
> > 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.

We normally use Tonelli-Shanks, but we use Cipolla algorithm if e=v_2(p)
is large: see

src/basemath/arith1.c: line 1312
  /* If `e' is "too big", use Cipolla algorithm ! [GTL] */
    if (e*(e-1) > 20 + 8 * bit_accuracy(lgefint(p)))    

Would you propose a different criterion ?

> > 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.

Sure but it is the kind of bugs that should not be there in the first
place, because there was probably no need to reimplement leftright_pow.

Cheers,
Bill.