20040422, 05:08  #1 
Feb 2003
2^{5} Posts 
What qualifies for recordprime status?
What qualifies for recordprime status? What is meant by an explicit prime?
[a] If M(n) is the nth Mersenne prime, and n*2^k*M(n)1 is a 10million 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*s1 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? 
20040422, 08:43  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3^{3}·389 Posts 
Quote:
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 

20040423, 05:04  #3 
Mar 2003
1010001_{2} 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^[(N1)/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 veryvery rare. 
20040423, 08:58  #4  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10100100000111_{2} Posts 
Quote:
Paul 

20040423, 12:47  #5  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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 LucasLehmer test. In fact, it will take slightly more. LL 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^p1 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] 

20040424, 10:29  #6 
Mar 2003
1010001_{2} 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^(nm) + 1, so nm to be 32bit 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^p1 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 mersenneprime 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^n1, 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^p1, 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. Nowaday 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 nonmersenne, 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 
20040424, 11:10  #7 
Sep 2002
Vienna, Austria
3·73 Posts 
That reminds me about the N1 test where you have a large prime factor of N1.
I think we could start a project for 2k*M(p)+1 primes. (Hopefully we'll start from M30 or M31) 
20040424, 18:00  #8 
Mar 2003
3^{4} 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  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
For the amusement of the record prime hunters  a1call  Miscellaneous Math  11  20170205 07:19 
M7508981 has at least 12 prime factors(new factor # record)  pdazzl  Factoring  261  20151109 15:00 
Another record probable prime found!  philmoore  Five or Bust  The Dual Sierpinski Problem  15  20090208 19:43 
Record probable prime found!  philmoore  Five or Bust  The Dual Sierpinski Problem  18  20090128 19:47 
Nicely done PrimeGrid  Record Woodall Prime  axn  Prime Cullen Prime  7  20070903 08:48 