[seqfan] Re: (3^n+1)/2 is prime, A171381
charles.greathouse at case.edu
Mon Jun 14 18:15:44 CEST 2010
Some experiments with Pari suggest that a 3.0 GHz machine with 3.5 MB
of L2 cache (per core) could do a Rabin-Miller test on that number
(20, that is, 1.6 million bits) in about two weeks. Since you won't
find a machine with that much L2, you'd probably need a month.
That's actually not as bad as I had expected -- though maybe reality
won't be as forgiving as my estimates.
Case Western Reserve University
On Mon, Jun 14, 2010 at 10:15 AM, Joerg Arndt <arndt at jjj.de> wrote:
> * Georgi Guninski <guninski at guninski.com> [Jun 14. 2010 15:12]:
>> 16,17,18 failed the pari pseudoprime test in less than 2 hours.
>> This seems to leave the smallest candidates:
>> 20 - 0.5 million decimal digits
>> 22 - 2 million decimal digits
>> Looks like the scientific approach is first to run P-1 or EC
>> factoring (probably gmp-ecm) before pseudoprime tests. Have no idea
>> how long the pseudoprime test will take.
> Not quite, generally Rabin-Miller first.
> A 100k+ digit number that survives just one pass of
> RM is already very likely prime. After it survives
> 3 passes (small primes), let some proof-method
> hum away and wait.
> If the form of possible divisors is identified
> (which seems to be the case here), one could
> try the few smallest such divisors first (before RM)
> if this is much cheaper than one pass of RM.
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan