|Bill Allombert on Tue, 03 Jan 2006 19:31:51 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Issquare function|
On Tue, Jan 03, 2006 at 06:19:02PM +0100, Tautócrona wrote: > 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 this is correct. PARI/GP follows the Algorithm 1.7.3. in the GTM 138 agorithm: it checks if I is q square mod 64, 63, 65 and 11, and then use sqrtint(). Ultimatly the optimal algorithm would depend on the practical probability of I being a square (The higher the probability the lower the the number of modular test should be made): in most applications the integer I is not random and the probability of being a square can be high, so the best choice depends on the application. Cheers, Bill.