Croatian

Algorithms in Number Theory

Elective course in graduate program Computer science and mathematics                             0+0   3+0
The goal of this course is to enable students to understand the role of number theory in modern cryptography and to derive, apply and implement algorithms for solving problems involving congruences, testing primality and factorization of large integers.

There are no formal prerequisites. It would be desirable that the students passed the course Number Theory from the undergraduate mathematics study programme.

Contents

Basic algorithms in number theory. Algorithms for multiplying large integers. Euclidean algorithm. Chinese remainder theorem. Continued fractions. Quadratic congruences. Squares and square roots. LLL algorithm.

Public key cryptography. Cryptosystems based on the problem of factorization. Cryptosystems based on the discrete logarithm problem. Other public key cryptosystems. Application of LLL-algorithm in cryptanalysis.

Testing and proving primality. Distribution of prime numbers. Pseudoprime numbers. Miller-Rabin, AKS and other primality tests.

Factorization methods. Pollard ρ-method. Pollard p-1 method. Continued fraction method. Quadratic sieve method.

Basic references

  1. A. Dujella, M. Maretic: Kriptografija, Element, Zagreb, 2007.

  2. A. Dujella: Teorija brojeva, Skolska knjiga, Zagreb, 1st edition 2019, 2nd edition 2024.

  3. A. Dujella: Number Theory, Skolska knjiga, Zagreb, 2021.

Additional references

  1. H. Cohen: A Course in Computational Algebraic Number Theory, Springer-Verlag, 1993.

  2. R. Crandall, C. Pomerance: Prime Numbers. A Computational Perspective, Springer-Verlag, 2001.

  3. A. Das: Computational Number Theory, CRC Press, 2013.

  4. N. Koblitz: A Course in Number Theory and Cryptography, Springer-Verlag, 1994.

  5. A. J. Menezes, P. C. Oorschot, S. A. Vanstone: Handbook of Applied Cryptography, CRC Press, 1996.

  6. D. R. Stinson: Cryptography. Theory and Practice, CRC Press, 2005.

Lecture notes
(in pdf format; in Croatian)

Examples in PARI/GP

Cryptography - Undergraduate course

Number Theory - Undergraduate course

Elliptic Curves in Cryptography - Undergraduate course

Algorithms for Elliptic Curves - Graduate course (2008/2009)

Number Theory in Cryptography - Graduate course (2003/2004)

Recommended readings in number theory

PARI/GP home page

PARI/GP in browser

Searching elliptic curves with high rank in PARI/GP (Vinko Petricevic)

SageMathCell

MAGMA Calculator

Andrej Dujella home page