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

2×2,861 Posts
Default

Quote:
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 offline   Reply With Quote