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^21[/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^21[/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 N1 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 N1 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 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[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 (KonyaginPomerance) nor CHG (CoppersmithHowgraveGraham). :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 (KonyaginPomerance) nor CHG (CoppersmithHowgraveGraham). :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/197529130/S00255718197503846731/"]BrillhartLehmerSelfridge (1975)[/url] 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. 
All times are UTC. The time now is 08:32. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.