20000112: log means natural logarithm. Amount of work to verify a trial-division proof of primality. Amount of work to verify a trial-division proof of compositeness. Examples: 1729; 1089. Strategy to enumerate the primes up through L. Example for L=30. The Sieve of Eratosthenes for general L. How fast is the Sieve of Eratosthenes? Time roughly L/2+L/3+L/5+L/7+...+L/sqrt(L). Comparison to 1+1/4+1/9+1/16+... Comparison to 1+1/2+1/3+1/4+...; calculus approach. Mertens's theorem. Summary of time of Sieve of Eratosthenes.
20000114: Diagram of factorization methods, with rough summaries of speeds: trial division, Pollard's rho method, Pollard's p-1 method, the elliptic curve method, SQUFOF, the continued fraction method, the quadratic sieve, and the number field sieve. Diagram of primality testing methods: trial division, DOWNRUN methods, elliptic-curve primality proving, Jacobi-sum primality proving, probabilistic methods. Outline of course topics: primality, factorization, arithmetic.
20000119: Fermat's compositeness-proving method. Review of compositeness proof for 9. Notes on reduction mod 9. Questions about Fermat's method: How often does it succeed? How quickly can we compute 2^(n-1) mod n? First number where Fermat's method fails: 341. Computing 2^340 mod 11, mod 31, mod 341. Overall reliability of Fermat's method. Computing 2^(n-1) by repeated doubling. Analysis of number of digits written down. Better: Computing 2^(n-1) mod n by repeated doubling mod n. Analysis of number of digits written down. Much better: Computing 2^(n-1) mod n by repeated squaring. Example.
20000121: Multidigit arithmetic inside a computer. Homework assignment #1. Multiplication by repeated doubling. Time analysis of multiplication; inductive proof that number of doublings is small. Notes on how much more quickly we can multiply. Exponentiation by repeated squaring.
20000124: The general notion of an associative binary operation. Examples: integer addition; multiplication mod n. Repetition of an associative binary operation. General algorithm for fast repetition. Number of operations needed for fast repetition. Examples: number of additions needed for multiplication; number of multiplications mod n needed for exponentiation mod n. Total time to exponentiate mod n. Comparison to trial-division time. How to handle composites not proven composite by Fermat's method? Using other bases. Carmichael numbers. Many Carmichael numbers with large prime divisors. Existence of better compositeness-proving methods.
20000126: The square roots of 1 mod n, when n is an odd prime. Strengthening Fermat's theorem. Examples: n = 7, n = 13, n = 17. The base-b compositeness-proving method. Comparison of strength between this method and Fermat's method. What happens when b is chosen randomly. Selfridge's test. The Miller-Rabin test. Reliability of the Miller-Rabin test.
20000128: Definition of Fermat certificate. Definition of Selfridge certificate. Implications: factor implies nontrivial gcd, which implies Fermat certificate, which implies Selfridge certificate, which implies compositeness. Review of Selfridge's test and the Miller-Rabin test. The Miller-Bach test, assuming the Generalized Riemann Hypothesis. Adleman's test. Example for 10-digit numbers. Strategy to prove that one Miller-Rabin test is at least 50% reliable.
20000131: Homework assignment #2. Setup for proof of reliability: odd integer n, at least 3, not a power of a prime; the exponents (n-1)/2, (n-1)/4, (n-1)/8, etc.; the units mod n; the exponents where -1 has a root mod n; the largest exponent h; the group G of h'th roots of +-1 mod n. Example of setup for n=21. Construction of a unit c outside G, using the Chinese remainder theorem. Proof that c is a unit. Proof that cG is disjoint from G.
20000202: Review of setup. Example of construction of c for n=21; G versus cG. All non-certificates are inside G. Size of cG matches size of G, using the fact that c is a unit. Putting everything together to conclude that #non-certs is at most #units/2. Rephrasing proof algebraically: commutative rings, commutative groups, the ring Z/n, the group of units of Z/n, the subgroup G, Lagrange's theorem.
20000204: Definitions of 2-sprp, 2-spsp, b-spsp. What about prime powers? Newton's method in general. Newton's method to compute the square root of 314159. Definition of the order of b mod n. All b's for n = 10. The exponents giving 1's are the multiples of the order. All b's for n = 7. All b's for n = 8. Fact that (Z/n)^* is cyclic if n is prime.
20000207: Review of orders. Order of an arbitrary power in terms of order of the base. Why we like having (Z/n)^* cyclic: logarithms. Example of logarithms base 3 mod 7. The logarithm of a product; comparison to complex logarithms. Using logarithms to simplify equations. Proof that (Z/n)^* is cyclic if n is prime, using root-degree bound and order-lcm theorem.
20000209: The orders of 2 and 5 mod 31; deducing the order of 10 mod 31. The order of bc in general if the orders of b and c are coprime. Proof. Summary of facts about which orders exist for numbers mod n. Proof of the order-lcm theorem using factorizations of orders. Review of proof that (Z/n)^* is cyclic if n is prime. Outline of proof of the root-degree bound.
20000211: Definition of Z[x]. f(x)-f(r) divisible by x-r in Z[x], if f in Z[x] and r in Z. What happens if r is a root of f. Proof of the root-degree bound when n is prime. Conclusions. Statement of which (Z/n)^* are cyclic. Example: comparing orders for n=9 and n=3. Orders mod p^2 in general.
20000214: Constructing generators mod p^2 when p is prime. Comparison to Newton's method. Strategy for constructing generators mod p^3.
20000216: Proof that a generator mod p^2 is a generator mod p^3 when p is an odd prime. Back to certificates. Proof, using logs, that most numbers mod p^k are certificates for p^k. Goal of primality proving. Basic fact: If b has order n-1 mod n, then n is prime. Can prove that b has order e with not much computation, given prime factorization of e. Example: order 3 times 5. Example: order 314159 times 1000003.
20000218: The basic DOWNRUN theorem. Special case: Fermat numbers. Example: 65537 is prime. Example: 917519 is prime. DOWNRUN strategy to prove that a number n is prime, given primality of factors of n-1. Proof of the basic DOWNRUN theorem. Pepin's test for Fermat numbers, using quadratic reciprocity. How long it takes to check if 2^2^20+1 is prime. Which Fermat numbers are known to be prime; which Fermat numbers are known to be composite. Heuristic justification for the presumption that no other Fermat numbers are prime. Slight inaccuracy in the heuristic.
20000221: Questions about primality proving: How many generators are there mod n? How quickly can we factor n-1? If factorization is easy, how long does the whole method take? How long is the resulting proof? Are there better methods? Which numbers are easy to factor by trial division. Definition of smooth numbers and Psi. Heuristics for Psi. Conclusion that most numbers are difficult to factor by trial division.
20000223: Time analysis for primality proving, assuming that factorization is easy.
20000225: Pocklington's theorem. Proof of Pocklington's theorem. Fact that Pocklington's theorem applies whenever previous theorem does. Euclid's algorithm for gcd. Time taken by Euclid's algorithm. Example. Worst case: Fibonacci numbers. Overview of DOWNRUN improvements: 1/3; 3/10; n+1; combination.
20000228: Speed of the Jacobi-sum primality-proving algorithm. Speed of the elliptic-curve primality-proving algorithm. Introduction to cryptography. The Diffie-Hellman system.
20000301: A Wegman-Carter-type authentication system.
20000303: The RSA signature system.
20000306: Speed of trial division. Introduction to Pollard's rho method.
20000308: The tortiose-hare method of finding cycles. Speed of Pollard's rho method.
20000310: How Pollard's rho method was used to factor 2^256+1.
20000313: No class.
20000315: No class.
20000317: No class.
20000320: Fermat's factoring method.
20000322: Speeding up Fermat's factoring method.
20000324: Examples of continued fractions.
20000327: Proofs of basic properties of continued fractions.
20000329: Continued fractions for square roots.
20000331: Factoring integers with continued fractions. SQUFOF.
20000403: CFRAC. CFRAC versus SQUFOF for 100-digit numbers.
20000405: Asymptotics for CFRAC time; balancing recognition of smooth numbers with linear algebra. Speedups: how quickly we can recognize smooth numbers; how quickly we can do linear algebra.
20000407: Examples of factorization vectors. Wiedemann's method to compute the characteristic polynomial of a matrix.
20000410: Using the characteristic polynomial to find dependencies. Speed of Wiedemann's method; sparsity of factorization matrices.
20000412: The quadratic sieve.
20000414: Schroeppel's linear sieve. Computing discrete logarithms with the linear sieve. Table of conjectured speeds of CFRAC (original and improved), QS, LS, NFS.
20000417: Computer lab, SEL 2058.
20000419: The p-1 factorization method. Introduction to the p+1 factorization method.
20000421: The p+1 factorization method. The p+1 compositeness-proving method.
20000424: Some p+1 examples. The group operation on an elliptic curve. The elliptic-curve factorization method.
20000426: Planned: Fast Fourier transforms over Z/p. Fast integer multiplication. Fast integer division.
20000428: Using fast arithmetic to factor many smooth numbers.