Re: factor and factorint performances

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