Motivation§

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

Distribution of Primes§

Lemma 15.1

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$.