Thread: Proth and Riesel Primes View Single Post
2018-01-20, 12:25   #4
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

3×1,951 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)