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:

   $$n = x^2 - y^2 = (x - y)(x + y)\text{.} \nonumber$$

   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

$$2^{15-1} \equiv 2^{14} \equiv 4 \pmod{15}\text{.} \nonumber$$

However, $17$ is a potential prime since

$$2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}\text{.} \nonumber$$

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

$$2^{n-1} \equiv 1 \pmod{n}\text{.} \nonumber$$

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