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.

They probably use the Cuninngham tables, see

http://www.leyland.vispa.com/numth/factorization/cunningham/2-.txt
...
1003	605829388649921.1629239097907113911209.2252765682876603539639635308408558411526609.	P201

So you can do

? addprimes([605829388649921,1629239097907113911209,2252765682876603539639635308408558411526609])
%1 = [605829388649921,1629239097907113911209,2252765682876603539639635308408558411526609]
? factor(2^1003-1)
%2 = [131071,1;179951,1;3203431780337,1;605829388649921,1;1629239097907113911209,1;2252765682876603539639635308408558411526609,1;510220743809683794945526871987297018137321953892784240125078452679188592515535212261018198220942306424734402550338905905543998907950309832989158142146708664266462115666205013234650790948708097066620791,1]
? ##
  ***   last result computed in 2,168 ms.

There used to be a GP package "fullfactor" that does that for you by Jeroen Demeyer, see
https://pari.math.u-bordeaux.fr/Scripts/
Unfortunately the link is dead but you can get it there:
https://web.archive.org/web/20190316085632/http://cage.ugent.be/~jdemeyer/computer/fullfactor.html
Unfortunately it needs some minor updating,
but then you can do:
? fullfactor(partial_factor_pn_1(2,1003))
%1 = [131071,1;179951,1;3203431780337,1;605829388649921,1;1629239097907113911209,1;2252765682876603539639635308408558411526609,1;510220743809683794945526871987297018137321953892784240125078452679188592515535212261018198220942306424734402550338905905543998907950309832989158142146708664266462115666205013234650790948708097066620791,1]
? ##
  ***   last result computed in 4 ms.

Cheers,
Bill.