|
Bill Allombert on Wed, 19 Apr 2023 19:29:05 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: Factoring Carmichael Numbers
|
- To: pari-dev@pari.math.u-bordeaux.fr
- Subject: Re: Factoring Carmichael Numbers
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Wed, 19 Apr 2023 19:23:41 +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=1681925261; c=relaxed/relaxed; bh=jGpgxJ/DUDPylAJVjfk4i8bqh/ZH74r0vROqsbaI4WI=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=DZkREyaeqz+aWhCYNrD2ZT6PZuY+BreGQBUU0E/X1BpXNlrV/Bbgoo5uj2bTUjA+fsHUIOsUJINMhmSoP7URoOoVG1hW02JyXD1u655AA1UqC4rie67keL8OGJWbYkxHoPlFqz17LvjGbFKhpoUmzmyWtNgpzYjC66C551JWu4/dyAbnok0/sXMngfumP11A//lNjz6IPi1u+iVHsvlMqCVf4vAg7567fAZmmSeaDp0okTdrnsyb1VIwku6GchEu6yQ52t9B4408QeO3ZHecw1r+GLsoATh5OS2TJmW8eCMeTiA/054WahvtpDF0wvoGMtPw2EObjXKdEUufvaXKELGyGkYUJm+ldkYxr96rvk/tXN4a6+kbC5fsQcJ4gbeifdfVHiJkYoaD3L7kXDIatAf7Wj3BvFO/2v+QQMcwEkdvythAFkuKB4XVtfSRmxOJzPYiBrr+GtwzAdfd03yU/0fDZsspeFn4FteGWoG9BS5EwrbMxdfdYFBNiKkALt64i7T2qF0UAG1TnZ0bySuan6I/eShKKyhKO0d9h6JZr7NYTdRsTqNyriW6CMSwV1pQdp1GrbetBahjTfhNAPlVC4FAPheVNMFnX5OLXc8OqhT2gdnhM+M5xzItRaEdxOb9fxGgZeOUotjzS80KWyACzq3jjlAzX7ujxFq7yc5hUwY=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1681925261; cv=none; b=J+5zGk/p0SN8mS1Rt+rpR5mBKziPHE5oJphuruE5wvhHyr5wsuE6TMmJc7VwX9j7qD2+Ygb9BAoGtu/HvtrqtmUjaRUZvwz2LOUik616/qjC/aiFyRXQDkok4NK58KbT4UcyytP+941tT1j5NJEqZVOaxX1xl25wIzgPEdJ9wxYVz8rCQ8mk2/wihS9BZEQt05fa6JWvAvQMJCByZYiIcVF9A9pU0dxB5WXCffkHWu/x1mkHE3coEagzryhLthbGQ+w9jAmgdyZ35yGbWeOcMgxZ9oEsYyfkXiRjV+nROmaCJIidL4QVgT6qCAtDyYzVR4Y5JuFTMURJaXhaTylL4nKdYJc9W9qGUN1eWPBLPY0BypWmoX3JhKs43diqFW0qcaSQxIl8JFjpy3l4lS1HKPps/5TBRJ0t5IQdG6U0tTYw4I/RcXRjTeqAI3+uFEBKvnumV3nVI39+e/0lLWODdEYMaToktKnHJsksL9hEuxC/+uJuKnKY8PRssNaT23OGN+YTLnIWP9BPl/BwzAWK6MTYSIUJwfgNnXyQ/l8nYo4laSj+7Jq85frDhNBxhNydbbOtEaODRqp2LOZPbzcRUq/iSWwbOouC4q2w3D7//QVw3GCXhKtua1b2/xnCKM0fbs8ga1H8DOTDEL2XERBCLGj1sSA4iRKFFQfkU8x0CUQ=
- Authentication-results: smail; arc=none
- Delivery-date: Wed, 19 Apr 2023 19:29:05 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1681925261; bh=jGpgxJ/DUDPylAJVjfk4i8bqh/ZH74r0vROqsbaI4WI=; h=Date:From:To:Subject:References:In-Reply-To:From; b=s4OD8Qs2W3vEHs3in8c0AmUGgwDHs5ZKHdL6at1QuPOGAvWk0ScLLLNfvbeiM/XFS RaoH2qqa3/qwQ0I+DLXJfbc5+tLoVBUPz1dRFw4H2/vLxkyPF84yEENU/r+L7aUEGk 8Ox8ozxIqmjrwWNZgp1qd/KMKLYGBtkDjB4VwQzzNI7zao5tBuudKujzgalbPcTu0M P7E28RPSyrtzYz6gsstLFDFiEYpUde3uMVAlXviXniagiNPk8gjbhinEQnsKhyE9yv zVSbR0E7A5Xz+AwOr7qlejgLzkKesvG5h/WxDmE0qfAJvlHZPt0mJBhKQczzWoUc1d vck1rVDS5LS158lWsM2Mo3jaVbl+8v6ygPgBHemyQbZ48TCP3oxhm2d0so2iF2N8yR rQLd2XolXwHXz//NewoIUEyPdoD5gEbGyfE8b8+3FefpUJpVdK10IMJLBjvzcpGkCG AqioqScIl+aeViBEJFumZssXkQMzXv8UW2YtLfbWGOORUGhXaiJIHxfv3pr4zBgt+v yq1taB1BQSEM4G0JZLQEUu3xDYdN2IFYdRUmN4bZSRKavEKxaNZfFMmxz7bYtGFcQS 86JrjWV6l3vFaDHRkKZs7VLtNMwtOrQl6JpnisEIB2txV8nqczorY2M+f3imq55Br1 beGA//QG8UjFaWBY7uPkI+DY=
- In-reply-to: <trinity-d6f52275-fcc2-42d0-a314-d7da5527a1f9-1681863063683@3c-app-mailcom-lxa09>
- Mail-followup-to: pari-dev@pari.math.u-bordeaux.fr
- References: <trinity-d6f52275-fcc2-42d0-a314-d7da5527a1f9-1681863063683@3c-app-mailcom-lxa09>
On Wed, Apr 19, 2023 at 02:11:03AM +0200, Paul Underwood wrote:
> All timings were done on a single core of a 1.7GHz Celeron laptop with 1GB of
> memory allocated. For the 3808 digit number [1] with 662 factors:
> 23.0 seconds using Pari/GP's factor().
> 21.6 seconds using the above code.
>
> For the 43779 digit number [1] with 5616 factors 5,443.5 seconds. The
> function factor() ran out of memory after 21 hours and did not complete the
> task it was given.
Hello Paul,
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.
For 662.txt, it would finish in less than 5 seconds.
For 5616.txt, it would take 7h, 6min, 216 ms.
Cheers,
Bill