## Exercises7.5Additional Exercises: Primality and Factoring

In the RSA cryptosystem it is important to be able to find large prime numbers easily. Also, this cryptosystem is not secure if we can factor a composite number that is the product of two large primes. The solutions to both of these problems are quite easy. To find out if a number $$n$$ is prime or to factor $$n\text{,}$$ we can use trial division. We simply divide $$n$$ by $$d = 2, 3, \ldots, \sqrt{n}\text{.}$$ Either a factorization will be obtained, or $$n$$ is prime if no $$d$$ divides $$n\text{.}$$ The problem is that such a computation is prohibitively time-consuming if $$n$$ is very large.

### 1.

A better algorithm for factoring odd positive integers is Fermat's factorization algorithm.

1. Let $$n= ab$$ be an odd composite number. Prove that $$n$$ can be written as the difference of two perfect squares:

\begin{equation*} n = x^2 - y^2 = (x - y)(x + y)\text{.} \end{equation*}

Consequently, a positive odd integer can be factored exactly when we can find integers $$x$$ and $$y$$ such that $$n = x^2 - y^2\text{.}$$

2. Write a program to implement the following factorization algorithm based on the observation in part (a). The expression ceiling(sqrt(n)) means the smallest integer greater than or equal to the square root of $$n\text{.}$$ Write another program to do factorization using trial division and compare the speed of the two algorithms. Which algorithm is faster and why?

x := ceiling(sqrt(n))
y := 1

1 : while x^2 - y^2 > n do
y := y + 1

if x^2 - y^2 < n then
x := x + 1
y := 1
goto 1
else if x^2 - y^2 = 0 then
a := x - y
b := x + y
write n = a * b


### 2.Primality Testing.

Recall Fermat's Little Theorem from ChapterĀ 6. Let $$p$$ be prime with $$\gcd(a, p) = 1\text{.}$$ Then $$a^{p-1} \equiv 1 \pmod{p}\text{.}$$ We can use Fermat's Little Theorem as a screening test for primes. For example, $$15$$ cannot be prime since

\begin{equation*} 2^{15-1} \equiv 2^{14} \equiv 4 \pmod{15}\text{.} \end{equation*}

However, $$17$$ is a potential prime since

\begin{equation*} 2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}\text{.} \end{equation*}

We say that an odd composite number $$n$$ is a pseudoprime if

\begin{equation*} 2^{n-1} \equiv 1 \pmod{n}\text{.} \end{equation*}

Which of the following numbers are primes and which are pseudoprimes?

1. $$\displaystyle 342$$

2. $$\displaystyle 811$$

3. 601

4. $$\displaystyle 561$$

5. $$\displaystyle 771$$

6. $$\displaystyle 631$$

### 3.

Let $$n$$ be an odd composite number and $$b$$ be a positive integer such that $$\gcd(b, n) = 1\text{.}$$ If $$b^{n-1} \equiv 1 \pmod{n}\text{,}$$ then $$n$$ is a pseudoprime base $$b\text{.}$$ Show that $$341$$ is a pseudoprime base $$2$$ but not a pseudoprime base $$3\text{.}$$

### 4.

Write a program to determine all primes less than $$2000$$ using trial division. Write a second program that will determine all numbers less than $$2000$$ that are either primes or pseudoprimes. Compare the speed of the two programs. How many pseudoprimes are there below $$2000\text{?}$$

There exist composite numbers that are pseudoprimes for all bases to which they are relatively prime. These numbers are called Carmichael numbers. The first Carmichael number is $$561 = 3 \cdot 11 \cdot 17\text{.}$$ In 1992, Alford, Granville, and Pomerance proved that there are an infinite number of Carmichael numbers [4]. However, Carmichael numbers are very rare. There are only 2163 Carmichael numbers less than $$25 \times 10^9\text{.}$$ For more sophisticated primality tests, see [1], [6], or [7].