# Math 418

01. Public Key Crptography (2pp)
02. The Dancing Men*
03. The Big-O Notation
04. The Number of Digits
05. Bit Operations
06. Polynomial Time Algorithms
07. The Division Algorithm
08. The Euclidean Algorithm
09. The Euclidean Algorithm II
10. Implementing the gcd in Maple (2pp)
10a. The Euclidean Algorithm (Maple pgm- 2pp)
11. The Extended Euclidean Algorithm
12. The Extended Euclidean Algorithm: Examples 1 and 2 (2pp)
13. The Extended Euclidean Algorithm (Matrix Method) (2pp.)
13a. The Extended Eulidean Algorithm (Maple Program) (2pp.)
14. Solving mx + ny = c
15. Modular Arithmetic
16. Solving mx + ny = c and ax = b (mod m) (2pp.)
17. The Euler phi-function (2pp.)
18. The Chinese Remainder Theorem (4pp.)
19. The Binary Power Algorithm (3pp.)
20. Review of time estimates for algorithms
21. Definition of Cryptosystems
22. Classical Cryptosystems (2pp.)
23. Tasks for Public Key Cryptography
24. The RSA Method (4pp)
25. Design Features of RSA Keys
26. The RSA Challenge (2pp.)
27. The Discrete Log Problem (2pp.)
28. The Order of a Group Element (2pp.)
29. Orders of Elements mod 11
30. The Existence of Generators
31. DL-Cryptosystems
32. History of DL-Cryptosystems*
33. DL-Cryptosystems: Examples (5pp.)
34. Hashfunctions
35. The Logtable Method (2pp.)
36. Realistic Time/Space Estimates (2pp.)
37. The SPH Method
37a. The SPH Method: An Example (Maple pgm - 2pp)
38. DL-Attacks and their consequences (3pp.)
39. Generators of F_p (2pp.)
40. Primality Tests
41. Pseudoprimes and the Fermat Test (3pp.)
42. Subgroups and Lagrange's Theorem
44. Euler pseudoprimes and the Euler test (2pp.)
45. Strong Pseudoprimes and the Miller-Rabin Test
46. The Miller-Rabin Primality Test (2pp.)
47. Primality tests: Overview (2pp.)
48. Elliptic Curves (2pp.)
49. Elliptic Curves - Graphs
50. Complex Elliptic Curves* (2pp.)
51. Torsion Points (2pp.)
52. Elliptic Curves over Q* (2pp.)
53. Elliptic Curves over Finite Fields
54. Subgroups of Z/NZ x Z/NZ
55. Elliptic Curve Cryptosystems (2pp.)
56. The Embedding of Plaintexts in E(F_p)
57. Digital Signature (ECDSA)
58. Choosing E and P (2pp.)
59. Pollard's p-1 method*
60. Lenstra's factorization method* (2pp.)
61. Pocklington's Primality Test*
62. The Goldwasser/Kilian Elliptic Curve Primality Test* (2pp.)
63. Schoof's Algorithm (Basic Ideas)* (2pp.)
64. CM elliptic Curves* (2pp.)
65. Cornacchia's Algorithm (1918)*

* not on the exam