Proth and Riesel Primes

lukerichards · 2018-01-15, 22:09

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?

henryzz · 2018-01-15, 22:15

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.

lukerichards · 2018-01-15, 22:26

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)

henryzz · 2018-01-20, 12:25

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)

lukerichards · 2018-01-20, 12:46

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. 2^p - 1. To test primality I could find E = P +- 1, but this feels inefficient.

paulunderwood · 2018-01-20, 13:09

A good starting place for you would be this page. It does not mention KP (Konyagin-Pomerance) nor CHG (Coppersmith-Howgrave-Graham).

lukerichards · 2018-01-20, 13:30

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!

danaj · 2018-01-20, 16:47

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.

2018-01-15, 22:09	#1
lukerichards "Luke Richards" Jan 2018 Birmingham, UK 2⁵·3² 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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Proth primes	ET_	Proth Prime Search	15	2022-06-26 03:27
(NEW) Proth Primes Section	kar_bon	Riesel Prime Data Collecting (k*2^n-1)	6	2010-11-25 13:39
Riesel primes	Primeinator	Information & Answers	12	2009-07-19 23:30
Proth Riesel Drag Racing	robert44444uk	Math	1	2005-09-24 10:35
some primes I found with Proth.exe last year	ixfd64	Lounge	1	2005-09-07 23:42

2018-01-20, 13:09	#6
paulunderwood Sep 2002 Database er0rr 4,549 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, 16:47	#8
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 910₁₀ 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.