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

[Charles Greathouse]

> 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

In light of Neil's comment, the smallest untested number has 6.6
million bits.  Since #2 would take perhaps a year for a number that
size, I think the goal would be to find steps between #1 and #2.  #3
might be out of reach.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Mon, Jun 14, 2010 at 12:47 PM, Joerg Arndt <arndt at jjj.de> wrote:
> * 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)
> http://primes.utm.edu/prove/index.html
>
>
> 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).
>
> and
>
> Ronald Joseph Burthe, Jr.: Further Investigations with the Strong
> Probable Prime Test, Mathematics of Computation, vol.65, no.213,
> pp.373-381, (January-1996).
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>