. Si-l-'intervalle-d, arrivée des fonctions n'est pas [1/2,1[, alors il faut changer n' en n' + ji où ji est choisi en fonction de l'intervalle d'arrivée de fi. Éventuellement, on peut résoudre plusieurs équations du même type que l'équation (2.1)

T. La-recherche-sur-l-'intervalle-de-départ, Chacune de ces petites recherches est effectuée extrêmement rapidement -asymptotiquement, en temps quadratique en log N, log N' et log M -et on cherche donc naturellement à augmenter T car la complexité de la recherche complète sera de l'ordre de N /T. La raison pour laquelle on ne peut augmenter T arbitrairement est que la recherche rapide sur les petits intervalles est possible seulement si les intervalles en question sont suffisamment petits, Le but est donc de maximiser T sous la condition que la recherche sur les petits intervalles soit réalisable efficacement

. Pour-un-petit-intervalle-donné, fonctions ft et h par des polynômes Pl et P2 de degré 2 sur l'intervalle. On peut par exemple prendre les développements de Taylor d'ordre 2 des fonctions au milieu de l'intervalle. Ce n'est vraisemblablement pas la meilleure approximation, mais cela est suffisant ici. Une fois les deux polynômes calculés, on essaie de résoudre l'équation (2.1) pour les polynômes ~ à la place des fonctions fi, Bien entendu, ces polynômes doivent être suffisamment proches des fonctions et M doit être légèrement diminué pour ne pas écarter de solution. Plus précisément, on veut que N'·lfi(X) -~(x)1 ~ l/M pour tout x dans l'intervalle considéré

C. Si-f-est, on sait qu'il existe un réel t dans l'intervalle tel que l!i(X) -Pi (X) 1 = f(3)(t) ~

E. Calculer and N. Tel-que, ·IPi(t) -fi(t)1 < E pour tout tE

. Démonstration, Grâce à l'étape 12, il suffit de montrer que l'on n'écarte pas de solution à l'équation (2.1) Supposons que l'on ait un Xo E li-T, Til qui satisfasse l'équation (2.1) À Bibliographie

L. Adleman, On Breaking the Iterated Merkle-Hellman Public-Key Cryptosystem, Proceedings of Crypto 1982, pp.303-308, 1983.
DOI : 10.1007/978-1-4757-0602-4_29

M. Aharoni, S. Asaf, and R. , Maharik, 1. Nehama, 1. Nikulshin, and A. Ziv. Solving constraints on the invisible bits of the intermediate result for fioating-point verification, Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH'17), pp.76-83, 2005.

A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, 1974.

M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , STOC '96, pp.99-108, 1996.
DOI : 10.1145/237814.237838

M. Ajtai, The short est vector problem in l2 is NP-hard for randomized reductions (extended abstract), Proceedings of the 30th Symposium on the Theory of Computing, pp.284-293, 1998.

M. Ajtai, Random lattices and a conjectured 0-1 law about their polynomial time comput able properties, Proceedings of the 2002 Symposium on Foundations of Computer Science, pp.13-39, 2002.

M. Ajtai, The worst-case behavior of schnorr's algorithm approximating the short est nonzero vector in a lattice, Proceedings of the 35th Symposium on the Theory of Computing, pp.396-406, 2003.

M. Ajtai and C. Dwork, A public-key cryptosystem with worst-case/average-case equivalence, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , STOC '97, pp.284-293, 1997.
DOI : 10.1145/258533.258604

M. Ajtai, R. Kumar, and D. Sivakumar, A sieve algorithm for the short est lattice vector problem, Proceedings of the 33rd Symposium on the Theory of Computing, pp.601-610, 2001.

M. Ajtai, R. Kumar, and D. Sivakumar, Sampling short lattice vectors and the closest lattice vector problem, Proceedings 17th IEEE Annual Conference on Computational Complexity, pp.53-57, 2002.
DOI : 10.1109/CCC.2002.1004339

A. Akhavi, Analyse comparative d'algorithmes de réduction sur les réseaux aléatoires, 1999.

. Akhavi, Worst-Case Complexity of the Optimal LLL Algorithm, Proceedings of the 2000 Latin American Theoretical Informatics, pp.355-366, 2000.
DOI : 10.1007/10719839_35

. Akhavi, Random lattices, threshold phenomena and efficient reduction algorithms, Theoretical Computer Science, vol.287, issue.2, pp.359-385, 2002.
DOI : 10.1016/S0304-3975(01)00251-1

URL : https://doi.org/10.1016/s0304-3975(01)00251-1

A. Akhavi, C. Moreira, and . Santos, Another View of the Gaussian Algorithm, Proceedings of the 2004 Latin American Theoretical Informatics, pp.474-487, 2004.
DOI : 10.1007/978-3-540-24698-5_51

URL : https://hal.archives-ouvertes.fr/hal-00159666

). K. Atkinson, An introduction to Numerical Analysis, 1989.

L. Babai, On Lov??sz??? lattice reduction and the nearest lattice point problem, Combinatorica, vol.357, issue.1, pp.1-13, 1986.
DOI : 10.1016/B978-0-12-566780-7.50016-7

W. Backes and S. Wetzel, Heuristics on lattice basis reduction in practice, Journal of Experimental Algorithmics, vol.7, issue.1, 2002.
DOI : 10.1145/944618.944619

G. Batut, K. Belabas, D. Bernardi, H. Cohen, and M. Olivier, PARI/GP computer package version 2. Disponible à l'url http

A. Bjorck, Numerical Methods or Least Squares Problems, 1996.
DOI : 10.1137/1.9781611971484

J. Blomer and A. May, New Partial Key Exposure Attacks on RSA, Proceedings of Crypto 2003, pp.27-43
DOI : 10.1007/978-3-540-45146-4_2

L. Blum, M. Blum, and M. Shub, A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing, vol.15, issue.2, pp.364-383, 1986.
DOI : 10.1137/0215025

M. Blum and S. Micali, How to generate cryptographically strong sequences of pseudo random bits, 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pp.850-864, 1984.
DOI : 10.1109/SFCS.1982.72

S. Boldo, Preuves formelles en arithmétiques à virgule flottante, 2004.

D. Boneh and G. Durfee, Cryptanalysis of RSA with private key d less than NO.292, IEEE Transactions on Information Theory, vol.46, issue.4, pp.233-260, 2000.

D. Boneh, G. Durfee, and N. Howgrave-graham, Factoring N = p r q for Large r, Proceedings of Eurocrypt 1999, pp.326-337, 1999.
DOI : 10.1007/3-540-48405-1_21

D. Boneh, S. Halevi, and N. Howgrave-graham, The Modular Inversion Hidden Number Problem, Proceedings of Asiacrypt 2001, pp.36-51, 2001.
DOI : 10.1007/3-540-45682-1_3

R. Brent, Fast Multiple-Precision Evaluation of Elementary Functions, Journal of the ACM, vol.23, issue.2, pp.242-251, 1976.
DOI : 10.1145/321941.321944

R. P. Brent, Twenty year's analysis of the binary Euclidean algorithm, Millenniai Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in honour of Professor Sir Anthony Hoare, pp.41-53, 2000.

R. P. Brent, F. G. Gustavson, and D. Y. Yun, Fast solution of toeplitz systems of equations and computation of Pad?? approximants, Journal of Algorithms, vol.1, issue.3, pp.259-295, 1980.
DOI : 10.1016/0196-6774(80)90013-9

R. P. Brent and H. T. Kung, A systolic VLSI array for integer GCD computation, Proceedings of the 7th IEEE Symposium on Computer Arithmetic (ARITH'7), pp.118-125, 1985.

E. F. Brickell, Solving Low Density Knapsacks, Proceedings of Crypto 1983, pp.25-37, 1984.
DOI : 10.1007/978-1-4684-4730-9_2

E. F. Brickell, Breaking Iterated Knapsacks, Lecture Notes in Computer Science, vol.196, pp.342-358, 1984.
DOI : 10.1007/3-540-39568-7_27

E. F. Brickell, J. C. Lagarias, and A. M. Odlyzko, Evaluation of Adleman's attack on multiply iterated knapsacks (abstract), Proceedings of Crypto 1983, pp.39-42, 1984.

N. Brisebarre, D. Defour, P. Kornerup, J. Muller, and N. , A new range-reduction algorithm, IEEE Transactions on Computers, vol.54, issue.3, pp.331-339, 2005.
DOI : 10.1109/TC.2005.36

URL : https://hal.archives-ouvertes.fr/ensl-00086904

N. Brisebarre, J. Muller, and A. Tisserand, Computing machine-efficient polynomial approximations, ACM Transactions on Mathematical Software, vol.32, issue.2, 2005.
DOI : 10.1145/1141885.1141890

URL : https://hal.archives-ouvertes.fr/ensl-00086826

J. W. Cassels, An Introduction to the Geometry of Numbers, 1971.
DOI : 10.1007/978-3-642-62035-5

G. Cesari, Parallel implementation of Sch??nhage's integer GCD algorithm, Proceedings of the 3rd Algorithmic Number Theory Symposium (ANTS III), volume 1423 of Lecture Notes in Computer Science, pp.65-76, 1998.
DOI : 10.1007/BFb0054852

H. Cohen, A Course in Computational Algebraic Number Theory, 1995.
DOI : 10.1007/978-3-662-02945-9

H. Cohn and A. Kumar, The densest lattice in twenty-four dimensions, pp.58-67, 2004.

J. H. Conway and N. J. Sloane, Sphere Packings, Lattices and Groups, 1988.

D. Coppersmith, Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known, Proceedings of Eurocrypt 1996, pp.178-189, 1996.
DOI : 10.1007/3-540-68339-9_16

D. Coppersmith, Finding a Small Root of a Univariate Modular Equation, Proceedings of Eurocrypt 1996, pp.155-165, 1996.
DOI : 10.1007/3-540-68339-9_14

D. Coppersmith, Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities, Journal of Cryptology, vol.10, issue.4, pp.233-260, 1997.
DOI : 10.1007/s001459900030

D. Coppersmith, Finding Small Solutions to Small Degree Polynomials, Proceedings of the 2001 Cryptography and Lattices Conference, pp.20-31, 2001.
DOI : 10.1007/3-540-44670-2_3

URL : http://cr.yp.to/bib/2001/coppersmith.pdf

B. Daireaux, Analyse des algorithmes d'Euclide: une approche dynamique, 2005.

B. Daireaux, V. Maume-deschamps, and B. Vallée, The Lyapunov tortoise and the dyadic hare, Proceedings of the 2005 International Conference on the Analysis of Algorithm (AofA '05), DMTCS proc. AD, pp.71-94, 2005.
URL : https://hal.archives-ouvertes.fr/hal-01184044

R. Daudé and B. Vallée, An upper bound on the average number of iterations of the LLL algorithm, Theoretical Computer Science, vol.123, issue.1, pp.95-115, 1994.
DOI : 10.1016/0304-3975(94)90071-X

D. Defour, Cache-optimized methods for the evaluation of elementary functions Rapport du LIP, École Normale Supérieure de Lyon. Disponible à l'url http, 2002.

D. Defour, F. De-dinechin, and J. Muller, Correctly rounded exponential function in double precision arithmetic, SPIE, 46th Annual Meeting International Symposium on Optical Science and Technology, pp.156-167, 2001.
URL : https://hal.archives-ouvertes.fr/inria-00072387

D. Defour, G. Ranrot, V. Lefèvre, J. Muller, N. Revol et al., ProposaI for a standardization of mathematical function implementations in floatingpoint arithmetic, Numerical Algorithms, vol.37, pp.1-4367, 2004.

B. N. Delone and N. N. Sandakova, Theory of stereohedra, Trudy Mathematics Institute Steklov, vol.64, pp.28-51, 1961.

J. Demmel and Y. Rida, Accurate floating-point summation. Technical report of the computer science department of the University of California Berkeley, pp.2-1180, 2002.

F. De-dinechin, A. V. Ershov, and N. Gast, Towards the Post-Ultimate libm, 17th IEEE Symposium on Computer Arithmetic (ARITH'05), pp.288-295, 2005.
DOI : 10.1109/ARITH.2005.46

URL : https://hal.archives-ouvertes.fr/inria-00070636

G. Dinur, S. Kindler, and . Safra, Approximating CVP to within almost polynomial factors is NP-hard, Proceedings of the 1998 Symposium on Foundations of Computer Science, pp.99-109, 1998.
DOI : 10.1109/sfcs.1998.743433

URL : http://www.matha.mathematik.uni-dortmund.de/~fv/diplom_i/dks98.ps

F. Eisenbrand and G. Rote, Fast Reduction of Ternary Quadratic Forms, Proceedings of the 2001 Cryptography and Lattices Conference, pp.32-44
DOI : 10.1007/3-540-44670-2_4

5. N. Elkies, Rational points near curves and small nonzero Ix 3 -y21 via lattice reduction, Proceedings of the 4th Algorithmic Number Theory Symposium (ANTS IV), volume 1838 of Lecture Notes in Computer Science, pp.33-63, 2000.
DOI : 10.1007/10722028_2

URL : http://arxiv.org/pdf/math/0005139

P. Van-emde and . Boas, Another NP-complete partition problem and the complexity of computing short vectors in a lattice, Mathematisch Instituut, 1981.

M. Ernst, E. Jochens, A. May, and B. De-weger, Partial Key Exposure Attacks on RSA up to Full Size Exponents, Proceedings of Eurocrypt 2005, number 3494 in Lecture Notes in Computer Science, pp.371-386, 2005.
DOI : 10.1007/11426639_22

6. L. Fousse and P. Zimmermann, Accurate summation : towards a simpler and formaI pro of, Proceedings of the international conference on real numbers and computers (RNC'5), pp.97-108, 2003.

6. S. Gal, Computing elementary functions: A new approach for achieving high accuracy and good performance, Proceedings of Accurate Scientific Computations, pp.1-16, 1986.
DOI : 10.1007/3-540-16798-6_1

6. S. Gal and B. Bachelis, An accurate elementary mathematicallibrary for the IEEE floating point standard, ACM Transactions on Mathematical Software, vol.17, issue.1, pp.16-45, 1991.

6. J. Zur-gathen and J. Gerhardt, Modern Computer Algebra, 2003.
DOI : 10.1017/CBO9781139856065

6. C. Gauss, Disquisitiones ArithmeticfE, 1801.

6. D. Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys, vol.23, issue.1, pp.5-47, 1991.
DOI : 10.1145/103162.103163

6. O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudorandomness, 1999.
DOI : 10.1007/978-3-662-12521-2

6. O. Goldreich and S. Goldwasser, On the limits of non-approximability of lattice problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing , STOC '98, pp.540-563, 2000.
DOI : 10.1145/276698.276704

6. O. Goldreich, S. Goldwasser, and S. Halevi, Public-key cryptosystems from lattice reduction problems, Proceedings of Crypto 1997, pp.112-131, 1997.
DOI : 10.1007/BFb0052231

URL : http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-703.pdf

7. D. Goldstein and A. Mayer, On the equidistribution of Hecke points, Forum Mathematicum, vol.159, issue.2, pp.165-189, 2003.
DOI : 10.1515/form.2003.009

G. Gonnet, A note on finding difficult values to evaluate numerically Disponible à l'url http://www.inf.ethz.ch/personal/gonnet/FPAccuracy/NastyValues.ps, 2002.

T. Granlund, The GNU MP Bignum Library Disponible à l'url http

L. Groetschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 1988.

B. Helfrich, Algorithms to construct minkowski reduced and hermite reduced lattice bases, Theoretical Computer Science, vol.41, pp.125-139, 1985.
DOI : 10.1016/0304-3975(85)90067-2

URL : https://doi.org/10.1016/0304-3975(85)90067-2

C. Hermite, Extraits de lettres de M. Hermite à M. Jacobi sur différents objets de la théorie des nombres, deuxième lettre, Journal für die reine und angewandte Mathematik, pp.279-290, 1850.

N. J. Higham, The Accuracy of Floating Point Summation, SIAM Journal on Scientific Computing, vol.14, issue.4, pp.783-799, 1993.
DOI : 10.1137/0914050

M. Van-hoeij, Factoring Polynomials and 0???1 Vectors, Proceedings of the 2001 Cryptography and Lattices Conference, pp.45-50, 2001.
DOI : 10.1007/3-540-44670-2_5

J. Hoffstein, J. Pipher, and J. H. Silverman, NTRU: A ring-based public key cryptosystem, Proceedings of the 3rd Algorithmic Number Theory Symposium (ANTS III), volume 1423 of Lecture Notes in Computer Science, pp.267-288
DOI : 10.1007/BFb0054868

N. Howgrave-graham, Computational Mathematics inspired by RSA, 1998.

N. A. Howgrave-graham and N. P. Smart, Lattice attacks on digital signature schemes. Design, Codes and Cryptography, pp.283-290, 2001.

C. S. Iordache and D. W. Matula, On infinitely precise rounding for division, square root, reciprocal and square root reciprocal, Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No.99CB36336), pp.233-240, 1999.
DOI : 10.1109/ARITH.1999.762849

T. Jebelean, A Double-Digit Lehmer-Euclid Algorithm for Finding the GCD of Long Integers, Journal of Symbolic Computation, vol.19, issue.1-3, pp.145-157, 1995.
DOI : 10.1006/jsco.1995.1009

A. Joux and J. Stern, Lattice Reduction: A Toolbox for the Cryptanalyst, Journal of Cryptology, vol.11, issue.3, pp.161-185, 1998.
DOI : 10.1007/s001459900042

M. Kaib and C. P. Schnorr, The Generalized Gauss Reduction Algorithm, Journal of Algorithms, vol.21, issue.3, pp.565-578, 1996.
DOI : 10.1006/jagm.1996.0059

E. Kaltofen, On the complexity of finding short vectors in integer lattices, Proceedings of EUROCAL '83, pp.236-244, 1983.
DOI : 10.1007/3-540-12868-9_107

R. Kannan, Improved algorithms for integer programming and related lattice problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing , STOC '83, pp.99-108, 1983.
DOI : 10.1145/800061.808749

R. Kannan, A. K. Lenstra, and L. Lovâsz, Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers, Proceedings of the 16th Symposium on the Theory of Computing, pp.191-200, 1984.

S. Khot, Hardness of approximating the short est vector problem in lattices, Proceedings of the 2004 Symposium on Foundations of Computer Science, pp.126-135, 2004.

D. Knuth, The analysis of algorithms, pp.269-274, 1971.

D. Knuth, The Art of Computer Programming, 1981.

A. Korkine and G. Zolotarev, Sur les formes quadratiques, Mathematische Annalen, vol.6, issue.3, pp.336-389, 1873.
DOI : 10.1007/BF01442795

H. Koyand and C. P. Schnorr, Segment LLL-reduction of lattice bases, Proceedings of the 2001 Cryptography and Lattices Conference, pp.67-80, 2001.

H. Koy and C. P. Schnorr, Segment LLL-Reduction with Floating Point Orthogonalization, Proceedings of the 2001 Cryptography and Lattices Conference, pp.81-96, 2001.
DOI : 10.1007/3-540-44670-2_8

URL : http://www.mi.informatik.uni-frankfurt.de/research/papers/koy.segment_lll_fpo.2001.ps.gz

J. C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, Journal of Algorithms, vol.1, issue.2, pp.142-186, 1980.
DOI : 10.1016/0196-6774(80)90021-8

J. C. Lagarias, The computational complexity of simultaneous diophantine approximation problems, Proceedings of the 1983 Symposium on the Foundations of Computer Science, pp.32-39, 1983.

J. C. Lagarias, Knapsack Public Key Cryptosystems and Diophantine Approximation, Proceedings of Crypto 1983, pp.3-23, 1984.
DOI : 10.1007/978-1-4684-4730-9_1

URL : http://www.math.lsa.umich.edu/~lagarias/doc/1218knap.pdf

J. C. Lagarias, W. H. Lenstra, and C. P. Schnorr, Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica, vol.96, issue.4 (208), pp.333-348, 1990.
DOI : 10.1007/978-3-0348-6925-6

J. C. Lagarias and A. M. Odlyzko, Solving low-density subset sum problems, Proceedings of the 1983 Symposium on the Foundations of Computer Science, pp.1-10, 1983.

J. C. Lagarias and A. M. Odlyzko, Solving low-density subset sum problems, Journal of the A CM, vol.32, pp.229-246, 1985.
DOI : 10.1145/2455.2461

URL : http://www.busim.ee.boun.edu.tr/~mihcak/teaching/ee684-spring07/proposed-project-papers/hard-problems/subset-sum/p229-lagarias.pdf

J. L. Lagrange, Recherches d'arithmétique. Nouveaux Mémoires de l'Académie de Berlin, 1773.

T. Lang and J. Muller, Bounds on runs of zeros and ones for algebraic functions, Proceedings 15th IEEE Symposium on Computer Arithmetic. ARITH-15 2001, pp.13-20, 2001.
DOI : 10.1109/ARITH.2001.930099

C. L. Lawson and R. J. Hanson, Solving Least Squares Problems, 1995.
DOI : 10.1137/1.9781611971217

V. Lefèvre, An Algorithm that Computes a Lower Bound on the Distance Between a Segment and ???2, 1997.
DOI : 10.1007/978-94-017-1247-7_16

V. Lefèvre, An algorithm that computes a lower bound on the distance between a segment and 7l 2 ? Developments in Reliable Computing, pp.203-212, 1999.

V. Lefèvre, Moyens arithmétiques pour un calcul fiable, 2000.

V. Lefèvre, New results on the distance between a segment and 7l 2 ? Application to the exact rounding, Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH'17), pp.68-75, 2005.

V. Lefèvre and J. Muller, Worst cases for correct rounding of the elementary functions in double precision, Proceedings 15th IEEE Symposium on Computer Arithmetic. ARITH-15 2001, pp.111-118, 2001.
DOI : 10.1109/ARITH.2001.930110

]. V. Llo, J. Lefèvre, and . Muller, Worst cases for correct rounding in double pre- CISIOn. Disponible à l'url http, 2004.

]. D. Lehmer, Euclid's Algorithm for Large Numbers, The American Mathematical Monthly, vol.45, issue.4, pp.227-233, 1938.
DOI : 10.1080/00029890.1938.11990797

A. K. Lenstra, H. W. Lenstra, J. , and L. Lovasz, Factoring polynomials with rational coefficients, Mathematische Annalen, vol.32, issue.4, pp.513-534, 1982.
DOI : 10.1007/BF01457454

URL : http://www.busim.ee.boun.edu.tr/~mihcak/teaching/ee684-spring07/proposed-project-papers/hard-problems/lattice-problems/lenstra.pdf

H. W. Lenstra and J. , Integer Programming with a Fixed Number of Variables, Mathematics of Operations Research, vol.8, issue.4, 1981.
DOI : 10.1287/moor.8.4.538

H. W. Lenstra and J. , Integer Programming with a Fixed Number of Variables, Mathematics of Operations Research, vol.8, issue.4, pp.538-548, 1983.
DOI : 10.1287/moor.8.4.538

H. W. Lenstra and J. , Flags and Lattice Basis Reduction, Proceedings of the third European congress of mathematics
DOI : 10.1007/978-3-0348-8268-2_3

URL : http://www.mathematik.uni-bielefeld.de/~rehmann/ECM/cdrom/3ecm/pdfs/pant3/lenstra.pdf

D. Lichtblau, Half-GCD and fast rational recovery, Proceedings of the 2005 international symposium on Symbolic and algebraic computation , ISSAC '05, 2005.
DOI : 10.1145/1073884.1073917

J. E. Littlewood, A Mathematician's Miscellany, 1953.

]. L. Lovasz, An Algorithmic Theory of Numbers, Graphs and Convexity, CBMS-NSF Regional Conference Series in Applied Mathematics, 1986.
DOI : 10.1137/1.9781611970203

. Magma, The Magma computational algebra system for algebra, number theory and geometry. Disponible à l'url http

. Maplesoft, Maple 10 Disponible à l'url http

P. Markstein, A fast-st art method for computing the inverse tangent, Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH'11), pp.266-271, 2005.

J. Martinet, Perfect Lattices in Euclidean Spa ces, 2002.

A. May, Cryptanalysis of Unbalanced RSA with Small CRT-Exponent, Proceedings of Crypto 2002, pp.242-256, 2002.
DOI : 10.1007/3-540-45708-9_16

A. May, New RSA Vulnerabilities Using Lattice Reduction Methods, 2003.

A. May, Computing the RSA Secret Key Is Deterministic Polynomial Time Equivalent to Factoring, Proceedings of Crypto, pp.213-219, 2004.
DOI : 10.1007/978-3-540-28628-8_13

R. Merkle and M. Hellman, Hiding information and signatures in trapdoor knapsacks, IEEE Transactions on Information Theory, vol.24, issue.5, pp.525-530, 1978.
DOI : 10.1109/TIT.1978.1055927

D. Micciancio, The hardness of the closest vector problem with preprocessing, IEEE Transactions on Information Theory, vol.47, issue.3, pp.1212-1215, 2001.
DOI : 10.1109/18.915688

D. Micciancio, Improving Lattice Based Cryptosystems Using the Hermite Normal Form, Proceedings of the 2001 Cryptography and Lattices Conference, pp.126-145
DOI : 10.1007/3-540-44670-2_11

D. Mieciancio, The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant, SIAM Journal on Computing, vol.30, issue.6, pp.2008-2035, 2001.
DOI : 10.1137/S0097539700373039

D. Mieciancio and S. Goldwasser, Complexity of lattice problems : a cryptographie perspective, 2002.
DOI : 10.1007/978-1-4615-0897-7

H. Minkowski, Geometrie der Zahlen, 1896.

N. Moller, On Schonhage's algorithm, and subquadratie integer gcd computation, 2005.

P. Montgomery, Modular multiplication without trial division, Mathematics of Computation, vol.44, issue.170, pp.519-521, 1985.
DOI : 10.1090/S0025-5718-1985-0777282-X

J. Muller, Elementary Functions, Algorithms and Implementation, 1997.
URL : https://hal.archives-ouvertes.fr/ensl-01398294

Y. V. Nesterenko and M. Waldschmidt, On the approximation of the values of exponential function and logarithm by algebraie numbers, Matematicheskie Zapiski, vol.2, pp.23-42, 1996.

P. Nguyên, Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ???97, Proceedings of Crypto 1999, pp.288-304, 1999.
DOI : 10.1007/3-540-48405-1_18

P. Nguyên, Can We Trust Cryptographic Software? Cryptographic Flaws in GNU Privacy Guard v1.2.3, Proceedings of Eurocrypt, pp.555-570, 2004.
DOI : 10.1007/978-3-540-24676-3_33

P. Nguyên and D. Stehlé, Low-Dimensional Lattice Basis Reduction Revisited, Proceedings of the 6th Algorithmic Number Theory Symposium (ANTS VI), pp.338-357
DOI : 10.1007/978-3-540-24847-7_26

P. Nguyên and D. Stehlé, Floating-Point LLL Revisited, Proceedings of Eurocrypt 2005, pp.215-233
DOI : 10.1007/11426639_13

P. Nguyên and J. Stern, Cryptanalysis of the Ajtai-Dwork cryptosystem, Lecture Notes in Computer Science, vol.1462, pp.223-242, 1998.
DOI : 10.1007/BFb0055731

P. Nguyên and J. Stern, The Two Faces of Lattices in Cryptology, Proceedings of the 2001 Cryptography and Lattices Conference, pp.146-180, 2001.
DOI : 10.1007/3-540-44670-2_12

A. M. Odlyzko, The rise and fall of knapsack cryptosystems, Proceedings of Cryptology and Computational Number Theory, volume 42 of Proceedings of Symposia in Applied Mathematics, pp.75-88, 1989.
DOI : 10.1090/psapm/042/1095552

A. M. Odlyzko and H. Te-riele, Dispoof of Mertens conjecture, Journal für die reine und angewandte Mathematik, pp.138-160, 1985.

V. Y. Pan and X. Wang, Acceleration of Euclidean algorithm and extensions, Proceedings of the 2002 international symposium on Symbolic and algebraic computation , ISSAC '02, pp.207-213, 2002.
DOI : 10.1145/780506.780533

M. Payne and R. Hanek, Radian reduction for trigonometric functions, ACM SIGNUM Newsletter, vol.18, issue.1, pp.19-24, 1983.
DOI : 10.1145/1057600.1057602

M. Pohst, A modification of the LLL reduction algorithm, Journal of Symbolic Computation, vol.4, issue.1, pp.123-127, 1987.
DOI : 10.1016/S0747-7171(87)80061-5

S. The and . Project, MPFR, a LGPL-library for multiple-precision floating-point computations with exact rounding. Disponible à l'url http

G. B. Purdy, A carry-free algorithm for finding the greatest common divisor of two integers, Computers & Mathematics with Applications, vol.9, issue.2, pp.311-316, 1982.
DOI : 10.1016/0898-1221(83)90133-5

S. S. Ryskov, On Hermite, Minkowski and Venkov reduction of positive quadratic forms in n variables, Soviet Mathematics Doklady, vol.13, pp.1676-1679, 1972.

C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science, vol.53, issue.2-3, pp.201-224, 1987.
DOI : 10.1016/0304-3975(87)90064-8

C. P. Schnorr, A more efficient algorithm for lattice basis reduction, Journal of Algorithms, vol.9, issue.1, pp.47-62, 1988.
DOI : 10.1016/0196-6774(88)90004-1

C. P. Schnorr, Lattice Reduction by Random Sampling and Birthday Methods, Proceedings of the annual symposium on theoretical aspects of computer science, pp.145-156, 2003.
DOI : 10.1007/3-540-36494-3_14

URL : http://publikationen.ub.uni-frankfurt.de/volltexte/2005/1209/pdf/schnorr.pdf

C. P. Schnorr, Fast LLL-type lattice reduction. À paraître Version préliminaire disponible à l'url http, 2005.
DOI : 10.1016/j.ic.2005.04.004

URL : https://doi.org/10.1016/j.ic.2005.04.004

C. P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Mathematical Programming, vol.13, issue.1, pp.181-199, 1994.
DOI : 10.1007/BF01581144

URL : http://publikationen.ub.uni-frankfurt.de/files/4259/schnorr.pdf

A. Schonhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Informatica, vol.1, issue.2, pp.139-183, 1971.
DOI : 10.1007/BF00289520

A. Schonhage, Factorization of univariate integer polynomials by diophantine approximation and an improved basis reduction algorithm, Proceedings of the 1984 International Colloquium on Automata, Languages and Programming, pp.436-447, 1984.
DOI : 10.1007/3-540-13345-3_40

A. Schonhage, Fast reduction and composition of binary quadratic forms, Proceedings of the 1991 international symposium on Symbolic and algebraic computation , ISSAC '91, pp.128-133, 1991.
DOI : 10.1145/120694.120711

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

. Semaev, A 3-Dimensional Lattice Reduction Algorithm, Proceedings of the 2001 Cryptography and Lattices Conference, pp.181-193, 2001.
DOI : 10.1007/3-540-44670-2_13

A. Shamir, A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem, Proceedings of the 1982 Symposium on the Foundations of Computer Science (FOCS 1982), pp.145-152, 1982.

M. Shand and J. Vuillemin, Fast implementations of RSA cryptography, Proceedings of IEEE 11th Symposium on Computer Arithmetic, pp.252-259, 1993.
DOI : 10.1109/ARITH.1993.378085

V. Shoup, N. Ntl, C. Theory, and . Library, Disponible à l'url http

. Shparlinski, Cryptographic Applications of Analytic Number Theory, 2003.
DOI : 10.1007/978-3-0348-8037-4

C. L. Siegel, Lectures on the Geometry of Numbers, 1989.
DOI : 10.1007/978-3-662-08287-4

D. Simon, Solving quadratic equations using reduced unimodular quadratic forms, Mathematics of Computation, vol.74, issue.251, pp.1531-1543, 2005.
DOI : 10.1090/S0025-5718-05-01729-1

URL : http://www.ams.org/mcom/2005-74-251/S0025-5718-05-01729-1/S0025-5718-05-01729-1.pdf

D. Stehlé, BREAKING LITTLEWOOD'S CIPHER, Cryptologia, vol.28, issue.4, pp.341-357, 2004.
DOI : 10.1080/0161-110491892971

D. Stehlé, V. Lefèvre, and P. Zimmermann, Worst cases and lattice reduction, 16th IEEE Symposium on Computer Arithmetic, 2003. Proceedings., pp.142-147, 2003.
DOI : 10.1109/ARITH.2003.1207672

D. Stehlé, V. Lefèvre, and P. Zimmermann, Searching worst cases of a one-variable function using lattice reduction, IEEE Transactions on Computers, vol.54, issue.3, pp.340-346, 2005.
DOI : 10.1109/TC.2005.55

D. Stehlé and P. Zimmermann, A Binary Recursive Gcd Algorithm, Proceedings of the 6th Algorithmic Number Theory Symposium (ANTS VI), pp.411-425, 2004.
DOI : 10.1007/978-3-540-24847-7_31

D. Stehlé and P. Zimmermann, Gal's Accurate Tables Method Revisited, 17th IEEE Symposium on Computer Arithmetic (ARITH'05), pp.257-264, 2005.
DOI : 10.1109/ARITH.2005.24

J. Stein, Computational problems associated with Racah algebra, Journal of Computational Physics, vol.1, issue.3, pp.397-405, 1967.
DOI : 10.1016/0021-9991(67)90047-2

P. H. Sterbenz, Floating Point Computation, 1974.

M. 1. Stogrin, Regular Dirichlet-Voronoï partitions for the second triclinic group, Traduction en Anglais des actes de l'institut Steklov de mathématiques, p.123, 1973.

A. Storjohann, Faster algorithms for integer lattice basis reduction, 1996.

V. Strassen, Gaussian elimination is not optimal, Numerische Mathematik, vol.13, issue.4, pp.354-356, 1969.
DOI : 10.1007/BF02165411

P. P. Tammela, Reduction theory of positive quadratic forms, Journal of Soviet Mathematics, vol.96, issue.2, pp.651-655, 1973.
DOI : 10.1515/crll.1905.129.220

A. The and . Project, CR-Libm, a library of correctly rounded elementary functions in double-precision. Disponible à l'url http

K. Thull and C. K. Yap, A unified approach to HGCD algorithms for polynomials and integers. Disponible à l'url http, 1990.

A. L. Toom, The complexity of a scheme of functional elements realizing the multiplication of integers, Soviet Mathematics Doklady, vol.3, pp.714-716, 1963.

B. Vallée, Une Approche Géométrique de la Réduction des Réseaux en Petite Dimension, 1986.

B. Vallée, Gauss' algorithm revisited, Journal of Algorithms, vol.12, issue.4, pp.556-572, 1991.
DOI : 10.1016/0196-6774(91)90033-U

B. Vallée, Dynamical analysis of a class of Euclidean algorithms, Theoretical Computer Science, vol.297, issue.1-3, pp.447-486, 2003.
DOI : 10.1016/S0304-3975(02)00652-7

G. Voronoï, Nouvelles applications des paramètres continus à la théorie des formes quadratiques, Journal für die reine und angewandte Mathematik, pp.198-287, 1908.

B. L. Van-der-waerden, Die Reduktionstheorie der positiven quadratischen Formen, Acta Mathematica, vol.96, pp.265-309, 1956.
DOI : 10.1007/978-3-0348-6925-6_3

A. Weilert, Asymptotically Fast GCD Computation in ???[i], Proceedings of the 4th Algorithmic Number Theory Symposium (ANTS IV), pp.595-613, 2000.
DOI : 10.1007/10722028_40

J. H. Wilkinson, The Algebraic Eigenvalue Problem, 1988.

D. Wilson, LITTLEWOOD'S CIPHER PART I: A CHALLENGE., Cryptologia, vol.3, issue.2, pp.120-121, 1979.
DOI : 10.1080/0161-117991853927

D. Wilson, LITTLEWOOD'S CIPHER PART II: A METHOD OF SOLUTION, Cryptologia, vol.3, issue.3, pp.172-176, 1979.
DOI : 10.1080/0161-117991854007

C. K. Yap, Fast unimodular reduction: planar integer lattices, Proceedings., 33rd Annual Symposium on Foundations of Computer Science, pp.437-446, 1992.
DOI : 10.1109/SFCS.1992.267808

C. K. Yap, Fundamental Problems in Algorithmic Algebra, 2000.

A. Ziv, Fast evaluation of elementary mathematical functions with correctly rounded last bit, ACM Transactions on Mathematical Software, vol.17, issue.3, pp.410-423, 1991.
DOI : 10.1145/114697.116813