Mersenne banner
no. 1
Integer factorization and discrete logarithm problems
Les cours du CIRM, Volume 4 (2014) no. 1, Talk 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.

Published online:
DOI: 10.5802/ccirm.21 
@article{CCIRM_2014__4_1_A2_0,
     author = {Pierrick Gaudry},
     title = {Integer factorization and discrete logarithm problems},
     journal = {Les cours du CIRM},
     note = {talk:2},
     publisher = {CIRM},
     volume = {4},
     number = {1},
     year = {2014},
     doi = {10.5802/ccirm.21},
     language = {en},
     url = {https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.21/}
}
TY  - JOUR
TI  - Integer factorization and discrete logarithm problems
JO  - Les cours du CIRM
N1  - talk:2
PY  - 2014
DA  - 2014///
VL  - 4
IS  - 1
PB  - CIRM
UR  - https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.21/
UR  - https://doi.org/10.5802/ccirm.21
DO  - 10.5802/ccirm.21
LA  - en
ID  - CCIRM_2014__4_1_A2_0
ER  - 
%0 Journal Article
%T Integer factorization and discrete logarithm problems
%J Les cours du CIRM
%Z talk:2
%D 2014
%V 4
%N 1
%I CIRM
%U https://doi.org/10.5802/ccirm.21
%R 10.5802/ccirm.21
%G en
%F CCIRM_2014__4_1_A2_0
Pierrick Gaudry. Integer factorization and discrete logarithm problems. Les cours du CIRM, Volume 4 (2014) no. 1, Talk no. 2, 20 p. doi : 10.5802/ccirm.21. https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.21/

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

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

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

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

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

[6] Razvan Barbulescu; Pierrick Gaudry; Antoine Joux; Emmanuel Thomé 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

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

[8] Jean-Charles Faugère; Ludovic Perret; Christophe Petit; Guénaël Renault 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 (2012), pp. 27-44

[9] Jean-Charles Faugère; Mohab Safey El Din; Pierre-Jean Spaenlehauer 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

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

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

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

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

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

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

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

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

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

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

[20] Daniel Panario; Xavier Gourdon; Philippe Flajolet 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

[21] Christophe Petit; Jean-Jacques Quisquater 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

[22] C. Pomerance Fast, Rigorous Factorization and Discrete Logarithm Algorithms, Discrete Algorithms and Complexity, Proceedings of the Japan–US Joint Seminar, June 4–6, 1986, Kyoto, Japan (Perspectives in Computing) (1987), pp. 119-143

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

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

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

[26] Emmanuel Thomé 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

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

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

Cited by Sources: