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 Zp, 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 x2
(9.3.) 3. B-powersmooth numbers. Largest B-powersmooth elements. Outline of Pollard's (p-1) method. Time complexity and probability of success of the first version Pollard's (p-1) method.
Practicals: Calculation of B-powersmooth elements for specific small B, determination of their number and asymptotic behavior. Fermat numbers, proof of primality of F4 and compositeness of F5.