Integer factorization and discrete logarithm problems

Gaudry, Pierrick

Journées Nationales de Calcul Formel. 3 – 7 Novembre 2014, Les cours du CIRM, no. 1 (2014), Exposé no. 2, 20 p.

These are notes for a lecture given at CIRM in 2014, for the “Journées Nationales du Calcul Formel”. We explain the basic algorithms based on combining congruences for solving the integer factorization and the discrete logarithm problems. We highlight two particular situations where the interaction with symbolic computation is visible: the use of Gröbner basis in Joux’s algorithm for discrete logarithm in finite field of small characteristic, and the exact sparse linear algebra tools that occur in the Number Field Sieve algorithm for discrete logarithm in large characteristic.

[1] Adleman, L. M.; Huang, M.-D. A. Primality testing and Abelian varieties over finite fields, Lecture Notes in Math., 1512, Springer–Verlag, 1992 | MR | Zbl

[2] Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin PRIMES is in P, Annals of mathematics (2004), pp. 781-793 | DOI | MR | Zbl

[3] Atkin, A. O. L.; Bernstein, D. J. Prime sieves using binary quadratic forms, Math. Comp., Volume 73 (2004) no. 246, pp. 1023-1030 | DOI | MR | Zbl

[4] Atkin, A. O. L.; Morain, F. Elliptic curves and primality proving, Math. Comp., Volume 61 (1993) no. 203, pp. 29-68 | DOI | MR | Zbl

[5] Bai, Shi; Bouvier, Cyril; Kruppa, Alexander; Zimmermann, Paul Better Polynomials for GNFS (Preprint available at http://www.loria.fr/~zimmerma/papers/sopt-20140905.pdf) | Zbl

[6] Barbulescu, Razvan; Gaudry, Pierrick; Joux, Antoine; Thomé, Emmanuel A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, Advances in Cryptology–EUROCRYPT 2014 (Lecture Notes in Comput. Sci.), Volume 8441, Springer, 2014, pp. 1-16 | DOI | MR | Zbl

[7] Bouvier, C.; Gaudry, P.; Imbert, L.; Jeljeli, H.; Thomé, E. Discrete logarithms in GF(p) — 180 digits, 2014 (Announcement available at the NMBRTHRY archives, item 004703)

[8] Faugère, Jean-Charles; Perret, Ludovic; Petit, Christophe; Renault, Guénaël Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields, Advances in Cryptology - EUROCRYPT 2012 (Lecture Notes in Comput. Sci.), Volume 7237, Springer (2012), pp. 27-44 | DOI | MR | Zbl

[9] Faugère, Jean-Charles; Safey El Din, Mohab; Spaenlehauer, Pierre-Jean Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): Algorithms and complexity, Journal of Symbolic Computation, Volume 46 (2011) no. 4, pp. 406-437 | DOI | Zbl

[10] Galbraith, Steven D Mathematics of public key cryptography, Cambridge University Press, 2012 | Zbl

[11] Galway, William F. Dissecting a sieve to cut its need for space, Algorithmic number theory (Lecture Notes in Comput. Sci.), Volume 1838, Springer (2000), pp. 297-312 | DOI | MR | Zbl

[12] Giorgi, Pascal; Lebreton, Romain Online order basis algorithm and its impact on the block Wiedemann algorithm, International Symposium on Symbolic and Algebraic Computation, ISSAC’14, ACM (2014), pp. 202-209 | Zbl

[13] GMP-ECM (Elliptic Curve Method for Integer Factorization, available at http://ecm.gforge.inria.fr/)

[14] Gordon, Daniel M Discrete Logarithms in GF(P) Using the Number Field Sieve, SIAM Journal on Discrete Mathematics, Volume 6 (1993) no. 1, pp. 124-138 | DOI | MR | Zbl

[15] Joux, Antoine A New Index Calculus Algorithm with Complexity $L(1/4+o(1\left)\right)$ in Small Characteristic, Selected Areas in Cryptography - SAC 2013 (Lecture Notes in Comput. Sci.), Volume 8282, Springer (2014), pp. 355-379 | DOI | MR | Zbl

[16] The development of the number field sieve, Lecture Notes in Math., 1554 (1993) | MR | Zbl

[17] Lenstra, Jr., H. W. Factoring integers with elliptic curves, Ann. of Math., Volume 126 (1987), pp. 649-673 | DOI | MR | Zbl

[18] Lenstra Jr., H. W.; Pomerance, C. A Rigorous Time Bound for Factoring Integers, J. Amer. Math. Soc., Volume 5 (1992) no. 3, pp. 483-516 | DOI | MR | Zbl

[19] Nechaev, V. Complexity of a determinate algorithm for the discrete logarithm, Mathematical Notes, Volume 55 (1994) no. 2, pp. 165-172 | DOI | MR | Zbl

[20] Panario, Daniel; Gourdon, Xavier; Flajolet, Philippe An analytic approach to smooth polynomials over finite fields, Algorithmic number theory – ANTS III (Lecture Notes in Comput. Sci.), Volume 1423, Springer, 1998, pp. 226-236 | DOI | MR | Zbl

[21] Petit, Christophe; Quisquater, Jean-Jacques On polynomial systems arising from a Weil descent, Advances in Cryptology–ASIACRYPT 2012 (Lecture Notes in Comput. Sci.), Volume 7658, Springer, 2012, pp. 451-466 | DOI | MR | Zbl

[22] Pomerance, C. Fast, Rigorous Factorization and Discrete Logarithm Algorithms, Discrete Algorithms and Complexity, Proceedings of the Japan–US Joint Seminar, June 4–6, 1986, Kyoto, Japan (Johnson, D. S.; Nishizeki, T.; Nozaki, A.; Wolf, H. S., eds.) (Perspectives in Computing), Academic Press, Orlando (1987), pp. 119-143 | Zbl

[23] Schirokauer, Oliver Using number fields to compute logarithms in finite fields, Math. Comp., Volume 69 (2000) no. 231, pp. 1267-1283 | DOI | MR | Zbl

[24] Schirokauer, Oliver Virtual logarithms, Journal of Algorithms, Volume 57 (2005) no. 2, pp. 140-147 | DOI | MR | Zbl

[25] Shoup, V. Lower bounds for discrete logarithms and related problems, Advances in Cryptology – EUROCRYPT ’97 (Fumy, W., ed.) (Lecture Notes in Comput. Sci.), Volume 1233, Springer–Verlag (1997), pp. 256-266 | DOI | MR

[26] Thomé, Emmanuel Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, Journal of Symbolic Computation, Volume 33 (2002) no. 5, pp. 757-775 | DOI | MR | Zbl

[27] van Oorschot, P. C.; Wiener, M. J. Parallel collision search with cryptanalytic applications, J. of Cryptology, Volume 12 (1999), pp. 1-28 | DOI | MR | Zbl

[28] Zimmermann, Paul; Dodson, Bruce 20 years of ECM, Algorithmic number theory (Lecture Notes in Comput. Sci.), Volume 4076, Springer, 2006, pp. 525-542 | DOI | MR | Zbl