|
Bill Allombert on Tue, 23 May 2023 17:39:18 +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 17:34:39 +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=1684856069; c=relaxed/relaxed; bh=JRV5dCsxmNtIan2eQw/BMx+dww4o2wiWazPSoKZQBNM=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=gNQ4lW2Z3taK9yucFvbqt+DXAJ+FPNBT1AuinBkUDW4Nv+KqrBd6Fdi0fhoTIlOcF4DVMaTJlvzqz/STwoUmZfZBqymL/zFPbpjQy97WI91d3M02gdKxNLx2NbjkX1vxvNX4pO3uhwlUe/QDpZ4lZL1CYD7VLndOC9yVYc7vqcOvN3FYr7VC3H+HpPlr2mqnF/xriCRJsL6QTn2CdWgFp3TARU7Vm3h7FdtEhv5Epc9P57u3NjC7Ge66fFKbURIg6Pvf9p/hHMRe0Ls9WanOLcydeAXf4mvTXxIW0Dxpcvh1S8+MV2zNSpBOHEha8Zqqq9z709KXc8GiIejb1lL99XUVmEa6I9RP4ZKMfTB9sZ4iu02zANQqWtd8IvNir/9tQ319B4HGYMHriBy8C50A90p0LRKA8DAHjO6nIQpB9sWEU7aL9SlmDUzX80uCfYWARHJOX58I8F4Q4Qjzj5c2FsA/9gU42td96ZAvHNVd1m+7sv+WLerJ8ES8jZFbRcOPAzWJznQYxyTmHRVl/JbW2Nme7jiMc4tEcmB0YTffoHU2TNZyfNqbvw7JvNHtcvzEQyu1wnwCpuiknxMPy9+3O1GcQvPpV9ZGX8sCr6chgPmW3HwAxjeL8SdHVWVzF7Gi9YhdVUz5UqZwgCVyvkGyDa2dY17llIjOYP94iYpUJhA=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1684856069; cv=none; b=fKimNvG2xShbZ7unfG9hEwsStAqmGEcbvf9iQVWC5eBG1+6fsd35udtAuolxNxdJtAO37YIcbxPml+R1FwvgH/nUOEcV91Qtvk1z6H/hAvxACX9BzhCl8l/CSI74qe8CNcWDyNvCTmHdG3C0n/Eur8NU6LuxYbb5doWPgXQoBNPdZwvk99lasuv9Pi1WsAlKLgpUySFk+U3A3rs2YXvDo8LV42yg6dO8ZpuaZ7glaXVj3QbJxMy3bBHwU9G278EBzt6wGbyzer1jhpa24mlrTdK6gceWQ5g6hynfoRckIjaLvAAKjVPtMG1HtWaUi7LLdQq82i5Zil+mcaIUaLTEU8sJ8W1bOoqaDiSWz1zn8ZOOyBivEus4rxHjlSb8qywiTW+G5OZEn/cgys0ISPtVIobIpaiia4jsZy7N5T2cTUK4OqY3aGAGRfYQ85cSXjTVtmPcWDsO653EWagg0x+xL3OC3NRGk4vEd/Z5lhtQmH6DTl+drhKjnsc1KH064EC7ibBYzlycyjEJ/DJH59RyQnSXlWYU7m+2ZzWqGQ7QtQRT95Ri2Fq9h7nUpN5AlYOBDPAi5tvT1iq9pZF3xgLq77PidEEYp5dsrak5wnbmuHKgNopDezKYMDvZHIMIahRvhfY5Oeh6DvMyw0x7D1cAzG2rMqUPf/yzqEfp3lP9l1o=
- Authentication-results: smail; dmarc=none header.from=math.u-bordeaux.fr
- Authentication-results: smail; arc=none
- Delivery-date: Tue, 23 May 2023 17:39:19 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1684856069; bh=JRV5dCsxmNtIan2eQw/BMx+dww4o2wiWazPSoKZQBNM=; h=Date:From:To:Subject:References:In-Reply-To:From; b=lt47pgKfrkHvWQG81JY7wyROTOp9ushLP+bY1JtwkSYTIWY7qn/qC9YS48L82UPoO akNfmmb3qdIRzKawoykPLePWAYpnHpvPEJzls+RHceY5z4C0UBD9IbS5UfCWduwlru 4nPIIn09ovcYKTm+1dgu9KVTq/CRgvGpExIKNACi2l6R9e6rzhN/JF0c+wcCgDVHbB kSbEkn9Lq5wYUouca6H3WyH0FZgC2ttXS9nhpFeWosp6ObHVlFNK0QeVpQ+OGS0qAd Bh963ZMpH1x7B+xLRFMY79pF9uAMxd01aben1SRMxJJJ7ExWPO6V8QbRUyFH7K3xas u7PF13qLSf8Ng2hpq5HPnKh3ac9NByQA1C/hValhk5lEIF5mNW9UG5VM+w94ubccgy 8p848WlaA0wXWDCNsUwSJniVzqkX8kXmH9GFDqfTDc1QUHnelm5M3+3XH+xf+vI1Wy csp7zYGZGuq0+lWKVUxyk6LpwXNRrFEpFre4m2Mg4RKHsY+fc5US6MaEf4A64/sBRX R2i6OiBlJgD0YyHAl1Dz8hYLfZzzLwrnii2Iw3LnpBOjvDnF4ZJSpIhfsmoOKtxbrK ERGKaBo7n0jUjDgP5d0FLlvKRdgs85/ETpycT9xWcDBsjpjiOYsCmYAr4tzrpNnHEO 7t1AhC7klunpoL8EaTa8Fplc=
- 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.
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