|
Bill Allombert on Wed, 26 Apr 2023 18:07:07 +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, 26 Apr 2023 18:05:51 +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=1682525143; c=relaxed/relaxed; bh=GhxXN/z5GAqN481SE+nRp0M7tA8k64Mypwdvmf4Y6AY=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=mGeuve0e+OHu2OnzPE3+OIRXBCgAHjLTJNIbNBONn7+k/TcpeTSc8kUrMerGjZiRK+GamoC2kapViSquJ4BYENjWk/zxBQUpueZ96fgXBPLXkPR3h2hC/FbjMdTl83er9ZdobANnd64V1NFJtVRUGkviOH1Jxx1GlW5PrOdIrx8cH3AaGPC+U9s3dcaWbGrB3HTkc1+NNoAX8Wohm5xIE3PTSINDIjcflbEC/9R8oJ7BKWr7JVPl99Wc+dcfURGkAQKKtFUNHatMlQePhnNuRbkfKPeaTEomAucF5H6IDPqdbuVw187T6PNfUgLrgws6Y5kjyFtNPXUEZvUXpq/DKLcBNXZf5G+PbFWjfq1OSZXVbDfdmlZbVA5qghISfy7kbBtm4Lz22NmJIdkn4ElgPwrWHjj8s24ueSFOhrslaoHH4lza4sHDP4cdYkviwGNTDv9JdDvidP44AT/JuDaeyS5KKJoAZNBs1TqPkhUhEEeFVIZ128npwZ2qKKcbCSz5FSCAWG6Mfm1yZwNvLm5gULvJ29vjc7EzK5eUfCYSF0blhrDKhwYNY+w+hg0r4eY+nIGRgYKnSWD/fb8PMjQrhsu/jkfZg3IrdulgwxGSPGMuhjXpR4tJ1rVFaNqY16E3MAd3J+RcKfIBWb7olebudWPcQa8J6Z/cD79cYohjrbE=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1682525143; cv=none; b=pwEcowZDVSoQS8wNR2ndJvycmiJ4Hvkl6pD/KY6gTr43rTRSsONXgntgLkaJzlhzyEQ5HAimbXv/w4b+QczNvsn3zV/pLjZI34ImrBKLYYFIWxweWQQWzGBMDLuMuwUmAdrFFvBUgPNXScWIXVoH6vbPsXVtgEJnteFi7A0L3qkgjlc5kZveB6jvNfoIUq63LivGWNaz0dp2y4rsiUhDtBV3CYHPbYjj1Lzc+KV7cw398aCYmPCVsW+FiLOq12vBfpGYxmlzxpq7pYu/eyphwFokVteNFrMB4ZHKWbkdjYTYGX+cqXDdRXxrfcSMv5miYOQ0ar4XM39iC/mJK45rKYGMnMKinaSPRXoCRFY75DbPV46pHTAtN5t4Kc0s7mny+JV1rRH+jYKqXWzL67qrAXpN6uvfSxWoA4A+zD4xkFZ1l3Nb+wb3WGDN23Ari1pGYeGLV9+zBWXUXKYaeIrn2/G/m3EhokS5eK5yYwVKA0pUYyIrCWyxV0QZYrwRse4jZ4NGhSvRsrPOA50QYHwMhnUEpeMtw07MAl8GJk8mlb/fqbxeLcfERadw2mMxvuZKUrPT2/rLbe72rnEuEP2KQzgxtkXGvlVJ8qrjS2+b/BVxD+XZtn6dLJPNigkT/qp49C3GrXme7ncXztTywP3qEwKNpQMOHRx3/cN9Vsq8p80=
- Authentication-results: smail; arc=none
- Delivery-date: Wed, 26 Apr 2023 18:07:07 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1682525143; bh=GhxXN/z5GAqN481SE+nRp0M7tA8k64Mypwdvmf4Y6AY=; h=Date:From:To:Subject:References:In-Reply-To:From; b=N8AXhaJLaZY43F4frywu6tTeNneqCarrF+zbaOa7OUeCyOSs4RdvmmZ0C9s/Yq/8X JQt+6+sObfK9iyDgusPQJJ2ElEIZucHI9n5b9RY8tTXdaPAoV+QrQDjiZYGj2iwCkc vZmbpSN0HY35n9tQGTkEybKEMv2f5syquxSKDIdoBaA+VgfGMqUos4m7gTeRTt7YkJ eXPbvnBez5nlBe3BT5zpLb91HsLouZfdzhwY/oMij5JqAzEwlSoBAdweTPrU5SvxN+ nQZ5I/ZzGswvaUYCy3p3vLewmQ0l9HfNhV0uRwzdqlC0Rr2SAEw+sryP25Q5jA/Ajs qMXGDKfd/zA4PrxnHYYC8h5mQPicT9W4S0KkssnzH083UKdBe1VAjN5NcEiD8nmnK1 M8HYyyGgLco4wqWPLDbomNm0dub4Tlx140AeROADpGP2Gmf56mibH8vsAdhoXd5Ycb EEBij2d7OaQyWsITlYbFCDje4QqNp+wya8AT0+DU5yPZ95cI8rvi/WaVGhMv96POuo dLor97jhGJMf6SFcY+xD9WxCU5HL+cELkcjkl6osPaApYCZ0wjhZu8R/tDrZJ2nR+6 ke/I7IbW1VlejOfiG2UL9jxCvm4M8uYB4Agw6DR4WD9hfz5a4G8eRVN8I4XAb8kX9u 2DBkwNyb0ZThvZcQer5MlDas=
- In-reply-to: <trinity-de49f4de-bafc-48e0-862a-ee86905fae68-1681984783289@3c-app-mailcom-lxa15>
- Mail-followup-to: pari-dev@pari.math.u-bordeaux.fr
- References: <trinity-de49f4de-bafc-48e0-862a-ee86905fae68-1681984783289@3c-app-mailcom-lxa15>
On Thu, Apr 20, 2023 at 11:59:43AM +0200, Paul Underwood wrote:
> Hi Bill,
>
> thank you for the explanation about factor().
>
> I have majorly increased the speed of my code, partly by incorporating
> factor() into it, but mostly by switching from expensive 2 selfridges Lucas
> sequences to 1 selfridge "Miller-Rabin" type calculations. The code now
> computes the maximum g.c.d of N with the "simple" algebraic factors of
> a^(n-1)-1.
By curiosity, why would you need to factor such numbers ? They are almost always
built from their factorisation.
You can probably speed up your code by skipping ispseudoprime until the factor
are fairly small (or fail to factor).
Cheers,
Bill.