Re: issquare() for t_INTMOD's

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

On Thu, Oct 20, 2011 at 07:32:55PM -0400, Alan McConnell wrote:
> On Fri, Oct 21, 2011 at 01:11:08AM +0200, Bill Allombert wrote:
> >
> > > 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).
>   	 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!

I am afraid this is not that easy. Basically there are two classes of
algorithms:
1) algorithms that can prove that a number is composite.
2) algorithms that can prove that a number is prime.

So given a number, you can start by algo 1) or by algo 2). It is some kind of
bet: you can bet that the number is composite and start by 1), or bet that the
number is prime and start by 2). If you lose, you have to run both algorithms
instead of only one.

Now, given a random number less than 10^10, there is more than 95% of chance that
it is composite, so factor() reasonnably bet on 'composite'. On the other hand, 
isprime expect to be called mostly on prime numbers, so it bet on 'prime'.

The real bug is maybe that issquare should be expected to be called mostly with
prime moduli, and calls isprime before factor.

Cheers,
Bill.