Karim BELABAS on Sat, 25 Aug 2001 02:37:55 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: kro(a,q) vs. issquare() |
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/