Proth and Riesel Primes
 

I may be missing something here, but why in the definition of Proth ([TEX]k\cdot2^n + 1[/TEX]) and Reisel ([TEX]k\cdot2^n - 1[/TEX]) is there the requirement that [TEX]k < 2^n[/TEX]?

There are primes which exist when [TEX]k > 2^n[/TEX] so is it for the purposes of more efficient primality testing?

[QUOTE=lukerichards;477616]I may be missing something here, but why in the definition of Proth ([TEX]k\cdot2^n + 1[/TEX]) and Reisel ([TEX]k\cdot2^n - 1[/TEX]) is there the requirement that [TEX]k < 2^n[/TEX]?

There are primes which exist when [TEX]k > 2^n[/TEX] so is it for the purposes of more efficient primality testing?[/QUOTE]

Otherwise all odd primes would fit both definitions.
The tests that we use to prove them prime rely on these conditions.

[QUOTE=henryzz;477617]Otherwise all odd primes would fit both definitions. [/QUOTE]

Yes, of course! I knew I was missing something obvious! :blush::blush::blush:

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

(It is prime btw... It's [URL="https://numbermatics.com/n/2541865828331/"]2541865828331[/URL])

[QUOTE=lukerichards;477619]Yes, of course! I knew I was missing something obvious! :blush::blush::blush:

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

(It is prime btw... It's [URL="https://numbermatics.com/n/2541865828331/"]2541865828331[/URL])[/QUOTE]

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)

[QUOTE=henryzz;477966]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)[/QUOTE]

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

A good starting place for you would be [URL="http://primes.utm.edu/prove/index.html"]this page[/URL]. It does not mention KP (Konyagin-Pomerance) nor CHG (Coppersmith-Howgrave-Graham). :smile:

[QUOTE=paulunderwood;477968]A good starting place for you would be [URL="http://primes.utm.edu/prove/index.html"]this page[/URL]. It does not mention KP (Konyagin-Pomerance) nor CHG (Coppersmith-Howgrave-Graham). :smile:[/QUOTE]

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!

[url="http://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/"]Brillhart-Lehmer-Selfridge (1975)[/url] 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.