AATA Additional Exercises: Primality and Factoring

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,

we can use trial division. We simply divide

n

d = 2, 3, \dots, \sqrt{n} .

Either a factorization will be obtained, or

n

is prime if no

d

divides

n .

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 = a b$ 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) .$

Consequently, a positive odd integer can be factored exactly when we can find integers $x$ and $y$ such that $n = x^{2} - y^{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 .$ 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 .

Then

a^{p - 1} \equiv 1 (\mod p) .

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 (\mod 15) .

🔗

However,

17

is a potential prime since

2^{17 - 1} \equiv 2^{16} \equiv 1 (\mod 17) .

🔗

We say that an odd composite number

n

is a pseudoprime if

2^{n - 1} \equiv 1 (\mod 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 .

b^{n - 1} \equiv 1 (\mod n),

then

n

is a pseudoprime base

b .

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 .

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

For more sophisticated primality tests, see [1], [6], or [7].

Prev Top Next