[seqfan] Re: (3^n+1)/2 is prime, A171381

[Charles Greathouse]

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.

Charles Greathouse
Analyst/Programmer
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/
>