Primality: Fermat Test and Carmichael Numbers

17 Dec 2021

§ Motivation

We can use number theoretic approaches to hopefully find methods of determining primality faster than the naïve method.

§ Distribution of Primes

Prime Distribution

Let $\pi(x)$ be the number of primes less than or equal to $x$ , then

\pi(x) \sim \frac{x}{\log x},

in other words

\lim_{x\to\infty} \frac{\pi(x)}{\frac{x}{\log x}} = 1.

In the case of RSA, we want very large primes, using Lemma 15.1 we can estimate the number of primes in a given interval. Say that we wanted to know how many primes exist in the range from $10^{100}$ and $2\cdot10^{100}$ . Then, the number of primes we can expect in this interval is given by

\pi\left(2\cdot 10^{100}\right) -\pi\left(10^{100}\right) \sim \frac{10^{100}}{100\log{10}} \sim 10^{98}.

We see from the lemma that there exist many primes in this interval, so the odds of generating a random prime in this interval is not vanishingly small.

The following theorem is something that came up in class and I thought it was interesting.

Chebychev's Theorem (Bertrand's Postulate)

For any integer $n \gt 3$ , there exists at least one prime number $p$ in the interval

n \lt p \lt 2n - 2.

§ Fermat Primality Test

Fermat Primality Test

From the results of Fermat's Little Theorem, if $p$ prime then the following holds

a^{p-1} \equiv 1 \pmod{p}.

However, not all numbers satisfying this congruence are prime.

Carmichael Numbers

Composite numbers $n$ that satisfy the following congruence are called Carmichael numbers,

a^n \equiv a \pmod{n}.

It should be noted that there exists infinitely many Carmichael numbers, so we cannot rely solely on the Fermat primality test.

Carmichael Number

The smallest Carmichael number is $n=561$ , which is divisible by $3$ .

Using Magma, we can compute $a^{560} \pmod{561}$ using the command:

Modexp(a, 560, 561);

Where a is to be replaced by any integer.

When testing we will see that for any choice of a it will yield $1$ .