Why Do We Say “It is probably prime”? Surely it is, or it isn’t!

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]:

With this we test:

and where:

and the Jacobi symbol (also known as the Legendre symbol). Now if we try for a value of n=997 and a=3, we get [here]:

This is true, as 997 is a prime number. A value of 889 will show it not to be a prime number (as it fails the Euler test) [here]:

But if we try a Carmichael number of 2,465, it will be a positive result for a prime number: [here]:

And there you go. In theory, the Solovay-Strassen method has a failure rate of 50% with Carmichael numbers, so there’s a chance that we think a value is a prime number, and it is not. With the Rabin-Miller, this falls to a 25% failure rate. But, if we have a large space for our prime numbers, it is very unlikely we will hit a Carmichael number, but it is possible. And so we get the concept of “probably prime”.

An outline of the code is:

import sys
import libnum
a=2

n=561

def legendre_symbol(a, p):
# Returns 1 if a has a square root modulo p, -1 otherwise.

    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls

if (len(sys.argv)>1):
  n=int(sys.argv[1])

if (len(sys.argv)>2):
  a=int(sys.argv[2])

print ("a = ",a)
print ("n = ",n)

if (libnum.gcd(a,n)!=1):
	print ("a and n share a factor");
	sys.exit() 

val=pow(a,(n-1)//2, n)
val2=pow(a,n-1, n)
leg=legendre_symbol(a,n)

print (f"Euler test: {a}^({n-1}) (mod {n}) = {val2}")
print (f"Jacobi test: {a}^({(n-1)//2}) (mod {n}) =  {val}")
print (f"Legendre symbol =  {leg}")

if (val==(n-1)): val=-1

if (val==leg and val2==1):
	print (f"\n{n} is probably prime")
else:
	print (f"\n{n} is not prime")

A sample run with an unsafe value is:

a =  5
n =  162259276829213363391578010288127
Euler test: 5^(162259276829213363391578010288126) (mod 162259276829213363391578010288127) = 1
Jacobi test: 5^(81129638414606681695789005144063) (mod 162259276829213363391578010288127) =  162259276829213363391578010288126
Legendre symbol =  -1

162259276829213363391578010288127 is probably prime

So do Carmichael numbers stop at a given point? Well, no, they go on forever [here]:

Luckily, the Rabin-Miller method is better at detecting Carmichel numbers [here]:

For this the tests are:

Conclusions

And so there is a risk that the system will select a bad prime that isn’t one, and which would be considerably weaker in security terms. Luckily the chances of hitting a Carmichael number for a 2,048 bit prime number (as used in the Diffie-Hellman key exchange method) is extremely low.

Subscribe: https://billatnapier.medium.com/subscribe