Re: issquare() for t_INTMOD's

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

* Bill Allombert [2011-10-21 01:11]:
> On Fri, Oct 21, 2011 at 02:52:57AM +0400, Max Alekseyev wrote:
>> On Fri, Oct 21, 2011 at 12:59 AM, Bill Allombert
>> <Bill.Allombert@math.u-bordeaux1.fr> wrote:
>>> On Thu, Oct 20, 2011 at 11:56:53PM +0400, Max Alekseyev wrote:
>>>> Why issquare() is so much slower than kronecker()?
>>>>
>>>> ? p = nextprime(10^10)
>>>> %1 = 10000000019
>>>> ? for(i=1,10^6, issquare( Mod(random(p),p) ) )
>>>> ? ##
>>>>   ***   last result computed in 19,690 ms.
>>>> ? for(i=1,10^6, kronecker(random(p),p) )
>>>> ? ##
>>>>   ***   last result computed in 521 ms.
>>>
>>> issquare need to check whether p is prime, but not kronecker.
>>> So you should compare against
>>> for(i=1,10^6, isprime(p) && kronecker(random(p),p))
>> 
>> ? for(i=1,10^6, isprime(p); kronecker(random(p),p) )
>> ? ##
>>  ***   last result computed in 2,893 ms.
>> 
>> This is still much better than issquare().
>> Why?
> 
> because issquare is actually doing factor(p), which for some reason is much
> slower than isprime(p).

I believe the problem has now gone away in testing branch (2.6.*, available
via git):

Current pari-stable (2.5.1) :

  ? p = nextprime(10^10);
  ? for(i=1,10^6, kronecker(random(p),p) )
  time = 476 ms.
  ? for(i=1,10^6, issquare( Mod(random(p),p) ) )  \\ slooow
  time = 18,586 ms.
  ? for(i=1,10^6, isprime(p) && kronecker(random(p),p))
  time = 2,700 ms.

Current pari-testing (2.6.*)

  ? p = nextprime(10^10);
  ? for(i=1,10^6, kronecker(random(p),p) )
  time = 468 ms.
  ? for(i=1,10^6, issquare( Mod(random(p),p) ) )  \\ better
  time = 2,460 ms.
  ? for(i=1,10^6, isprime(p) && kronecker(random(p),p))
  time = 2,677 ms.

Note that for "not-so-small" inputs (p > 2^64), factor(p) is much faster
than isprime(p), because by default it does not rigorously prove primality
of factors, whereas isprime (understandably) does. If you set 'factor_proven'
to 1 (*not* the recommended setting), you'll get the "expected" speeds:

  ? p = nextprime(10^20);
  ? default(factor_proven,0);
  ? for(i=1,10^4, isprime(p) )
  time = 7,084 ms.
  ? for(i=1,10^4, factor(p) )  \\ fast !
  time = 3,112 ms.

  ? default(factor_proven,1);
  ? for(i=1,10^4, isprime(p) )
  time = 7,080 ms.
  ? for(i=1,10^4, factor(p) )  \\ not so fast...
  time = 10,001 ms.

* Alan McConnell [2011-10-21 01:33]:
>  Bill, and other pari-developers: can some serious work be
>  done on this issue?   A lot of us mathematicians(and IT
>  crackers) really need for factor(p) to be as fast as
>  isprime(p).   Surely some polishing of the algorithms could
>  make this possible???   Please Really Hasten!

It's currently not possible to make factor(n) as fast as isprime(p) for
prime inputs, but the difference should be marginal and the above should
be the worst case behaviour: it (now) only comes down to the amount of
trial division before embarking on more costly algorithms: isprime()
expects its input to be prime more often than factor() does, so expends
less time in trial division. Also isprime doesn't care about valuations
and checks for many small primes divisors in one go.

This is not likely to change until somebody implements a super-fast
trial-divider (by all primes < 2^14, say, but a (slower) dynamic version
would also be nice). One only needs to figure a nice way to store
(static or dynamic) product trees, but a little tedious to implement
and test...

Cheers,

    K.B.
-- 
Karim Belabas, IMB (UMR 5251)  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-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`