Re: kro(a,q) vs. issquare()

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

On Tue, 7 Aug 2001, John Cremona wrote:
> Why is kro(a,q) very much faster (about 3 times) than issquare for
> testing modular squares?

Because Kronecker-Jacobi symbol cannot ascertain that a is a square without
factoring q (which you implicitly assume to be prime when using kro()).

Admitedly, pari should FIRST compute kro, THEN factor q (in case answer
wasn't -1). Currently it always factors q which is a waste half of the
time.

Also, for such small numbers, factor() is much better at primality "proving"
than isprime is:
(02:28) gp > for(i=1,10^4, isprime(103))
time = 1,410 ms.
(02:28) gp > for(i=1,10^4,factor(103))
time = 510 ms.

This should be retuned somehow...

> If it is because issquare() is also computing the root (returned through
> an optional second argument) then there is still something wrong since
> that does not work with this type:  issquare(aa,&b) gives the error
> message   ***   not an integer argument in an arithmetic function

The documentation specifies that the optional second argument is only allowed
when an exact square root HAS to be computed, which is not the case here. It
looks like a better idea to allow it in all cases, for the sake of
consistency. I'll change that.

Cheers,

    Karim.

-- 
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://www.parigp-home.de/