20180115, 22:09  #1 
"Luke Richards"
Jan 2018
Birmingham, UK
120_{16} Posts 
Proth and Riesel Primes
I may be missing something here, but why in the definition of Proth () and Reisel () is there the requirement that ?
There are primes which exist when so is it for the purposes of more efficient primality testing? 
20180115, 22:15  #2  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
1011011101110_{2} Posts 
Quote:
The tests that we use to prove them prime rely on these conditions. 

20180115, 22:26  #3 
"Luke Richards"
Jan 2018
Birmingham, UK
120_{16} Posts 
Yes, of course! I knew I was missing something obvious!
So if, for example, one wanted to check the primality of there's no *efficient* algorithm for so doing? (It is prime btw... It's 2541865828331) Last fiddled with by lukerichards on 20180115 at 22:26 
20180120, 12:25  #4  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·5·587 Posts 
Quote:


20180120, 12:46  #5  
"Luke Richards"
Jan 2018
Birmingham, UK
120_{16} Posts 
Quote:
N+1 = 635466457083 * 2 * 2 An algorithm exists for efficient primality testing? Could you point me in the direction of those algorithms? Also  my understanding is that there are various elements of number theory which help with primality testing when P can be written as E+1 or E1, (where E is an even number) but that this gets significantly trickier where the known representation of P is O+2 or O2 (where O is an odd composite number). Does anyone know, or is anyone able to point me in the direction of anything useful, which might help with primality testing O +/ 2 or help with understanding why this is difficult. I'm currently working on an algorithm which generates O, such that P = O + 2 and seems empirically to be more likely to be prime c.f. 2^{p}  1. To test primality I could find E = P + 1, but this feels inefficient. 

20180120, 13:30  #7  
"Luke Richards"
Jan 2018
Birmingham, UK
440_{8} Posts 
Quote:
In the extremely unlikely event that my general playing around ever discovers something new, I think a great amount of credit will have to be given to the GIMPS forum! 

20180120, 16:47  #8 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2^{2}·227 Posts 
BrillhartLehmerSelfridge (1975) show over 30 forms of n1, n+1, and hybrid factoring.
It doesn't help at all with n2 or n+2 other than to give the proofs behind lots of the n1/n+1 methods. These methods work quite well for small numbers (say, less than 40 digits) but suffer from scaling issues in general as once into the 100+ digit range it just takes too long for the partial factoring. It's still worth checking for easy cases. If your input is constructed then perhaps even large inputs have a known partial factorization for p1 and/or p+1. Remember that your proof relies on the factor primality as well so for nontrivial factors you get to recurse. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Proth primes  ET_  Proth Prime Search  9  20201002 07:11 
(NEW) Proth Primes Section  kar_bon  Riesel Prime Data Collecting (k*2^n1)  6  20101125 13:39 
Riesel primes  Primeinator  Information & Answers  12  20090719 23:30 
Proth Riesel Drag Racing  robert44444uk  Math  1  20050924 10:35 
some primes I found with Proth.exe last year  ixfd64  Lounge  1  20050907 23:42 