Introduction to Primality Test

A primality test is an algorithm that checks if a number is prime. Given an integer n, it returns n is prime or composite.

For small numbers, a simple approach would be using trial division, which tries to divide n by every integer up to $\sqrt{n}$. However, this kind of test becomes impractical when n contains hundreds of bits or more, which is common in fields like cryptography.

Primality Tests are broadly of two types: deterministic and probabilistic. Deterministic tests return a mathematically certain answer, whereas probabilistic tests use randomly chosen values to test whether a number behaves like a prime, as we will see later.

Probabilistic Primality Test

A probabilistic primality test works by looking for some defined evidence that a number is composite. If such evidence is found, the number is proved to be composite. If no evidence is found, the algorithm doesn’t guarantee the number is prime. Rather, it signifies that the number is probably prime. If we repeat the test with independently chosen random values, the probability of mistaking composite number for a prime gets extremely small.

Miller-Rabin Primality Test

Miller-Rabin Primality Test is a probabilistic type of primality test. It is based on a property that every odd prime must satisfy.

Choose an odd integer (n > 2). We can express n in the following form:

$$ n = a2^b+1 \qquad (a \text{ is odd}) \tag{1} $$

Let’s suppose n that we chose is actually prime. Now we choose random integer c such that

$$ c \in (\mathbb{Z}/n\mathbb{Z})^* $$

Here, $2^b$ is the largest power of 2 dividing n-1. If a was even, we could factor another 2 out of it, which would contradict $2^b$ as the largest power of 2 dividing n-1.

$c \in \mathbb{Z}/n\mathbb{Z}$ means that c is an integer considered modulo n. For example, $$ \mathbb{Z}/5\mathbb{Z} = \left\lbrace0,1,2,3,4\right\rbrace $$

$c \in (\mathbb{Z}/n\mathbb{Z})^*$ means that c should also be invertible modulo n i.e. $\gcd(c,n)=1$. As we are assuming n as prime, every nonzero residue modulo n is invertible, so

$$ (\mathbb{Z}/n\mathbb{Z})^* = \left\lbrace1,2,3,….,n-1\right\rbrace $$

Algorithm

The algorithm claims that if n is prime, at least one of the following must be true:

  • $$c^{a} \equiv 1 \quad (mod \quad n)$$
  • $$c^{a2^{i}} \equiv -1 \quad (mod \quad n)$$ $$ for \quad some \quad 0 \leq i < b. $$
Proof:

From Equation (1), we have,

$$ n - 1 = a2^b $$

From Fermat’s Little Theorem,

$$ c^{n-1} \equiv 1 \quad (mod \quad n) $$

Combining them, we get

$$ c^{a2^{b}} \equiv 1 \quad (mod \quad n) \tag{2} $$

Suppose,

$$ c^a\not\equiv1\pmod n $$

Since,

$$ c^{a2^b}\equiv1\pmod n $$

There must be a point while repeatedly squaring where the value becomes 1. i.e. For some $i\in{0,1,\ldots,b-1}$ , we must have

$$ c^{a2^i}\not\equiv1\pmod n \tag{3} $$

but

$$ c^{a2^{i+1}}\equiv1\pmod n \tag{4} $$

Now, let

$$ x=c^{a2^i} \tag{5} $$

Or,

$$ x^2 = c^{a2^{i+1}} \tag{6} $$

From Equation (4) and (6), we can write $$ x^2 \equiv1\pmod n $$

$$ Or, x^2-1 \equiv0\pmod n $$

$$ Or, (x-1)(x+1) \equiv0\pmod n \tag{7} $$

From Equation (3) and (5), we can write,

$$ x\not\equiv1\pmod n \tag{8} $$

Now From (7) and (8), we can see that $x^2 - 1$ is divisible by n however $x - 1$ isn’t divisible by n. So, by Euclid’s Lemma, n must divide $x+1$. Which implies,

$$ x\equiv-1\pmod n $$

$$ Or, c^{a2^i}\equiv-1\pmod n \tag{9} $$

Takeaway: For a number to be prime, either of the following case must be true:

  • it starts at 1 i.e. $c^a \equiv 1 \quad(mod \quad n)$ or
  • while repeatedly squaring, the value becomes -1 (mod n) before becoming 1 (mod n).

Witness for Compositeness

If we choose some c and neither of the condition for prime is satisfied, then n must be composite.

So, for a chosen value of c,

$$ c^a \not\equiv 1 \quad(mod \quad n) $$

and

$$ c^{a2^i} \not\equiv -1 \quad(mod \quad n) $$

For every $0 \leq i<b$.

Such a value of c is called a witness for compositeness of n.

However, satisfying one of these conditions does not necessarily prove that n is prime. Some composite numbers can satisfy Miller-Rabin condition for some choices of c. Such c is called a non-witness/strong liar.

Probabilistic Approach

If we repeat the test independently with different random bases, after k rounds the probability that every chosen base happens to be a non-witness/strong-liar is at most

$$ (1/2)^k $$

so the repetition gives very high confidence of prime if all the k rounds miss the compositeness.

Now, suppose n is an odd composite number that is not a perfect power. Let’s try to prove that if n is composite, then atleast half of the possible bases $c \in (Z/nZ)^*$ will prove n as composite. This will imply that if you randomly choose c, there is a good chance it is a witness for compositeness.

Proof:

For a prime number, if the very first value $x^a$ is not already 1, then somewhere before the final 1, one of these values must be -1.

So, we consider the equations

$$
x^a\equiv-1\pmod n,
$$

$$
x^{2a}\equiv-1\pmod n,
$$

$$
x^{4a}\equiv-1\pmod n,
$$

and so on, up to

$$
x^{a2^{b-1}}\equiv-1\pmod n.
$$

Let

$$
x^{a2^j}\equiv-1\pmod n
$$

be the equation with the largest value of j that has at least one solution in $(\mathbb Z/n\mathbb Z)^*.$ We consider every possible j because we wouldn’t know where -1 will appear beforehand.

Consider a set $G= \left\lbrace c \in(Z/nZ)^* : c^{a2^j} \equiv \pm1\right\rbrace$

We will prove three facts about G.

Fact 1: If some c is not a witness for the compositeness of n, then $c \in G$.

Let’s say c is a non-witness. Then it should satisfy Miller-Rabin condition, so either

$$
c^a\equiv1\pmod n
$$

or

$$
c^{a2^i}\equiv-1\pmod n
$$

for some

$$
i\in \left\lbrace0,1,\ldots,b-1\right\rbrace.
$$

For the first case,

$$
c^a\equiv1\pmod n.
$$

Raising both sides to $2^j$,

$$
c^{a2^j} = (c^a)^{2^j}
\equiv1\pmod n.
$$

Therefore,

$$
c\in G.
$$

For the second case,

$$
c^{a2^i}\equiv-1\pmod n.
$$

Since j was chosen as the largest index for which such an equation has a solution, we must have

$$
i\le j.
$$

Therefore, $$
c^{a2^j} = \left(c^{a2^i}\right)^{2^{j-i}}.
$$

Since,

$$
c^{a2^i}\equiv-1\pmod n,
$$

we obtain

$$
c^{a2^j}
\equiv
(-1)^{2^{j-i}}
\equiv\pm1\pmod n.
$$

Hence,

$$
c\in G.
$$

Therefore, $\boxed{\text{Non-witnesses}\subseteq G}$

Fact 2: G is a subgroup of $(Z/nZ)^*$. Take any

$$
c,d\in G.
$$

By the definition of `G,

$$
c^{a2^j}\equiv\pm1\pmod n
$$

and

$$
d^{a2^j}\equiv\pm1\pmod n.
$$

Then $$
(cd)^{a2^j} = c^{a2^j}d^{a2^j}
\equiv
(\pm1)(\pm1)
\equiv\pm1\pmod n.
$$

Therefore, $cd\in G$ (multiplication closure).

Also,

$$
(c^{-1})^{a2^j} = \left(c^{a2^j}\right)^{-1}
\equiv(\pm1)^{-1}
\equiv\pm1\pmod n.
$$

Hence, $c^{-1}\in G$ (inverse closure).

Also,

$$ 1^{a2^j} = 1 $$

Hence, the identity element is also in G.

Therefore, G is a subgroup of $(\mathbb Z/n\mathbb Z)^*$.

Fact 3: G is a proper subgroup of $(Z/nZ)^*$.

We must show that there is some element w of $(Z/nZ)^*$ that isn’t in G.

Choose a prime p that divides n, $$ n = p^hg, \qquad where \quad gcd(p^h,g)=1 $$

Because n is assumed not to be a perfect power, $g>1$.

By the definition of j, there exists some $x_0\in(\mathbb Z/n\mathbb Z)^*$ such that

$$
x_0^{a2^j}\equiv-1\pmod n. \tag{10} $$

Therefore, it is also true modulo $p^h$

$$
x_0^{a2^j}\equiv-1 \quad(mod \quad p^h). \tag{11}
$$

Now we construct an element w such that $w\equiv x_0\pmod{p^h}$ and $w\equiv1\pmod g$.

Since $\gcd(p^h,g)=1$, the Chinese Remainder Theorem guarantees that such a w exists modulo n.

So,

$$
w
\equiv
x_0
\pmod{p^h}. $$

$$ Or, \quad w^{a2^j}
\equiv
x_0^{a2^j}
\equiv-1\pmod{p^h}. \tag{12} $$

and,

$$ w
\equiv
1
\pmod{g}. $$

$$ Or, \quad w^{a2^j}\equiv1\pmod g. \tag{13} $$

From (12), we can see that $w^{a2^j}$ cannot be congruent to $1\pmod{p^h}.$ Similarly from (13), we can see that $w^{a2^j}$ cannot be congruent to $-1\pmod{g}.$

Hence,

$$
w^{a2^j}\not\equiv\pm1\pmod n.
$$

Therefore, $w\notin G.$

So, G is not the entire group $(Z/nZ)^*$.

Lagrange’s Theorem

We have proved that G is a proper subgroup of $(\mathbb Z/n\mathbb Z)^*$.

Let H = $(\mathbb Z/n\mathbb Z)^*$,

Lagrange’s Theorem tells us that $|G|$ must divide $|H|$. but $G \neq H$ So,

$$ |G| < |H| $$

Since $|G|$ must divide $|H|$, the largest it could possibly be is

$$ \frac{|H|}{2} $$

Therefore,

$$ |G| \leq \frac{|H|}{2} $$

We have from Fact 1, $\boxed{\text{Non-witnesses}\subseteq G}$. So,

$$ non-witnesses \leq |G| \leq \frac{|H|}{2} $$

Therefore, we can conclude that atleast the other half are witnesses:

$$ witnesses \geq \frac{1}{2}|H| $$

Hence, $Pr(random \quad c \quad is \quad witness \quad of \quad compositeness) \geq \frac{1}{2}$.

Conclusion

So using probabilistic primality test like Miller-Rabin, compositeness can be proved when a witness is found. We can also conclude that repeated successful rounds give increasingly high confidence that the number is prime.

thanks for reading. hope you enjoyed :D