Bill Allombert on Sat, 22 Oct 2011 00:23:19 +0200

 Re: issquare() for t_INTMOD's

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