Bill Allombert on Thu, 20 Oct 2011 22:59:50 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: issquare() for t_INTMOD's


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))

This is because kronecker() is only equivalent to issquare if p is prime.

(when I eat too much chocolate, I dream I add a way to tag numbers as primes to
avoid such check).

Cheers,
Bill.