Re: factor and factorint performances

Le 23/05/2023 à 12:40, Jean-Luc ARNAUD a écrit :
>
> 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.
>
> Could this be a solution? How would you do that?
>
> TIA for your help.
>
> -- 
> Jean-Luc Arnaud

Thank you to all of you, Aurel, Charles, Bill and Georgi.

cunninghamprimes.gp seems to be an easy solution.

-- 
Jean-Luc Arnaud