Re: factor and factorint performances

It's definitely not the primality tests -- on my machine, real primality
tests on all the prime factors take half a second, and I think the
factoring engine uses ispseudoprime by default anyway (1 ms), unless
default(factor_proven) is set.

If you're factoring a well-known or possibly well-known number, it's best
to check on factordb.com first to save some effort.

I think in general PARI/GP has world-class factoring for small numbers but
beyond 50 digits or so there are much better engines out there. After 90
digits it's rarely worthwhile to run PARI on them at all unless they're
particularly smooth.

For that number, it's probably best to use ECM (43-digit factor, a few
thousand curves at B1 = 11M or so), but SNFS and GNFS are also available.
Standard heuristics say GNFS would be faster than SNFS (assuming you get
the factors up through the 22-digit one with ECM first).

On Tue, May 23, 2023 at 8:10 AM Aurel Page <[email protected]>
wrote:

> Hi Jean-Luc,
>
> On 23/05/2023 12:40, Jean-Luc ARNAUD wrote:
>
> Hi everybody,
> Playing with factor and factorint functions, I was amazed at their
> performances (compared to other Math libraries), until I tried to factorize
> 2^1003-1.
> After more than 11 hours, no result ...
> So I tried this Web tool (https://www.dcode.fr/prime-factors-decomposition
> in English, https://www.dcode.fr/decomposition-nombres-premiers in
> French) and got a result in ... 2.25 seconds!!!!
> Unless they use a supercalculator (and I don't think so), their algorithm
> is very, very efficient.
> Is it possible to get the same performance using PariGP? In a previous
> message, Bill said that it could be possible to skip the primality test
> with factor.
>
> The reason PARI is slow is that it does a primality test each time it finds a factor.
> Since the number is large with lots of factors, then it takes a long time.
> (about 90s for each factor). So it should finish in about 54 hours.
>
> If we expected that the number do not have prime factors larger than some bounds, we
> could just skip the primality test.
>
> This number has few prime factors, so this is completely independent. You
> need real hard work to factor it. My guess is that the website you are
> linking to stores all known factors of Mersenne numbers.
>
> Best,
> Aurel
>
>