What qualifies for record-prime status?

[1260]

What qualifies for record-prime status? What is meant by an explicit prime?

[a] If M(n) is the n-th Mersenne prime, and n*2^k*M(n)-1 is a 10-million digit prime for some positive integers n and k, will it qualify as an explicit prime?

[b] If p,q,r,s are Generalized Fermat primes with 250 thousand digits or more, and 2*k*p*q*r*s-1 is prime for some positive integer k, will it qualify as an explicit prime?

[c] Suppose p,q,r,s in [b] are replaced with Mersenne primes, will it qualify?

[xilman]

Originally Posted by 1260

What qualifies for record-prime status? What is meant by an explicit prime?

[ a ] If M(n) is the n-th Mersenne prime, and n*2^k*M(n)-1 is a 10-million digit prime for some positive integers n and k, will it qualify as an explicit prime?

[ b ] If p,q,r,s are Generalized Fermat primes with 250 thousand digits or more, and 2*k*p*q*r*s-1 is prime for some positive integer k, will it qualify as an explicit prime?

[ c ] Suppose p,q,r,s in [ b ] are replaced with Mersenne primes, will it qualify?

The answer to all of these is the same.

If you can specify numerical values for all the symbols you use (n and k in the first; k,p,q,r and s in the second; the numerical index for each of the Mersenne primes in the third) and can provide a proof which can be independently checked that the quantity so specified is indeed prime, then you have an explicit prime.

Paul

[Cyclamen Persicum]

Why so complex?
You need a 10 million digit prime?
It is easy.
Let's N=k*2^33,000,000+1
Then choose small k and a for which a^[(N-1)/2]=-1 mod N
Thats all falks.
And it is easier than merrsennes due to ordinary 1/ln(N) probability raither than 1/N for Mersennes which are very-very rare.

[xilman]

Originally Posted by Cyclamen Persicum

Why so complex?
You need a 10 million digit prime?
It is easy.
Let's N=k*2^33,000,000+1
Then choose small k and a for which a^[(N-1)/2]=-1 mod N
Thats all falks.
And it is easier than merrsennes due to ordinary 1/ln(N) probability raither than 1/N for Mersennes which are very-very rare.

If it's that easy, you go for it!


Paul

[R.D. Silverman]

Originally Posted by Cyclamen Persicum

Why so complex?
You need a 10 million digit prime?
It is easy.
Let's N=k*2^33,000,000+1
Then choose small k and a for which a^[(N-1)/2]=-1 mod N
Thats all falks.
And it is easier than merrsennes due to ordinary 1/ln(N) probability raither than 1/N for Mersennes which are very-very rare.

What is it that compels people who are ignorant about a subject to make such
bold (and wrong) pronouncements?

(1) How do you propose to do this exponentiation? i.e. the multiplications
involved at each iteration? They will be slower than the irrational base FFT
used for Mp.
(2) The modular reductions will be somewhat slower than for Mp, even with
small k.
(3) It will take as many multiplications to do the exponentiation as are
required by a Lucas-Lehmer test. In fact, it will take slightly more. L-L is
all squarings. Modular exponentiation will involve not only squarings, but
some [approximately 1/2 log(p)] multiplications by a as well. [using the binary
method; I would want to use a more sophisticated sliding window to reduce
this]
(4) Your claim about probabilities is grossly wrong. The probability that
N = 2^p-1 will be prime for randomly chosen p is C/p for some constant C.
[the exact constant is still an open question]. It is NOT 1/N. It is C/lg N.

Testing your N, for each choice of k will take longer than an equivalent
sized Mp. And it is no more likely to be prime. [up to perhaps a small constant]

[Cyclamen Persicum]

Here you are, Bob Silverman!!!
Nice to hear you, an angry man, an implacable enemy of bullshit, a preceptor of erringers.
Are you one of a couple of tens so called GIMPS experts?

That is an interesting question - which is faster, Mersennes or Prothes?

(1) How do you propose to do this exponentiation? i.e. the multiplications
involved at each iteration? They will be slower than the irrational base FFT
used for Mp.

Technically Prothes may be four or five times slower than Mersennes, one can measure it exactly by comparing Prime95.exe and PRP.EXE. But in principle, IBWDT only *TWO* times faster than FFT, to say nothing about cutting a long number into chunks of various length, which is much slower than 16 or 8 bit padding using conventional memory access.

(2) The modular reductions will be somewhat slower than for Mp, even with
small k.

But not so slow as you think. In the case of classical reduction i.e. without WDT it is needed a lot of long shifts to cut mersennes into two chunks for summing them. But Proth Number k*2^n + 1 can be denormalized as (k*2^m)*2^(n-m) + 1, so n-m to be 32-bit aligned, hence no long shifts required.


(3) Modular exponentiation will involve not only squarings, but
some [approximately 1/2 log(p)] multiplications by a as well.

Look at a Proth Number attentively. Then look again, and then look thrice.
Its binary representation contains almost only zeros.


(4) Your claim about probabilities is grossly wrong. The probability that
N = 2^p-1 will be prime for randomly chosen p is C/p for some constant C.
[the exact constant is still an open question]. It is NOT 1/N. It is C/lg N.

I'll tell you more! The probability for N to be mersenne-prime even LESS than 1/N,
it is 1/N log N. The mersennes grow as log log N, more exactly as 2 log [log N / log 2].

Starting say from 2^30,000,000, you should search for new mersenne on the interval
[2^30,000,000; 2^(c*30,000,000)], where c is about exp(1/2). Experimantally c=1.606 upon the average. That is an unimaginable interval [2^30,000,000; 2^ 50,000,000] !!!
So I was right when told you about 1/N. One mersenne for 2^50,000,000 candidates!!!
And what you are talking about is a SIEVE.
1) We know, that mersennes have form 2^n-1, so we need not try every 2^50,000,000 integers. This remains us only 20,000,000 candidates.
2) We know, that mersennes have form 2^p-1, so we need not try every 20,000,000 exponents. This remains us only 1,000,000 candidates.
3) And so on...

As to Prothes, they also allow fast sieving since they may be fast calculated modulo certain divisors. Now-a-day the greatest Proth is 1.5 million digits long.

Testing your N, for each choice of k will take longer than an equivalent
sized Mp. And it is no more likely to be prime.

You are right here. It was a joke for poster who hopes to combine four 2,500,000 digit primes into a one 10 millions using many parameters. But the difference is not so fundamental. If one want to discover an unique prime of some smaller (not equivalent) size, or merely non-mersenne, Proth is a good choice. They are also good for twins records.
How many mersennes have you discovered?
And now I am giving the world an unique proth prime, none have seen it before
and never will rediscover it in future:
350C44EEBD264AA586D9FDAFDA7577EBh*2^898 + 1

[wpolly]

That reminds me about the N-1 test where you have a large prime factor of N-1.
I think we could start a project for 2k*M(p)+-1 primes. (Hopefully we'll start from M30 or M31)

[Cyclamen Persicum]

By the way, I have found an advantage of Prothes in sence of speed.
When performing destributed calculations, all 10,000,000 digit prothes will
require the same time to check. And in the case of mersennes the last candidate will require up to 1.5^2 more time to check than the first.