Re: issquare() for t_INTMOD's

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

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

Cheers,
Bill.