Re: Issquare function

["Karim Belabas" <belabas@math.u-bordeaux1.fr>]

* Tautócrona [2006-01-03 18:36]:
> Hi:
> 
> I want to know how is implemented the issquare( ) function for Pari-GP when the
> argument is a natural number.
> 
> I think the program checks several quadratic residue conditions to see if the number is a
> quadratic non-residue, and if all the conditions are true, then compute I = intsqrt (n) 
> and check if I^2 = n. Is
> this correct?

Yes.

> If it is, how many conditions and in which Z_n's are they done? Why these and not others?

See src/basemath/arith1.c:carremod()

We check modulo N = 64 * 63 * 65 * 11 = 2882880 [ cost ~ 1 long division,
3 small divisions and <= 4 table lookups ]. The proportion of squares in each
of the residue rings is

  12/64 < 16/63 < 21/65 < 6/11, 

for a total of 6 / 715 < 1/100 quadratic residues in Z/NZ. Computing mod p^k
instead of mod p for p > 3 would make tables larger for a negligible
improvement. Adding extra primes p >= 17 would add one table every
2 primes, and eliminate roughly 3/4 of surviving non-squares.

But this would quickly involve extra long divisions, whereas on average we
already expect less than 1 / 100 of our square roots to yield a
non-square...

    Karim.
-- 
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]