Re: factor and factorint performances

[Jean-Luc ARNAUD <jl.arnaud@free.fr>]

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