## Math 418

### Index of Hand-outs

 Date No. Title 11 Sep 17 01 Course Information * Public Key Cryptography (2pp.) * The Dancing Men 13 Sep 17 * The Big-O Notation * The Number of Digits * Bit Operations * Polynomial Time Algorithms 14 Sep 17 * The Division Algorithm * The Euclidean Algorithm * The Euclidean Algorithm II 18 Sep 17 * Implementing the gcd in Maple (2pp) * The Euclidean Algorithm (Maple pgm - 2pp) * The Extended Euclidean Algorithm * The Extended Euclidean Algorithm: Examples 1 and 2 (2pp.) 20 Sep 11 * MAPLE homework instructions * MAPLE hints * Basic MAPLE Commands (4pp.) * The Extended Euclidean Algorithm (Matrix Method) (2pp.) * The Euclidean Algorithm (Maple Program - 2pp.) * Solving mx + ny = c 21 Sep 17 * Modular Arithmetic * Solving mx + ny = c and ax = b (mod m) 25 Sep 17 * The Euler phi-function (2pp.) 27 Sep 17 * The Chinese Remainder Theorem (4pp.) 28 Sep 17 * The Binary Power Method (3pp.) * Review of time estimates for algorithms 02 Oct 17 * The Definition of Cryptosystems * Classical Cryptosystems (2pp.) 04 Oct 17 * Tasks for Public Key Cryptography * The RSA Method (4pp.) 05 Oct 17 * Design Features of RSA Keys * The RSA Challenge (2pp.) * The Discrete Log Problem (2pp.) 11 Oct 17 * The Order of a Group Element (2pp.) 12 Oct 17 * Orders of elements mod 11 16 Oct 17 * The existence of generators * DL-Cryptosystems * History of DL-Cryptosystems 18 Oct 17 * DL-Cryptosystems: Examples (5pp.) 19 Oct 17 * Hashfunctions 23 Oct 17 * The Log Table Method (2pp.) * Realistic Time/Space Estimates (2pp.) * The SPH Method 25 Oct 17 * The SPH Method: An Example (Maple - 2pp.) * DL-Attacks and their consequences (3pp.) 26 Oct 17 * Generators of F_p (2pp.) 29 Oct 17 * Primality Tests * Pseudoprimes and the Fermat Test (3pp.) 01 Nov 17 * Subgroups and Lagrange's Theorem 02 Nov 17 * Quadratic Residues * Euler Pseudoprimes and the Euler Test (2pp,) 06 Nov 17 * Strong Pseudoprimes and the Miller-Rabin Test 08 Nov 17 * The Miller-Rabin Primality Test (2pp.) * Primality Tests: Overview (2pp.) * Elliptic Curves (2pp.) 09 Nov 17 * Elliptic Curves (Graphs) 13 Nov 17 * Complex Elliptic Curves (2pp.) * Torsion Points (2pp.) 15 Nov 17 * Elliptic Curves over Q (2pp.) * Comments and Hints for Term Project * Elliptic Curves over Finite Fields 20 Nov 17 * Subgroups of Z/NZ x Z/NZ * Elliptic Curve Cryptosystems (2pp.) * The Embedding of Plaintexts in E(F_p) 22 Nov 17 * Digital Signature (ECDSA) * Choosing E and P (2pp.) 23 Nov 17 * Pollard's p - 1 Method * Lenstra's Factorization Method (2pp.) 27 Nov 17 * Pocklington's Primality Test * The Goldwasser/Kilian EC Primality Test (2pp.) 29 Nov 17 * Schoof's Algorithm (Basic Ideas) (2pp.) 30 Nov 17 CM Elliptic Curves (2pp.) * Cornacchia's Algorithm (1918)