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 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.
(16.3.) Probability of success of the second version Pollard's (p-1)-method.
Two-phase version of the Pollard's (p-1) method for one large prime.
Congruences on rings ZN[x], the field extension of the field Fp of degree 2 and the idea of (p+1)-method.
(23.3.) Formulation and correctnes of (p+1)-algorithm.
4. Lenstra's elliptic-curve algorithm.
Partial addition on the set ZN2 for general N and the group Ea,b(Zp) for a prime number p.
Collision search when computing the operation on Ea,b(ZN).
Practicals: If the collision-search algorithm over ZN doesn't find a proper divisor, then
\pip(A+B) = \pip(A) +\pip(B) for each p|N.
Operations on the groups Ea,b(Zp) for a prime p.
(30.3.) Relations between powers of an element of Ea,b(ZN) and the group power of the proejction in Ea,b(ZN) for a prime divisor p of N. Lenstra's ECM algorithm.
Practicals: Calculation and finding colisions of addition in ZN2.
(13.4.) Parallel inversion algorithm for ECM. 5. Roots modulo n. The Pohlig-Hellman reduction and idea of the Tonelli-Shanks algorithm for computing the square root modulo an odd prime.
(20.4.) Correctness and time complexity of Tonelli-Shanks algorithm.
Finding roots of polynomials modulo an odd prime and square roots modulo a power of a prime using Hensel's lifting.
Practicals: Square root calculation modulo a prime number using the Tonelli-Shanks algorithm. Finding roots of quadratic and general polynomials modulo a prime number.
(27.4.) Square root calculation modulo a composite number.
An attack on RSA using a deterministic algorithm for finding square roots modulo the product of two distinct primes.
6.Dixon's faktorization and CFRAC. Basis of faktorization and smooth relations. Scheme of Dixon's faktorization.
(4.5.) Calculation of the linear phase of Dixon’s factorization. Continued fractions and convergent fractions, an algorithm for calculating the continued fraction expansion of a square root.
Practicals: Calculation of the continued fraction of a square root. Finding the value of a periodic continued fraction. Description of the set of bad solutions of the linear phase of Dixon’s factorization.
(11.5.) Generating relations and formulation of the CFRAC algorithm.
7. Quadratic sieve. Finding smooth relations using sieving, a simple version.
Practicals: Bad solutions in linear phase of Dixon’s factorization form a subspace.
(18.5.) Sieving higher powers, and finding partial relations. 8. Discrete logarithm. The discrete logarithm problem. The Pohlig-Hellman reduction, the baby-steps algorithm, and the giant-steps algorithm. Factorization using an oracle solving the generalized discrete logarithm problem in the group ZN*.
Practicals: Structure of involutions in the group ZN*, properties of the subgroup K and searching of proper divizor of N.