TMA4162 Computational algebra
News
26/4: There will be no lecture on 30/4. Visiting hours before the exam will be 15/5 and 16/5, both days 1200-1500, in my office.
Teaching
Lecturer:
- Kristian Gjøsteen. SBII, room 848.
Teaching assistant:
Lectures:
Exercise class:
- Monday 1215-1400, R54.
The lectures will be in-person only.
Reference group
Everyone.
Curriculum
The curriculum is defined to be the material covered during the lectures and projects (including the suggested solutions for projects). The schedule below contains references to written materials that essentially cover the curriculum (and more!).
Schedule
This schedule will change. With respect to the resources below: HAC refers to the Handbook of Applied Cryptography, Gj refers to the lectures notes in cryptography and PMC refers to Practical Mathematical Cryptography, Milne refers to Algebraic Number Theory by J. S. Milne.
| Week | Topic | Notes |
|---|---|---|
| 2 | Introduction to algorithms and their analysis. Primes. Algorithms for arithmetic. Exponentiation. Elliptic curves | HAC 2.3, 2.4.2, 4.2.1; demo; HAC 14.6.1; Gj DH-3, DH-6; PMC 2.3, 2.5 |
| 3 | Elliptic curves | Gj DH-3, DH-6; PMC 2.3, 2.5; HAC 2.4 |
| 4 | Lattices | PMC 3.5; Gj PKE-6; Galbraith 16 |
| 5 | Lattice algorithms | PMC 3.5, 3.7; Gj PKE-6, 8; Galbraith 17-18 |
| 6 | Lattice algorithms | PMC 3.5, 3.7; Gj PKE-6, 8; Galbraith 17-18 |
| 7 | Chinese Remainder Theorem. Lattices | PMC 3.5; Gj PKE-6 |
| 8 | No lectures | |
| 9 | Factoring | PMC 3.4, 2.4; Gj PKE-5, Gj DH-5.3; Galbraith 15 |
| 10 | Sieving methods | Galbraith 15 |
| 11 | Number fields | Milne Intro, parts of 2 |
| 12 | Number field sieve | Milne parts of 2, parts of 3 |
| 13 | Easter | |
| 14 | Gröbner basis | IVA 1, 2 |
| 15 | Gröbner basis | IVA 1, 2 |
| 16 | Repetition, old exams | No lecture 19/4 |
| 17 | Repetition, old exams |
Projects
In order to do the exam, projects 1-4 must all be handed in and approved. If you run into difficulties, contact me as soon as possible.
Projects 1-4 should be handed in through Blackboard. You should submit a report (using LaTeX) and your source code, both as an appendix to the report and as source code files.
Note: Two of the projects shown below are from spring 2023. They will be different for spring 2024, though similar.
| Number | Topic | Deadline | Notes |
|---|---|---|---|
| 0 | Getting started | N/A | No hand-in |
| 1 | Exponentiation | 26/1 | |
| 2 | Primes | 9/2 | |
| 3 | Lattices | 1/3 | |
| 4 | Factoring | 22/3 | You may hand in 5/4, if you insist. |
Code examples and demos
- Storing the result of computations to avoid having to wait for a result that has not changed: pickle_demo.py
Exam
The exam will look like the projects, minus the programming. That is, in addition to the usual knowledge of relevant algebra, you will be expected to explain how algorithms work, prove that they work and analyse their resource usage.
- A trial exam from 2023 is available in Blackboard.
Any resit exam will almost certainly be an oral exam.
Resources
Books and lecture notes:
- Steven D. Galbraith. Mathematics of Public Key Cryptography. Cambridge University Press, 2012. https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html.
- Victor Shoup. A Computational Introduction to Number Theory and Algebra. Cambridge University Press, 2008. https://www.shoup.net/ntb/
- Kristian Gjøsteen. Lecture notes in TMA4160 Cryptography. https://wiki.math.ntnu.no/tma4160/notes, 2019.
- Kristian Gjøsteen. Practical Mathematical Cryptography. Chapman and Hall/CRC, 2022.
- Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. https://cacr.uwaterloo.ca/hac/.
- Henri Cohen. A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics (GTM, volume 138). Springer, 1993. https://link.springer.com/book/10.1007/978-3-662-02945-9
- The Development of the Number Field Sieve. Arjen K. Lenstra, Hendrik W. Lenstra (eds.). Springer, 1993. https://link.springer.com/book/10.1007/BFb0091534
- J. S. Milne. Algebraic Number Theory. https://www.jmilne.org/math/CourseNotes/ant.html (This text is much more advanced than what we did in the course, but it covers the material with good examples.)
- David A. Cox John Little Donal O'Shea. Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra. Fourth Edition. Springer, 2015. https://link.springer.com/book/10.1007/978-3-319-16721-3
Software: