mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-04-22, 05:08   #1
1260
 
Feb 2003

2016 Posts
Question What qualifies for record-prime status?

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?
1260 is offline   Reply With Quote
Old 2004-04-22, 08:43   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

100111011111102 Posts
Default

Quote:
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
xilman is online now   Reply With Quote
Old 2004-04-23, 05:04   #3
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

34 Posts
Default

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.
Cyclamen Persicum is offline   Reply With Quote
Old 2004-04-23, 08:58   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

235768 Posts
Default

Quote:
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
xilman is online now   Reply With Quote
Old 2004-04-23, 12:47   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
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]
R.D. Silverman is offline   Reply With Quote
Old 2004-04-24, 10:29   #6
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

10100012 Posts
Default

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
Cyclamen Persicum is offline   Reply With Quote
Old 2004-04-24, 11:10   #7
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

3·73 Posts
Default

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)
wpolly is offline   Reply With Quote
Old 2004-04-24, 18:00   #8
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

34 Posts
Default

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.
Cyclamen Persicum is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
For the amusement of the record prime hunters a1call Miscellaneous Math 11 2017-02-05 07:19
M7508981 has at least 12 prime factors(new factor # record) pdazzl Factoring 261 2015-11-09 15:00
Another record probable prime found! philmoore Five or Bust - The Dual Sierpinski Problem 15 2009-02-08 19:43
Record probable prime found! philmoore Five or Bust - The Dual Sierpinski Problem 18 2009-01-28 19:47
Nicely done PrimeGrid - Record Woodall Prime axn Prime Cullen Prime 7 2007-09-03 08:48

All times are UTC. The time now is 09:57.

Wed Oct 21 09:57:59 UTC 2020 up 41 days, 7:08, 0 users, load averages: 1.94, 1.68, 1.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.