Re: modular square roots

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

On Sun, Mar 13, 2005 at 12:05:58AM +0100, Bill Allombert wrote:
> 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 ?

Gonzalo Tornaria told me that this criterion was optimal for random
values of the radicand in average, but it was not for -1 and powers of
two.

So eventually we could special case -1 and use another criterion in that
case.

I just commited a change proposed by Gonzalo that should make things
a bit faster for -1.

Cheers,
Bill