Re: Issquare function

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

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.