TMA4162 Computational algebra
News
3/2: Please note that the projects are obligatory and important, but they will not cover the entire curriculum for the written exam.
Teaching
Lecturer:
- Kristian Gjøsteen. SBII, room 848.
Teaching assistant:
Lectures:
Exercise class:
- Thursday 1415-1600, B1.
Office hours:
- TBA, room 848 in SBII.
The lectures will be in-person only.
Reference group
TBA
Curriculum
The curriculum is defined to be the material covered during the lectures and projects (including the suggested solutions for projects 1-3). 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. Algorithms for arithmetic. Exponentiation. Elliptic curves | HAC 2.3, 2.4.2, 4.2.1; demo; HAC 14.6.1; Gj DH-6, PMC 2.5 |
| 3 | Elliptic curves | Gj DH-6, PMC 2.5; HAC 2.4 |
| 4 | Chinese Remainder Theorem. Lattices | References in Project 2; PMC 3.5, Gj PKE-6 |
| 5 | Lattices | PMC 3.5, Gj PKE-6, Galbraith 16 |
| 6 | Lattice algorithms | PMC 3.5, 3.7; Gj PKE-6, 8; Galbraith 17-18 |
| 7 | Lattice algorithms | PMC 3.5, 3.7; Gj PKE-6, 8; Galbraith 17-18 |
| 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 | Sieving methods | Galbraith 15 |
| 12 | Number fields | Milne Intro, parts of 2 |
| 13 | Number field sieve | Milne parts of 2, parts of 3 |
| 14 | Easter | |
| 15 | Repetition | |
| 16 | Repetition, trial exam |
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.
| Number | Topic | Deadline | Notes |
|---|---|---|---|
| 0 | Getting started | N/A | No hand-in |
| 1 | Exponentiation | 25/1 | Updated 9/1 |
| 2 | Number-theoretic transform | 8/2 | |
| 3 | Lattices | 5/3 | Updated 17/2 |
| 4 | Factoring | 31/3 | if you really want to, you may hand in on 2/4 instead. |
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 has been posted to Blackboard.
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
- 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.)
Software: