26.4.17

Subsets of Safe Primes

The set of safe primes is composed of 2 mutually disjoint sets: the set of tough primes and the set of steady primes.


a list of the first few safe primes with tough primes in light blue background; the rest are steady primes


The main difference between these two sets lies in the structure of the exponentiation tables of their elements. For a tough prime p, I conjecture that:

Conjecture: If p is a prime of the form 8n+7, then the order of even powers of 2 mod p is p-1 and the order of odd powers of 2 mod p is (p-1)/2

In contrast, for a steady prime q I conjecture that:

Conjecture: If q is of the form 8n-1 such that 4n-1 and 8n-1 are also primes, then the order of all powers of 2 mod q is equal to (p-1)/2

Example: Let p = 11 and let q  = 7. Below are the corresponding exponentiation tables of Z11 and Z7.
The order of 2 mod 11 = 10, which is equal to the order of 8 mod 11, but the order of 4 mod 11 is half of that. Whereas in  Z7 the order of all powers of 2 is equal to 3.


Steady primes are the only primes where the order of all powers of 2 mod p is the same.  For all other primes the order of different powers of 2 is different.

On a slightly different note, as bad as safe primes may sound for cryptography, they are still not as bad as strong primes.