|
Bill Allombert on Tue, 23 May 2023 16:37:32 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: factor and factorint performances
|
- To: pari-dev@pari.math.u-bordeaux.fr
- Subject: Re: factor and factorint performances
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Tue, 23 May 2023 16:32:52 +0200
- Arc-authentication-results: i=1; smail; arc=none
- Arc-message-signature: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1684852362; c=relaxed/relaxed; bh=Kgp1nd4aqaxz6Cf9Kf7hik/EKv6TddRHa32ZUJ5prKs=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=uYsxITmMTYDV15QsConxsP4txPHsPngwUjAHmEIzGIefcq8NDEMqE8wecQH+hGtVTVya9Dt5qvueIWBQh48xlwodMzTPFrQ+XAF6LFq4p+H7TMh5Pkv2SgLIbZg9lxi9wA5xaG0FW0gBmGS81oeV2L4m7nMHRHE+Rod0HjWNNk9NZSsTFW+t4kkXrrqRExkuve2xMfCHm48F5A5ghrdYo2JYDmi6D5BNCVIRoQPrE+ceGiFrjpdyY/4chN2uRKLmAe1Yg1T3ar5aqYA3Id6Yj4+LeISHL2JlgVrp/EIJxwgymAI6zPGTO7PXejChpjTJ045sag42CW6YKkGMpzX3soWeF7Ur7Z02i6dNBttoxYgczWEkSnPpv0amMkPdjxcGPaHrt33vaJeHdXCg0eSJe4R1LpJCMxxKqUxpo3eXAxrAuES2ZN+a7Is2fSjMoJnwKC/gx2CwZTnYD4dYc8ltZcnx8PCQc+bCIhyVltlwsyti+FTFZ4nlVNFYr8EhQb/J+6VqAinNkuUR67W/COVvs3F+rJEVRFyRQekjxWn4GtTct+M+ApUAqzP1NvRjFq6tW+v0Te227Yr1//CL6zUIpyTjMQVE9zvGVum+bctXZRwea3Wu0N7B0Ucv5WoEO4B20Ckuj6QzAxkymbIn/1zv/jLpKwIqhOV5MCMoium4Xw0=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1684852362; cv=none; b=DYEAFm8BZfVv82VBCfd/dwU5DLWZ8XQZqXwpcfcprjaEhRFSA646e/1iLEFhLNI30qbSkuv7ngFTqrm7mPUjGRj6CL9QngbA9z5uIN9m16gBDB2xLRZErRlYN7mDMf8RSo948t70DOwhA5dkR1bayb9E9sFbOv+xSr1Ck0/rg66Ewy6vXBrwu+eZkCJc1GZuLaKtY+sCbgepPI+Zz3R41cAtVV7n5PebD3dv85JUXyChzXx7F+e/Bl5BlJ/YSldGq9o96Bkw795KiG3iBs5mr+OQuwx51xwNAa/c3RVy7ijYx1WasLnCTcuzX57TD6eunhs2zU2mEymujHe9ltpgSZh7GVlw13WaugNkZ0AxHv67Pl4UbvUvwm+lb/m1SeihoP1J95fOhC2aO33mMpgfeokMzbDhYQd9Pf9RMiM5cZ+Ou6rOMucZtTHkCPD5M1lLmNg25yu5b7IKpDR+cPItyamqH444ItaSK9QfjTJK1PB35i6OiG1xA7zMaUP3aFLcuP+vJOTJd/DxAz2rPCCPDEfLDW+oMUP8JnxMShwPTcwBuMDcChucu76dkMrorDPZOjds4yLdqWDLKgzPi0htZ6FpquesDorx/j2LSp/UaFlcpZYR0RgRAYyEe24Iu0tGxCH6Zmx1zoRexpFh94iA5VJSRlMTKd8wi3Vq5+taY2w=
- Authentication-results: smail; dmarc=none header.from=math.u-bordeaux.fr
- Authentication-results: smail; arc=none
- Delivery-date: Tue, 23 May 2023 16:37:32 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1684852362; bh=Kgp1nd4aqaxz6Cf9Kf7hik/EKv6TddRHa32ZUJ5prKs=; h=Date:From:To:Subject:References:In-Reply-To:From; b=gWX3M2JxWfCj5FQ8dzAfADYVyKBjujxN3avicKU5lDj0w92Y2g90it6f9zzTnRZJs +8YnTqfHRbHsyafCE2tRyPy1oTFqrqzZOlnqEjjbPfaUBLOqXQia4M2hvMv9sgdWdt ozx71Eii1uVCS37qQ4FJk8MHOsKoeZillt9IFGkjmEU4ov54SPAITpDFRqHsRydAHl AxP6ErFGYmLE5z24a2TLfqRXz0tDGzizGLJPQ/f2JwLuaFbbGorAfa4x3wSaT5Qa45 gCpr4CJZ967+FEfpE+qzeoh6dZK6cKlTiD8S+cCUMnKZzp8KvKmjkV2QugeO+UBBIM 0DnRl7nZkSA7kmaj/Ibnqd3lDQmFCWhZyXx+fjKe4fWfeCFJ62mR/RehDSf655PmjQ Tj9BylDcx0EWp1x2/EndNWbJC1+cavUJSP+SVAy/PIlY7aUKaxuoXgRBHm78LkL45+ fZ0qtxfnlwh+5sr/jX5lsetiWqDrInAemzXKUKaD6z/2yOPE5deFd59JQ1hTTk6c2P j3ApPctTiCNYpIOqK/JPdtRIlVbSwbtMe4g4Icmz9p9wfQmv2UXkd6mEQjlYkYjhlA DAnza2s4HNi2wqmuQIRhCVnn1FdX5umNUdJ6j9RtvavWJd04baJ4Z3WW+7wYAOFWtq Cz0cpXgO7+L0qIR0ljGtH9dg=
- In-reply-to: <1ce43d63-78db-9df0-9a1d-8b5fc747aae7@free.fr>
- Mail-followup-to: pari-dev@pari.math.u-bordeaux.fr
- References: <1ce43d63-78db-9df0-9a1d-8b5fc747aae7@free.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.