mersenneforum.org > Math Proth and Riesel Primes
 Register FAQ Search Today's Posts Mark Forums Read

 2018-01-15, 22:09 #1 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 32·31 Posts Proth and Riesel Primes I may be missing something here, but why in the definition of Proth ($k\cdot2^n + 1$) and Reisel ($k\cdot2^n - 1$) is there the requirement that $k < 2^n$? There are primes which exist when $k > 2^n$ so is it for the purposes of more efficient primality testing?
2018-01-15, 22:15   #2
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT)

24·353 Posts

Quote:
 Originally Posted by lukerichards I may be missing something here, but why in the definition of Proth ($k\cdot2^n + 1$) and Reisel ($k\cdot2^n - 1$) is there the requirement that $k < 2^n$? There are primes which exist when $k > 2^n$ so is it for the purposes of more efficient primality testing?
Otherwise all odd primes would fit both definitions.
The tests that we use to prove them prime rely on these conditions.

2018-01-15, 22:26   #3
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

4278 Posts

Quote:
 Originally Posted by henryzz Otherwise all odd primes would fit both definitions.
Yes, of course! I knew I was missing something obvious!

So if, for example, one wanted to check the primality of $635466457083\cdot2^2-1$ there's no *efficient* algorithm for so doing?

(It is prime btw... It's 2541865828331)

Last fiddled with by lukerichards on 2018-01-15 at 22:26

2018-01-20, 12:25   #4
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT)

24·353 Posts

Quote:
 Originally Posted by lukerichards Yes, of course! I knew I was missing something obvious! So if, for example, one wanted to check the primality of $635466457083\cdot2^2-1$ there's no *efficient* algorithm for so doing? (It is prime btw... It's 2541865828331)
There isn't an algorithm that scales to numbers anything like the size of proth and riesel primes for general numbers although there are efficient algorithms if the full factorization of N-1 or N+1 is known(and further extensions to partial factorization)

2018-01-20, 12:46   #5
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

32×31 Posts

Quote:
 Originally Posted by henryzz There isn't an algorithm that scales to numbers anything like the size of proth and riesel primes for general numbers although there are efficient algorithms if the full factorization of N-1 or N+1 is known(and further extensions to partial factorization)
Interesting, thank you. So in this instance, because:

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 E-1, (where E is an even number) but that this gets significantly trickier where the known representation of P is O+2 or O-2 (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. 2p - 1. To test primality I could find E = P +- 1, but this feels inefficient.

 2018-01-20, 13:09 #6 paulunderwood     Sep 2002 Database er0rr 5·17·37 Posts A good starting place for you would be this page. It does not mention KP (Konyagin-Pomerance) nor CHG (Coppersmith-Howgrave-Graham).
2018-01-20, 13:30   #7
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

32·31 Posts

Quote:
 Originally Posted by paulunderwood A good starting place for you would be this page. It does not mention KP (Konyagin-Pomerance) nor CHG (Coppersmith-Howgrave-Graham).
Thank you!

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!

 2018-01-20, 16:47 #8 danaj   "Dana Jacobsen" Feb 2011 Portland, OR 90010 Posts Brillhart-Lehmer-Selfridge (1975) show over 30 forms of n-1, n+1, and hybrid factoring. It doesn't help at all with n-2 or n+2 other than to give the proofs behind lots of the n-1/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 p-1 and/or p+1. Remember that your proof relies on the factor primality as well so for non-trivial factors you get to recurse.

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ Proth Prime Search 8 2020-02-15 16:06 kar_bon Riesel Prime Data Collecting (k*2^n-1) 6 2010-11-25 13:39 Primeinator Information & Answers 12 2009-07-19 23:30 robert44444uk Math 1 2005-09-24 10:35 ixfd64 Lounge 1 2005-09-07 23:42

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

Tue Apr 7 01:58:22 UTC 2020 up 12 days, 23:31, 2 users, load averages: 2.62, 2.38, 2.30