Number Theoretic Algorithms 2025/26

Number Theoretic Algorithms

Lectures and exercises:

   (16.2.) Course motivation: description of standard algorithms for factorization of composite numbers and related problems. 1. Relationship between RSA and factorization. Calculation of RSA public composit number decomposition using a private key.

   (23.2.) Factorization algorithm with an oracle for finding an RSA private key. 2. Pollard's rho method. Period and preperiod of sequences given by functions, Floyd's method for finding cycles.
   Practicals: Compatibility of polynomial functions. Period and preperiod of affine functions on Z_p, group of affine transformations on a line.

   (2.3.) Estimates of the complexity of algorithms of trial division. Pollard's rho method and Pollard-Floyd algorithm. Period and preperiod of a function given by x²