Max Alekseyev on Fri, 21 Oct 2011 00:53:04 +0200


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

Re: issquare() for t_INTMOD's


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?

Regards,
Max