L. M. Adlemanadl94-]-l and . Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography The function field sieve, 20th Annual Symposium on Foundations of Computer Science (FOCS '79) 1st Algorithmic Number Theory Symposium, pp.55-60, 1979.

J. [. Adleman and . Demarrais, A subexponential algorithm for discrete logarithms over all finite fields, Mathematics of Computation, vol.61, issue.203, pp.1-15, 1993.
DOI : 10.1090/S0025-5718-1993-1225541-3

J. [. Adleman, M. Demarrais, and . Huang, A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields
DOI : 10.1007/3-540-58691-1_39

M. [. Adleman and . Huang, Function Field Sieve Method for Discrete Logarithms over Finite Fields, Information and Computation, vol.151, issue.1-2, pp.5-16, 1999.
DOI : 10.1006/inco.1998.2761

J. [. Aho, J. D. Hopcroft, and . Ullman, The design and analysis of computer algorithms, 1974.

G. [. Beckerman and . Labahn, A Uniform Approach for the Fast Computation of Matrix-Type Pad?? Approximants, SIAM Journal on Matrix Analysis and Applications, vol.15, issue.3, pp.804-823, 1994.
DOI : 10.1137/S0895479892230031

E. [. Bender and . Canfield, An Approximate Probabilistic Model for Structured Gaussian Elimination, Journal of Algorithms, vol.31, issue.2, pp.271-290, 1999.
DOI : 10.1006/jagm.1999.1008

]. E. Ber68, . R. Berlekamp-[-ba80-]-r, B. D. Bitmead, and . Anderson, Algebraic coding theory Asymptotically fast solution of Toeplitz and related systems of linear equations, Linear Algebra Appl, vol.34, pp.103-116, 1968.

I. F. Blake, R. Fuji-hara, R. C. Mullin, and S. A. Vanstone, Computing Logarithms in Finite Fields of Characteristic Two, SIAM Journal on Algebraic Discrete Methods, vol.5, issue.2, pp.276-285, 1984.
DOI : 10.1137/0605029

G. R. Dans, D. Blakley, and . Chaum, Advances in Cryptology ? CRYPTO '84, Proc. Cryptology Workshop, pp.73-82, 1984.

H. [. Boender and . Te-riele, Factoring Integers with Large-Prime Variations of the Quadratic Sieve, Experimental Mathematics, vol.48, issue.4, pp.257-273, 1996.
DOI : 10.1080/10586458.1996.10504592

M. [. Boneh, . J. Franklin, and . Kilian, Identity-Based Encryption from the Weil Pairing, Proc. 21st Annual International Cryptology Conference, pp.213-229, 2001.
DOI : 10.1007/3-540-44647-8_13

]. D. But97 and . Butenhof, Programming with POSIX threads. Professional computing series

[. G. Cantor, H. Zassenhauscav00-]-s, W. Cavallar, . Bosma, A. S. Editeur et al., A new algorithm for factoring polynomials over finite fields Strategies in filtering in the number field sieve The Netherlands [Cav02] S. Cavallar. On the number field sieve factorization algorithm. Doctor's thesis Factorization of a 512-bit RSA modulus [Cer] Certicom corp. The Certicom ECC challenge Coppersmith. Fast evaluation of logarithms in fields of characteristic two, 4th Algorithmic Number Theory Symposium Preneel, ´ editeur, Advances in Cryptology ? EUROCRYPT Proc. International Conference on the Theory and Application of Cryptographic TechniquesCop93] D. Coppersmith. Solving linear equations over GFCop94] D. Coppersmith. Solving linear equations over GF(2) via block Wiedemann algorithmCOS86] D. Coppersmith, A. M. Odlyzko, et R. Schroeppel. Discrete logarithms in GF(p), pp.587-592, 1981.

]. R. Algorithmicacp01, C. Crandall, and . Pomerance, Prime numbers ? A Computational Perspective, pp.1-15, 1986.

D. Dans and . Chaum, Advances in Cryptology ? CRYPTO '83, Proc. Cryptology Workshop, pp.103-113, 1983.

T. Denny, B. Dodson, A. K. Lenstra, M. S. Manasse, and D. R. Stinson, On the factorization of RSA-120 Advances in Cryptology ? CRYPTO '93 New directions in cryptography, Proc. 13th Annual International Cryptology ConferenceDL95] B. Dodson et A. K. Lenstra. NFS with four large primes: an explosive experiment, pp.166-186644, 1976.

D. Dans and . Coppersmith, Advances in Cryptology ? CRYPTO '95, Proc. 15th Annual International Cryptology ConferenceDor87] J.-L. Dornstetter. On the equivalence between Berlekamp's and Euclid's algorithm, pp.372-385, 1995.

D. , R. Dupont, A. Engedem03, ]. R. Dupont, A. Enge et al., Practical non-interactive key distribution based on pairings A para??trepara??tre dans Proceedings WCC '03 Building curves with arbitrary mov defree over finite prime fields. Manuscrit en préparation A public-key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory IEEE Trans. Inform. Theory, issue.34, pp.33428-431, 1985.

. [. Elkenbracht-huizing, P. Enge, . Gaudryfkp89-]-p, D. E. Flajolet, E. B. Knuth et al., Elkenbracht-Huizing. Factoring integers with the number field sieve. Doctor's thesis A general framework for subexponential discrete logarithm algorithms The first cycles in an evolving graph The average case analysis of algorithms: counting and generating functions, FO90] P. Flajolet et A. M. Odlyzko. Random mapping statistics Advances in Cryptology ? EUROCRYPT '89 Proc. Eurocrypt '89, pp.231-25383, 1989.

. De-analytic-combinatorics-[-fs94-]-p, R. Flajolet, . [. Sedgewick, R. Flajolet, G. Sedgewick et al., The average case analysis of algorithms: saddle point asymptotics Rapport de recherche RR-2376, INRIA, 1994. chapitre 6 de Analytic combinatorics Analytic combinatorics ? symbolic combinatorics. Dis- poniblè a l'adresse http://algo.inria.fr/flajolet/Publications/books.html chapitres 1?3 de Analytic combinatorics, ` a para??trepara??tre. Version revue et augmentée de A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves Arithmetic and factorization of polynomials over F 2 (extended abstract) Modern Computer Algebra, vzGP01] J. von zur Gathen et D. Panario. Factoring polynomials over finite fields: A survey, pp.865-874, 1994.

J. Symbolic-computvzgs92, ]. J. Von-zur-gathen, and V. Shoup, Computing Frobenius maps and factoring polynomials, Gau00a] P. Gaudry. An algorithm for solving the discrete log problem on hyperelliptic curves, pp.3-17187, 1992.

B. Dans and . Preneel, Advances in Cryptology ? EUROCRYPT, Proc. International Conference on the Theory and Application of Cryptographic Techniques. [Gau00b] P. Gaudry. Algorithmique des courbes hyperelliptiques et applicationsàapplications`applicationsà la cryptologie. Thèse, ´ Ecole PolytechniqueGG01] P. Gaudry et N. Gürel. An extension of Kedlaya's algorithm to superelliptic curves, pp.19-34, 2000.

C. Dans, E. Boyd, . P. Dawson, F. Gaudry, E. N. Hess et al., Advances in Cryptology ? ASIACRYPT Constructive and destructive facets of Weil descent on elliptic curves, Proc. 7th International Conference on the Theory and Applications of Cryptology and Information Security, Dec. 9?13, pp.480-49419, 2001.

J. [. George, J. W. Gilbert, and . Liu, Graph theory and sparse matrix computation, Math. Appl, vol.56, 1993.
DOI : 10.1007/978-1-4613-8369-7

J. [. George and . Liu, Computer Solutions of Large Sparse Positive Definite Systems, Prentice-Hall Series in Computational Mathematics, 1981.

]. D. Gor93 and . Gordon, Discrete logarithms in GF(p) using the number field sieve, SIAM J. Discrete Math, vol.6, issue.1, pp.124-138, 1993.

K. [. Gordon, E. F. Mccurley, and . Brickell, Massively Parallel Computation of Discrete Logarithms, Proc. 12th Annual International Cryptology Conference, pp.312-323, 1992.
DOI : 10.1007/3-540-48071-4_22

. [. Granlund, GMP, the GNU multiple precision arithmetic library, 1996.

D. [. Gustavson and . Yun, Fast algorithms for rational Hermite approximation and solution of Toeplitz systems, IEEE Transactions on Circuits and Systems, vol.26, issue.9, pp.750-755, 1979.
DOI : 10.1109/TCS.1979.1084696

]. R. Göt94 and . Göttfert, An acceleration of the Niederreiter factorization algorithm in characteristic 2, Math. Comp, vol.62, issue.206, pp.831-839, 1994.

M. [. Hanrot, E. P. Quercia, and . Zimmerman, The middle product algorithm, I. Speeding up the division and square root of power series, 2003.
URL : https://hal.archives-ouvertes.fr/inria-00071921

]. R. Har and . Harley, The ECDL project

R. [. Joux, ]. Lercierjl02, R. Joux, and . Lercier, The Function Field Sieve Is Quite Special, 5th Algorithmic Number Theory Symposium, pp.431-445, 2001.
DOI : 10.1007/3-540-45455-1_34
URL : https://hal.archives-ouvertes.fr/hal-01102040

]. E. Kal95 and . Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Math. Comp, vol.64, issue.210, pp.777-806, 1995.

A. [. Kaltofen and . Lobo, Distributed Matrix-Free Solution of Large Sparse Linear Systems over Finite Fields, Algorithmica, vol.24, issue.3-4, pp.331-348, 1999.
DOI : 10.1007/PL00008266

V. [. Kaltofen and . Shoup, Subquadratic-time factoring of polynomials over finite fields, Mathematics of Computation, vol.67, issue.223, pp.1179-1197, 1998.
DOI : 10.1090/S0025-5718-98-00944-2

]. D. Knu98 and . Knuth, The Art of Computer Programming

]. N. Kob87 and . Koblitz, Elliptic curve cryptosystems, Math. Comp, vol.48, issue.177, pp.203-209, 1987.

]. N. Kob89 and . Koblitz, Hyperelliptic cryptosystems, J. of Cryptology, vol.1, pp.139-150, 1989.

]. A. Kry31 and . Krylov, On the numerical solutions of the equation by which the frequency of small oscillations is determined in technical problems (in russian), Izv. Akad. Nauk SSSR Ser. Fiz.-Mat, vol.4, pp.491-539, 1931.

A. [. Lamacchia, A. J. Odlyzko, S. A. Menezes, and . Vanstone, Solving Large Sparse Linear Systems Over Finite Fields, Proc. 10th Annual International Cryptology Conference, pp.109-133, 1990.
DOI : 10.1007/3-540-38424-3_8

]. R. Lam96 and . Lambert, Computational aspects of discrete logarithms, 1996.

H. [. Lenstra and J. Lenstra, The development of the number field sieve, Lecture Notes in Math, vol.1554, 1993.
DOI : 10.1007/BFb0091534

H. [. Lenstra, J. Lenstra, M. S. Manasse, J. M. Pollard, A. K. Lenstra et al., The number field sieve, Lecture Notes in Math, vol.32, pp.11-42
DOI : 10.1109/TIT.1986.1057137
URL : https://hal.archives-ouvertes.fr/inria-00108061

M. [. Lenstra, J. Manasse, J. Quisquater, and . Vandewalle, Factoring by electronic mail, Proc. Eurocrypt '89, pp.355-371, 1989.
DOI : 10.1007/3-540-46885-4_35

M. [. Lenstra, I. B. Manasse, and . Damgård, Factoring with two large primes, Proc. Workshop on the Theory and Application of Cryptographic Techniques, pp.72-82, 1990.
DOI : 10.1007/3-540-46877-3_7

M. [. Lenstra and . Manasse, Factoring with two large primes, Mathematics of Computation, vol.63, issue.208, pp.785-798, 1994.
DOI : 10.1090/S0025-5718-1994-1250773-9

E. [. Lenstra, M. Verheul, and . Bellare, The XTR Public Key System, Proc. 20th Annual International Cryptology Conference, pp.1-19, 2000.
DOI : 10.1007/3-540-44598-6_1

H. [. Lidl and . Niederreiter, Finite fields. Encyclopedia of mathematics and its applications, 1983.

]. A. Lob95 and . Lobo, Matrix-free linear system solving and applications to symbolic computations, 1995.

]. J. Mas69 and . Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory, IT?, vol.15, issue.1, pp.122-127, 1969.

]. R. Mat99 and . Matsumoto, Using C ab curves in the function field sieve, IEICE Trans. Fundamentals, issue.3, p.82, 1999.

Y. [. Maurer, ´. Davies, and . Editeur, Non-interactive Public-Key Cryptography, Proc. Workshop on the Theory and Application of Cryptographic Techniques, pp.498-507, 1991.
DOI : 10.1007/3-540-46416-6_43

Y. [. Maurer and . Yacobi, A non-interactive public-key distribution system, Des. Codes Cryptogr, vol.9, issue.3, pp.305-316, 1996.

]. U. Mau94, G. Maurer, and . Desmedt, Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms Advances in Cryptology ? CRYPTO '94, Proc. 14th Annual International Cryptology Conference, pp.271-281, 1994.

S. [. Maurer, N. Wolf, and . Koblitz, Diffie-Hellman Oracles, Proc. 16th Annual International Cryptology Conference, pp.268-282, 1996.
DOI : 10.1007/3-540-68697-5_21

T. [. Menezes, S. A. Okamoto, and . Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory, vol.39, issue.5, pp.1639-1646, 1993.
DOI : 10.1109/18.259647

]. A. Mvov97, P. C. Menezes, E. S. Van-oorschot, and . Vanstone, Handbook of applied cryptography Use of elliptic curves in cryptography Advances in Cryptology ? CRYPTO '86, Mil87] V. Miller Proc. 7th Annual International Cryptology ConferenceMon95] P. L. Montgomery. A block Lanczos algorithm for finding dependencies over GF, pp.417-426, 1986.

L. C. Dans, J. Guillou, . F. Quisquater, M. A. Morain, J. Morrison et al., Analyzing pmpqs. Disponiblè a l'adresse ftp://lix.polytechnique.fr/ pub/submissions/morain/Preprints/pmpqs.ps.Z, 1993. Note informelle. [Mor80] M. Morf. Doubling algorithms for Toeplitz and related equations Conference Acoustics, Speech and Signal Processing A method of factoring and the factorization of F 7 [MPI] MPI, message passing interface, 1994?. Documentation, and homepage of the MPIch implementation at http://www-unix.mcs.anl.gov/mpi/. [Nec94] V. I. Nechaev. Complexity of a determinate algorithm for the discrete logarithm Factorization of polynomials and some linear-algebra problems over finite fields, Advances in Cryptology ? EURO- CRYPT '95 Proc. International Conference on the Theory and Application of Cryptographic Techniques Proc. IEEE InternatNie93b] H. Niederreiter. A new efficient factorization algorithm for polynomials over small finite fieldsOdl85] A. M. Odlyzko. Discrete logarithms in finite fields and their cryptographic significance, pp.106-120, 1975.

T. Dans, N. Beth, E. I. Cot, ´. Ingemarsson, P. C. Van-oorschot et al., Parallel collision search with cryptanalytic applications A look-ahead Lanczos algorithm for unsymmetric matrices Available from http An improved algorithm for computing logarithms over GF(p) and its cryptographic significance A Monte-Carlo method for factorization Monte Carlo methods for index computation (mod p) The lattice sieve The development of the number field sieve Analysis and comparison of some integer factoring algorithms, Advances in Cryptology ? EURO- CRYPT '84. Lecture Notes in Comput. Sci Proc. Eurocrypt '84 Lenstra, Jr. et R. Tijdeman, ´ editeurs, Computational methods in number theory, pp.224-3141, 1975.

J. [. Pomerance and . Smith, Reduction of Huge, Sparse Matrices over Finite Fields Via Created Catastrophes, Experimental Mathematics, vol.32, issue.2, pp.89-94, 1992.
DOI : 10.1080/10586458.1992.10504250

[. Quisquater, J. Delescaille, J. Quisquater, and J. Vandewalle, How easy is collision search? Application to DES, Proc. Eurocrypt '89, pp.429-434, 1989.
DOI : 10.1007/3-540-46885-4_43

]. J. [-ris72, I. Rissanen, T. J. Research, . Watson-research, and . Center, Realizations of matrix sequences, 1972.

A. [. Rivest, L. M. Shamir, and . Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, vol.21, issue.2, pp.120-126, 1978.
DOI : 10.1145/359340.359342

]. H. Rüc99 and . Rück, On the discrete logarithm in the divisor class group of curves, Math. Comp, vol.68, issue.226, pp.805-806, 1999.

K. [. Satoh and . Araki, Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Comment. Math. Helv, vol.47, issue.1, pp.81-92, 1998.

C. [. Sattler and . Schnorr, Generating random walks in groups, Ann. Univ. Sci. Budapest. Sect. Comput, vol.6, pp.65-79, 1985.

D. [. Schirokauer, T. F. Weber, ´. Denny-cohen, . Editeur, and . Ants-ii, Discrete logarithms: The effectiveness of the index calculus method, 2nd Algorithmic Number Theory Symposium, pp.337-361, 1996.
DOI : 10.1007/3-540-61581-4_66

]. C. Sch91 and . Schnorr, Efficient signature generation by smart cards, J. of Cryptology, vol.4, issue.3, pp.161-174, 1991.

V. [. Schönhage and . Strassen, Fast multiplication of large numbers, Computing, vol.150, issue.3-4, pp.281-292, 1971.
DOI : 10.1007/BF02242355

]. I. Sem98a and . Semaev, An algorithm for evaluation of discrete logarithms in some nonprime finite fields, Math. Comp, vol.67, issue.224, pp.1679-1689, 1998.

]. I. Sem98b and . Semaev, Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curves in characteristic p, Math. Comp, vol.67, issue.221, pp.353-356, 1998.

]. A. Sha85, G. R. Shamir, D. Blakley, and . Chaum, Identity-based cryptosystems and signature schemes Advances in Cryptology ? CRYPTO '84, Proc. Cryptology Workshop, pp.47-53, 1984.

]. D. Sha71, D. J. Shanks-dans, and . Lewis, Class number, a theory of factorization, and genera, Number theory institute. Proc. Sympos. Pure Math, pp.415-440, 1969.

]. V. Sho90 and . Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett, vol.33, pp.261-267, 1990.

]. V. Sho95 and . Shoup, A new polynomial factorization algorithm and its implementation, J. Symbolic Comput, vol.20, issue.4, pp.363-397, 1995.

]. V. Sho97, ´. Shoup-fumy, and . Editeur, Lower bounds for discrete logarithms and related problems Advances in Cryptology ? EUROCRYPT '97, Proc. International Conference on the Theory and Application of Cryptographic Techniques, pp.256-266, 1997.

J. H. Silverman, The arithmetic of elliptic curves, Grad. Texts in Math, vol.106, 1986.

]. N. Sma99 and . Smart, The discrete logarithm problem on elliptic curves of trace one, J. of Cryptology, vol.12, issue.3, pp.193-196, 1999.

]. V. Str69 and . Strassen, Gaussian elimination is not optimal, Numer. Math, vol.13, pp.354-356, 1969.

]. E. Tes01 and . Teske, On random walks for Pollard's rho method, Math. Comp, vol.70, issue.234, pp.809-825, 2001.

]. E. Tho01a and . Thomé, Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm, Proc. International Symposium on Symbolic and Algebraic Computation, pp.323-331, 2001.

]. E. Tho01b, C. Thomé, E. Boyd, and . Dawson, Computation of discrete logarithms in F 2 607 Advances in Cryptology ? ASIACRYPT, Proc. 7th International Conference on the Theory and Applications of Cryptology and Information Security, pp.107-124, 2001.

]. E. Tho02a and . Thomé, Discrete logarithms in GF(2 607 ) E-mail sur la liste NMBRTHRY. Disponiblè a l'adresse http Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, J. Symbolic Comput, vol.33, issue.5, pp.757-775, 2002.

]. G. Vil97 and . Villard, A study of Coppersmith's block Wiedemann algorithm using matrix polynomials, LMC-IMAG, vol.975, 1997.

T. [. Weber, H. Denny, and . Krawczyk, The solution of McCurley's discrete log challenge, Proc. 18th Annual International Cryptology Conference, pp.458-471, 1998.
DOI : 10.1007/BFb0055747

]. D. Wie86 and . Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory, IT?, vol.32, issue.1, pp.54-62, 1986.

]. P. Zim98 and . Zimmermann, An implementation in GMP of Schönhage's fast multiplication algorithm modulo 2 N + 1, 1998. Programme mul_fft