Prime Numbers And Primality Testing |

Written by Mike James | ||||

Thursday, 27 June 2019 | ||||

Page 3 of 3
## Pick a prime, any prime…To return to primality testing. You might think that the simplest way to create a randomized test that n is prime is to simply pick random values between 2 and The more you pick and fail to find a divisor the more certain you are that Any number which passes a randomized test with a high probability is referred to as a “pseudo-prime”. Currently one of the best known and most used test is Rabin’s Strong Pseudoprimality test and it’s interesting enough to explain in more detail. If the number we want to test is n-1=2sd where Next we pick an xd, x2d, x4d, x8d, … xn-1 (mod n) all calculated modulo Calculating modulo Once you have the sequence of values – called a “Miller-Rabin sequence” – you can be sure that if How does this help with a randomized primality test? Simple, just pick a value of The reason why this is such a good test is that if So if you pick one value at random and it gives a sequence that ends in a 1 the probability is one in four that it is really a composite non-prime. Pick 2 and the probability goes down to one sixteenth. If you continue picking M numbers that give a sequence that ends in 1, this means that the probability that you have a non-prime is ¼ For example, if you get sequences that end in 1 with 100 random values then the probability that you have a non-prime number is ¼ Such is the strange reasoning behind randomized testing for primes, and many other randomized algorithms. They never produce certainty but what is the practical difference between a probability of 1/10 There is more chance of a machine malfunction giving you the wrong answer computing a certain proof of primality than the Strong Pseudoprimality test failing! ## Certainty restored?So if knowing that a number is probably a prime is almost as good as knowing that it certainly is what’s the fuss about? There is still the philosophical point that a mathematical proof reveals a deeper truth than some random chance that something is true. What is more surprising is that the proof is so very simple and that it has remained undiscovered for so long. The problem also seems, on the face of it, to be an NP problem. That is the brute force way of testing a prime takes exponential time but if you give me a factor I can check that the number isn't prime with a single division. All NP problems are difficult to compute but easy to check. Also notice that proving a number to be a prime or not a prime doesn't actually help with the factoring problem. If you know a number is prime then it doesn't have factors but if you prove the number to be non-prime you still don't know what its factors are. Now consider what this means for the rest of the foundation of our cryptographic security. It is not that we can test primes fast that is important for the cryptography in general. It is more that something that we thought was difficult turns out to be easy. We assume that because something is difficult and because mathematicians have been working on the problem for years, centuries even, that the problem must really be difficult, intrinsically difficult. This is the assumption behind the factoring problem that many code systems rely on. Suppose now that the next problem Agrawal, Kayal, and Saxena, or some similar group, turn their attention to is factoring. Perhaps what was always assumed to be difficult will turn out not be if a sufficiently fresh approach is taken to the problem. Perhaps this has already happened. Answer to the factor problem:
First Draft |
||||

Last Updated ( Thursday, 27 June 2019 ) |