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

Joerg Arndt arndt at jjj.de
Mon Jun 14 18:47:06 CEST 2010

* Georgi Guninski <guninski at guninski.com> [Jun 14. 2010 18:03]:
> [...]

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

See me second paragraph above (drop the 'if' clause if you like).

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

IMHO more original sources to quote would be something
like  http://mersennewiki.org/index.php/Primality_test
or (more detailed)

So we agree on
1) little bit of trial factoring
   (use conditions of froms of those factors if known)
2) few rounds of Rabin-Miller
   (numbers surviving here are very likely prime)
3) Proof
   (a) for numbers of certain forms like
   Mersenne numbers there are tests that are
   very roughly as costly as one round of Rabin-Miller
   (b) for the general case proving primality of
   (say, a million digit number) may still be infeasible

(If the 'proof' is as cheap as Rabin-Miller we
may just skip Rabin-Miller).

If a proof isn't feasible use bounds (much better than the
'easy' "1/4 per round") given in (e.g.)

Ivan B. Damgård, Peter Landrock, Carl Pomerance: Average case error
estimates for the strong probable prime test, Mathematics of
Computation, vol.61, no.203, pp.177-194, (July-1993).


Ronald Joseph Burthe, Jr.: Further Investigations with the Strong
Probable Prime Test, Mathematics of Computation, vol.65, no.213,
pp.373-381, (January-1996).

More information about the SeqFan mailing list