Skip to main content

Exercises 7.5 Additional 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].