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

[Joerg Arndt]

* 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.


> [...]