Integer factorization and discrete logarithm problems

Pierrick Gaudry

Les cours du CIRM (2014)

  • Volume: 4, Issue: 1, page 1-20
  • ISSN: 2108-7164

Abstract

top
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.

How to cite

top

Gaudry, Pierrick. "Integer factorization and discrete logarithm problems." Les cours du CIRM 4.1 (2014): 1-20. <http://eudml.org/doc/275623>.

@article{Gaudry2014,
abstract = {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.},
author = {Gaudry, Pierrick},
journal = {Les cours du CIRM},
language = {eng},
number = {1},
pages = {1-20},
publisher = {CIRM},
title = {Integer factorization and discrete logarithm problems},
url = {http://eudml.org/doc/275623},
volume = {4},
year = {2014},
}

TY - JOUR
AU - Gaudry, Pierrick
TI - Integer factorization and discrete logarithm problems
JO - Les cours du CIRM
PY - 2014
PB - CIRM
VL - 4
IS - 1
SP - 1
EP - 20
AB - 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.
LA - eng
UR - http://eudml.org/doc/275623
ER -

References

top
  1. L. M. Adleman, M.-D. A. Huang, Primality testing and Abelian varieties over finite fields, 1512 (1992), Springer–Verlag Zbl0744.11065MR1176511
  2. Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P, Annals of mathematics (2004), 781-793 Zbl1071.11070MR2123939
  3. A. O. L. Atkin, D. J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030 Zbl1049.11137MR2031423
  4. A. O. L. Atkin, F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29-68 Zbl0792.11056MR1199989
  5. Shi Bai, Cyril Bouvier, Alexander Kruppa, Paul Zimmermann, Better Polynomials for GNFS 
  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 8441 (2014), 1-16, Springer Zbl1326.11080MR3213210
  7. C. Bouvier, P. Gaudry, L. Imbert, H. Jeljeli, E. Thomé, Discrete logarithms in GF(p) — 180 digits, (2014) 
  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 7237 (2012), 27-44, Springer Zbl1290.94070MR2972890
  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 46 (2011), 406-437 Zbl1226.13017MR2765378
  10. Steven D Galbraith, Mathematics of public key cryptography, (2012), Cambridge University Press Zbl1238.94027MR2931758
  11. William F. Galway, Dissecting a sieve to cut its need for space, Algorithmic number theory 1838 (2000), 297-312, Springer Zbl1032.11059MR1850613
  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), 202-209, ACM Zbl1325.68281MR3239927
  13. GMP-ECM 
  14. Daniel M Gordon, Discrete Logarithms in GF(P) Using the Number Field Sieve, SIAM Journal on Discrete Mathematics 6 (1993), 124-138 Zbl0772.11046MR1201995
  15. Antoine Joux, A New Index Calculus Algorithm with Complexity L ( 1 / 4 + o ( 1 ) ) in Small Characteristic, Selected Areas in Cryptography - SAC 2013 8282 (2014), 355-379, Springer Zbl06488134MR3218492
  16. The development of the number field sieve, 1554 (1993), LenstraA. K.A. K. Zbl0777.00017
  17. H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. 126 (1987), 649-673 Zbl0629.10006MR916721
  18. H. W. Lenstra Jr., C. Pomerance, A Rigorous Time Bound for Factoring Integers, J. Amer. Math. Soc. 5 (1992), 483-516 Zbl0770.11057MR1137100
  19. V. Nechaev, Complexity of a determinate algorithm for the discrete logarithm, Mathematical Notes 55 (1994), 165-172 Zbl0831.11065MR1275323
  20. Daniel Panario, Xavier Gourdon, Philippe Flajolet, An analytic approach to smooth polynomials over finite fields, Algorithmic number theory – ANTS III 1423 (1998), 226-236, Springer Zbl0908.11057MR1726074
  21. Christophe Petit, Jean-Jacques Quisquater, On polynomial systems arising from a Weil descent, Advances in Cryptology–ASIACRYPT 2012 7658 (2012), 451-466, Springer Zbl1292.94127MR3057514
  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 (1987), 119-143, Academic Press, Orlando Zbl0659.10003MR910929
  23. Oliver Schirokauer, Using number fields to compute logarithms in finite fields, Math. Comp. 69 (2000), 1267-1283 Zbl1042.11085MR1653978
  24. Oliver Schirokauer, Virtual logarithms, Journal of Algorithms 57 (2005), 140-147 Zbl1207.11124MR2177621
  25. V. Shoup, Lower bounds for discrete logarithms and related problems, Advances in Cryptology – EUROCRYPT ’97 1233 (1997), 256-266, Springer–Verlag MR1603068
  26. Emmanuel Thomé, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, Journal of Symbolic Computation 33 (2002), 757-775 Zbl1010.65024MR1919913
  27. P. C. van Oorschot, M. J. Wiener, Parallel collision search with cryptanalytic applications, J. of Cryptology 12 (1999), 1-28 Zbl0992.94028MR1664774
  28. Paul Zimmermann, Bruce Dodson, 20 years of ECM, Algorithmic number theory 4076 (2006), 525-542, Springer Zbl1143.11358MR2282947

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.