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

[Georgi Guninski]

On Mon, Jun 14, 2010 at 04:15:39PM +0200, Joerg Arndt 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.
> 
>


Are you sure your arguments apply for million digits numbers ?

The idea is that the exponentiation while O(log(n)) may be considerably slower than finding a relatively small factor (it it exists).

Can't find a better reference at the moment:
http://annapurna.dsg.cs.tcd.ie/www.teamprimerib.com/faq/gimps.FAQ.php
Frequently Asked Questions -- GIMPS enthusiasts

Trial Factoring (aka TF or Factoring) is a relatively short computation whose goal is to eliminate Mersenne candidates in a couple of days instead of a couple of weeks. Many Mersenne candidates are multiples of relatively small primes. Trial Factoring discovers if there is such a number. If it is, the more expensive Lucas-Lehmer test isn't needed. Trial Factoring is also a nice way to begin with GIMPS as the work unit ends quicker than other tests, especially for AMD owners.