Re: factor and factorint performances

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Tue, May 23, 2023 at 12:40:03PM +0200, 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.

One simple solution suggested by Aurel!

Download <https://pari.math.u-bordeaux.fr/~bill/cunninghamprimes.gp>
do
? \r cunninghamprimes.gp
? factor(2^1003-1)
%1 = [131071,1;179951,1;3203431780337,1;605829388649921,1;1629239097907113911209,1;2252765682876603539639635308408558411526609,1;510220743809683794945526871987297018137321953892784240125078452679188592515535212261018198220942306424734402550338905905543998907950309832989158142146708664266462115666205013234650790948708097066620791,1]
? ##
  ***   last result: cpu time 2,089 ms, real time 2,089 ms.

Cheers,
Bill