Abstract Algebra: Theory and Applications, Remixed!

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

   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 11.26 from Section 11.2. Let $p$ be prime with $gcd(a,p)=1\text{.}$ Then $a^{p-1}\equiv 1(\mathrm{mod}p)\text{.}$ We can use Fermat's Little Theorem as a screening test for primes. For example, $15$ cannot be prime since

However, $17$ is a potential prime since

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

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(\mathrm{mod}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].