View Single Post
Old 2018-01-20, 12:46   #5
lukerichards's Avatar
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts

Originally Posted by henryzz View Post
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)
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 E-1, (where E is an even number) but that this gets significantly trickier where the known representation of P is O+2 or O-2 (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. 2p - 1. To test primality I could find E = P +- 1, but this feels inefficient.
lukerichards is offline   Reply With Quote