 mersenneforum.org > Math What qualifies for record-prime status?
 Register FAQ Search Today's Posts Mark Forums Read 2004-04-22, 05:08 #1 1260   Feb 2003 25 Posts 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?   2004-04-22, 08:43   #2
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

101100011101102 Posts 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   2004-04-23, 05:04 #3 Cyclamen Persicum   Mar 2003 1218 Posts 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.   2004-04-23, 08:58   #4
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

261668 Posts 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   2004-04-23, 12:47   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101001001002 Posts 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]
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]   2004-04-24, 10:29 #6 Cyclamen Persicum   Mar 2003 34 Posts 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   2004-04-24, 11:10 #7 wpolly   Sep 2002 Vienna, Austria 21910 Posts 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)   2004-04-24, 18:00 #8 Cyclamen Persicum   Mar 2003 10100012 Posts 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.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 11 2017-02-05 07:19 pdazzl Factoring 261 2015-11-09 15:00 philmoore Five or Bust - The Dual Sierpinski Problem 15 2009-02-08 19:43 philmoore Five or Bust - The Dual Sierpinski Problem 18 2009-01-28 19:47 axn Prime Cullen Prime 7 2007-09-03 08:48

All times are UTC. The time now is 20:01.

Sat Jul 2 20:01:22 UTC 2022 up 79 days, 18:02, 1 user, load averages: 1.17, 1.14, 1.16