Why Do We Say “It is probably prime”? Surely it is, or it isn’t!
Prime numbers are at the core of your online security. Without them, an intruder could listen to your secret communications, or pretend to be a server that you connect to. They are at the core of our key exchange (with ECDH) and in digital signatures (such as ECDSA). And so we might generate a random prime number, such as for our key exchange method. But the result can tell if we have a composite number (a number that has factors, and thus not prime) and a “probable prime number”. For a random prime number generation, if we get a composite number, we would just keep adding “2”, until we found a probable prime number.
But surely we can do better than just “probable”. Well, no! There are pesky numbers known as Carmichael numbers, and where all the tests we have primality test will pass these numbers. The first few Carmichael numbers are: 561( 3x11x17), 1,105 (5x13x17), 1,729 (7x13x19) and 2,465 (5x17x29). The simplest test we have is Euler’s:
And, if we take a value of a=5, and where 5⁵⁶⁰ (mod 561), we will return a value of 1, and where it looks like the value is a prime number. Now we can improve this with the Solovay-Strassen method [here]:
