Math 115. Slides from Lecture of September 22

This handout contains the slides from the lecture of September 22 (with just one minor correction).

Techniques of Numerical Calculation

The main points of Section 2.3 (and related facts) for us are: A. “Polynomial time”

Definition. An algorithm runs in polynomial time if the time it takes is at most some polynomial function of the length of the input.

Examples:

• Addition: Adding an n-digit number and an m-digit number takes at most max{n, m} + 1 steps. This is polynomial time (actually, linear time).

• Multiplication: 2mn, so polynomial time (quadratic)

• Division (division algorithm): likewise

• Euclidean algorithm: The number of iterations is linear in the number of digits of the smaller of the two numbers. Each iteration takes time quadratic in the length of the input, so this takes place in polynomial time.

• Factoring a number n by trial division takes \sqrt{n} divisions. But:

n ≈ 3^{number of digits in n} .

So: exponential time. B. Computing a^{k} \underline{mod} m in polynomial time.

See the algorithm in the book. C. Primality testing: Given an integer m > 0 , is it prime?

Mostly this relies on Fermat’s Little Theorem: If there is an integer a such that 0 < a < m and a^{m−1} ≢ 1 (mod m) , then m is

not prime.

For each such a, this can be tested in polynomial time, by (B).

Definition. Let a ∈ ℤ with a > 1 . Then an integer m > 1 is a (weak) probable prime to the base a if a^{m−1} ≡ 1 (mod m) , and is a (weak) pseudoprime to the base a if in addition m is not prime.

Definition. A Carmichael number is a composite number m which is a weak pseudoprime to the base a for all integers a relatively prime to m.

The smallest Carmichael number is 561.

A better primality test.

Definition. Let m be an integer > 1 and write m − 1 = 2^{j}d with j ∈ ℕ and d odd. Let a ∈ ℤ with a > 1 . Then m is a strong probable prime to the base a if a^{m−1} ≡ 1 (mod m) , and the last element in the sequence

a^{d}, a^{2d}, a^{4d}, …, a^{2^{j}d} = a^{m−1}

which is ≢ 1 (mod m) (if any) is ≡ −1 (mod m) . (So if a^{d} ≡ 1 (mod m) then it is a strong probable prime.)

Strong pseudoprime to the base a is defined similarly.

D. Other tidbits:

• There is a test for primality that runs in polynomial time (AKS, 2002).

• Factoring a number is not known to have a polynomial-time algorithm.