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 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 N1 or N+1 is known(and further extensions to partial factorization)