Karim Belabas on Tue, 03 Jan 2006 19:03:44 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Issquare function |
* 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]