TMA4162 Computational algebra


3/2: Please note that the projects are obligatory and important, but they will not cover the entire curriculum for the written exam.



Teaching assistant:


  • Thursday 0815-1000, KJL5.
  • Friday 1015-1200, B1.

Exercise class:

  • Thursday 1415-1600, B1.

Office hours:

  • TBA, room 848 in SBII.

The lectures will be in-person only.

Reference group



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!).


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 TopicNotes
2 Introduction to algorithms and their analysis. Algorithms for arithmetic. Exponentiation. Elliptic curvesHAC 2.3, 2.4.2, 4.2.1; demo; HAC 14.6.1; Gj DH-6, PMC 2.5
3 Elliptic curvesGj DH-6, PMC 2.5; HAC 2.4
4 Chinese Remainder Theorem. LatticesReferences in Project 2; PMC 3.5, Gj PKE-6
5 LatticesPMC 3.5, Gj PKE-6, Galbraith 16
6 Lattice algorithmsPMC 3.5, 3.7; Gj PKE-6, 8; Galbraith 17-18
7 Lattice algorithmsPMC 3.5, 3.7; Gj PKE-6, 8; Galbraith 17-18
8 No lectures
9 FactoringPMC 3.4, 2.4; Gj PKE-5, Gj DH-5.3; Galbraith 15
10 Sieving methodsGalbraith 15
11 Sieving methodsGalbraith 15
12 Number fieldsMilne Intro, parts of 2
13 Number field sieveMilne parts of 2, parts of 3
14 Easter
15 Repetition
16 Repetition, trial exam


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 DeadlineNotes
0Getting startedN/ANo hand-in
1 Exponentiation 25/1Updated 9/1
2 Number-theoretic transform 8/2
3 Lattices 5/3Updated 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:


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.


Books and lecture notes:


2023-05-03, Kristian Gjøsteen