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.
Let $n= ab$ be an odd composite number. Prove that $n$ can be written as the difference of two perfect squares:
\n\\begin{equation*}\nn = x^2 - y^2 = (x - y)(x + y).\n\\end{equation*}\n
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{.}$
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))\ny := 1\n\n1 : while x^2 - y^2 > n do\n y := y + 1\n\nif x^2 - y^2 < n then\n x := x + 1\n y := 1\n goto 1\nelse if x^2 - y^2 = 0 then\n a := x - y\n b := x + y\n write n = a * b\n
2Primality 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
\n\\begin{equation*}\n2^{15-1} \\equiv 2^{14} \\equiv 4 \\pmod{15}.\n\\end{equation*}\n
However, 17 is a potential prime since
\n\\begin{equation*}\n2^{17-1} \\equiv 2^{16} \\equiv 1 \\pmod{17}.\n\\end{equation*}\n
We say that an odd composite number $n$ is a pseudoprime if
\n\\begin{equation*}\n2^{n-1} \\equiv 1 \\pmod{n}.\n\\end{equation*}\n
Which of the following numbers are primes and which are pseudoprimes?
342
811
601
561
771
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.
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?
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].