# Integer factorization and discrete logarithm problems

Les cours du CIRM (2014)

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

## Access Full Article

top## Abstract

top## How to cite

topGaudry, 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- L. M. Adleman, M.-D. A. Huang, Primality testing and Abelian varieties over finite fields, 1512 (1992), Springer–Verlag Zbl0744.11065MR1176511
- Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P, Annals of mathematics (2004), 781-793 Zbl1071.11070MR2123939
- A. O. L. Atkin, D. J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030 Zbl1049.11137MR2031423
- A. O. L. Atkin, F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29-68 Zbl0792.11056MR1199989
- Shi Bai, Cyril Bouvier, Alexander Kruppa, Paul Zimmermann, Better Polynomials for GNFS
- 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
- C. Bouvier, P. Gaudry, L. Imbert, H. Jeljeli, E. Thomé, Discrete logarithms in GF(p) — 180 digits, (2014)
- 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
- 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
- Steven D Galbraith, Mathematics of public key cryptography, (2012), Cambridge University Press Zbl1238.94027MR2931758
- William F. Galway, Dissecting a sieve to cut its need for space, Algorithmic number theory 1838 (2000), 297-312, Springer Zbl1032.11059MR1850613
- 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
- GMP-ECM
- Daniel M Gordon, Discrete Logarithms in GF(P) Using the Number Field Sieve, SIAM Journal on Discrete Mathematics 6 (1993), 124-138 Zbl0772.11046MR1201995
- Antoine Joux, A New Index Calculus Algorithm with Complexity $L(1/4+o(1\left)\right)$ in Small Characteristic, Selected Areas in Cryptography - SAC 2013 8282 (2014), 355-379, Springer Zbl06488134MR3218492
- The development of the number field sieve, 1554 (1993), LenstraA. K.A. K. Zbl0777.00017
- H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. 126 (1987), 649-673 Zbl0629.10006MR916721
- H. W. Lenstra Jr., C. Pomerance, A Rigorous Time Bound for Factoring Integers, J. Amer. Math. Soc. 5 (1992), 483-516 Zbl0770.11057MR1137100
- V. Nechaev, Complexity of a determinate algorithm for the discrete logarithm, Mathematical Notes 55 (1994), 165-172 Zbl0831.11065MR1275323
- 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
- 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
- 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
- Oliver Schirokauer, Using number fields to compute logarithms in finite fields, Math. Comp. 69 (2000), 1267-1283 Zbl1042.11085MR1653978
- Oliver Schirokauer, Virtual logarithms, Journal of Algorithms 57 (2005), 140-147 Zbl1207.11124MR2177621
- V. Shoup, Lower bounds for discrete logarithms and related problems, Advances in Cryptology – EUROCRYPT ’97 1233 (1997), 256-266, Springer–Verlag MR1603068
- 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
- P. C. van Oorschot, M. J. Wiener, Parallel collision search with cryptanalytic applications, J. of Cryptology 12 (1999), 1-28 Zbl0992.94028MR1664774
- Paul Zimmermann, Bruce Dodson, 20 years of ECM, Algorithmic number theory 4076 (2006), 525-542, Springer Zbl1143.11358MR2282947

## NotesEmbed ?

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