View Single Post
Old 2018-01-20, 12:25   #4
Just call me Henry
henryzz's Avatar
Sep 2007
Cambridge (GMT/BST)

2·5·587 Posts

Originally Posted by lukerichards View Post
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)
henryzz is online now   Reply With Quote