Search

Your search keyword '"Hanrot, Guillaume"' showing total 126 results
Start Over Author "Hanrot, Guillaume"
126 results on '"Hanrot, Guillaume"'

1. Plaintext-Ciphertext Matrix Multiplication and FHE Bootstrapping: Fast and Fused

Author

Bae, Youngjin, Cheon, Jung Hee, Hanrot, Guillaume, Park, Jai Hyun, Stehlé, Damien, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Reyzin, Leonid, editor, and Stebila, Douglas, editor

Published
2024
Full Text
View/download PDF

2. Approx-SVP in Ideal Lattices with Pre-processing

Author

Pellet-Mary, Alice, Hanrot, Guillaume, Stehlé, Damien, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Ishai, Yuval, editor, and Rijmen, Vincent, editor

Published
2019
Full Text
View/download PDF

3. Markov Chain Monte Carlo Algorithms for Lattice Gaussian Sampling

Author

Wang, Zheng, Ling, Cong, and Hanrot, Guillaume

Subjects
Computer Science - Information Theory
Abstract

Sampling from a lattice Gaussian distribution is emerging as an important problem in various areas such as coding and cryptography. The default sampling algorithm --- Klein's algorithm yields a distribution close to the lattice Gaussian only if the standard deviation is sufficiently large. In this paper, we propose the Markov chain Monte Carlo (MCMC) method for lattice Gaussian sampling when this condition is not satisfied. In particular, we present a sampling algorithm based on Gibbs sampling, which converges to the target lattice Gaussian distribution for any value of the standard deviation. To improve the convergence rate, a more efficient algorithm referred to as Gibbs-Klein sampling is proposed, which samples block by block using Klein's algorithm. We show that Gibbs-Klein sampling yields a distribution close to the target lattice Gaussian, under a less stringent condition than that of the original Klein algorithm., Comment: 5 pages, 1 figure, IEEE International Symposium on Information Theory(ISIT) 2014

Published
2014
Full Text
View/download PDF

4. Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases

Author

Hanrot, Guillaume and Stehlé, Damien

Subjects
Mathematics - Number Theory, Computer Science - Computational Complexity, Computer Science - Cryptography and Security
Abstract

The Hermite-Korkine-Zolotarev reduction plays a central role in strong lattice reduction algorithms. By building upon a technique introduced by Ajtai, we show the existence of Hermite-Korkine-Zolotarev reduced bases that are arguably least reduced. We prove that for such bases, Kannan's algorithm solving the shortest lattice vector problem requires $d^{\frac{d}{2\e}(1+o(1))}$ bit operations in dimension $d$. This matches the best complexity upper bound known for this algorithm. These bases also provide lower bounds on Schnorr's constants $\alpha_d$ and $\beta_d$ that are essentially equal to the best upper bounds. Finally, we also show the existence of particularly bad bases for Schnorr's hierarchy of reductions.

Published
2008

5. Improved Analysis of Kannan's Shortest Lattice Vector Algorithm

Author

Hanrot, Guillaume and Stehlé, Damien

Subjects
Computer Science - Cryptography and Security, Computer Science - Computational Complexity
Abstract

The security of lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of computing a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complexity estimates have not been improved since more than twenty years. Kannan's algorithm for solving the shortest vector problem is in particular crucial in Schnorr's celebrated block reduction algorithm, on which are based the best known attacks against the lattice-based encryption schemes mentioned above. Understanding precisely Kannan's algorithm is of prime importance for providing meaningful key-sizes. In this paper we improve the complexity analyses of Kannan's algorithms and discuss the possibility of improving the underlying enumeration strategy.

Published
2007
Full Text
View/download PDF

6. Time- and Space-Efficient Evaluation of Some Hypergeometric Constants

Author

Cheng, Howard, Hanrot, Guillaume, Thomé, Emmanuel, Zima, Eugene, and Zimmermann, Paul

Subjects
Computer Science - Symbolic Computation
Abstract

The currently best known algorithms for the numerical evaluation of hypergeometric constants such as $\zeta(3)$ to $d$ decimal digits have time complexity $O(M(d) \log^2 d)$ and space complexity of $O(d \log d)$ or $O(d)$. Following work from Cheng, Gergel, Kim and Zima, we present a new algorithm with the same asymptotic complexity, but more efficient in practice. Our implementation of this algorithm improves slightly over existing programs for the computation of $\pi$, and we announce a new record of 2 billion digits for $\zeta(3)$.

Published
2007

9. Analyzing Blockwise Lattice Algorithms Using Dynamical Systems

Author

Hanrot, Guillaume, Pujol, Xavier, Stehlé, Damien, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Rogaway, Phillip, editor

Published
2011
Full Text
View/download PDF

10. Algorithms for the Shortest and Closest Lattice Vector Problems

Author

Hanrot, Guillaume, Pujol, Xavier, Stehlé, Damien, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Chee, Yeow Meng, editor, Guo, Zhenbo, editor, Ling, San, editor, Shao, Fengjing, editor, Tang, Yuansheng, editor, Wang, Huaxiong, editor, and Xing, Chaoping, editor

Published
2011
Full Text
View/download PDF

12. Accelerating Lattice Reduction with FPGAs

Author

Detrey, Jérémie, Hanrot, Guillaume, Pujol, Xavier, Stehlé, Damien, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Abdalla, Michel, editor, and Barreto, Paulo S. L. M., editor

Published
2010
Full Text
View/download PDF

13. Primality Proving with Elliptic Curves

Author

Théry, Laurent, Hanrot, Guillaume, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Schneider, Klaus, editor, and Brandt, Jens, editor

Published
2007
Full Text
View/download PDF

16. Integer points close to a transcendental curve and correctly-rounded evaluation of a function

Author

Brisebarre, Nicolas, Hanrot, Guillaume, Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon), ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020), ANR-10-BLAN-0203,TaMaDi,Dilemme du Fabricant de Tables(2010), ANR-14-CE25-0018,Fast Relax,Approximation rapide et fiable(2014), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Arithmétiques des ordinateurs, méthodes formelles, génération de code (ARIC), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), and École normale supérieure de Lyon (ENS de Lyon)

Subjects
algorithmic number theory, AMS 2020 : Primary 11Y99, 41A05, 65G50, Secondary 11D75, 11J25, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, lattice basis reduction, LLL algorithm, correct rounding, Computer arithmetic, approximation theory, [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT]
Abstract

Despite several significant advances over the last 30 years, guaranteeing the correctly rounded evaluation of elementary functions, such as $\cos, \exp, \sqrt[3]{\cdot}$ for instance, is still a difficult issue. This can be formulated as a Diophantine approximation problem, called the Table Maker’s Dilemma, which consists in determining points with integer coordinates that are close to a curve. In this article, we propose two algorithmic approaches to tackle this problem, closely related to a celebrated work by Bombieri and Pila and to the so-called Coppersmith's method. We establish the underlying theoretical foundations, prove the algorithms, study their complexity and present practical experiments; we also compare our approach with previously existing ones. In particular, our results show that the development of a correctly rounded mathematical library for the binary128 format is now possible at a much smaller cost than with previously existing approaches.

Published
2021

24. MPFR: a multiple-precision binary floating-point library with correct rounding

Author

Fousse, Laurent, Hanrot, Guillaume, Lefevre, Vincent, Pelissier, Patrick, and Loria, Paul Zimmermann

Subjects
Algorithm, Libraries -- Analysis, Algorithms -- Usage, Floating-point arithmetic -- Analysis
Abstract

This article presents a multiple-precision binary floating-point library, written in the ISO C language, and based on the GNU MP library. Its particularity is to extend to arbitrary-precision, ideas from the IEEE 754 standard, by providing correct rounding and exceptions. We demonstrate how these strong semantics are achieved--with no significant slowdown with respect to other arbitrary-precision tools--and discuss a few applications where such a library can be useful. Categories and Subject Descriptors: D.3.0 [Programming Languages]: General--Standards; G.1.0 [Numerical Analysis]: General--Computer arithmetic, multiple precision arithmetic; G.1.2 [Numerical Analysis]: Approximation--Elementary approximation, special function approximation; G.4 [Mathematical Software]: Algorithm design and analysis, efficiency, portability General Terms: Algorithms, Standardization, Performance Additional Key Words and Phrases: Multiple-precision arithmetic, [EEE 754 standard, floating-point arithmetic, correct rounding, elementary function, portable software

Published
2007

25. Algorithmic Number Theory. 9th. International Symposium, ANTS-IX. Nancy, France, July 2010. Proceedings

Author

Hanrot, Guillaume, Morain, François, Thomé, Emmanuel, Computer arithmetic (ARENAIRE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Algorithmic number theory for cryptology (TANC), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Cryptology, Arithmetic: Hardware and Software (CARAMEL), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Guillaume Hanrot and François Morain and Emmanuel Thomé, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], ComputingMilieux_MISCELLANEOUS, [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT]
Abstract

International audience

Published
2010

26. Floating-Point $L^2$-Approximations

Author

Brisebarre, Nicolas, Hanrot, Guillaume, Computer arithmetic (ARENAIRE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques de l'Université de Saint-Etienne (LAMUSE), Université Jean Monnet - Saint-Étienne (UJM), Curves, Algebra, Computer Arithmetic, and so On (CACAO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Peter Kornerup and Jean-Michel Muller, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université Jean Monnet [Saint-Étienne] (UJM)

Subjects
[INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic
Abstract

International audience; Computing good polynomial approximations to usual functions is an important topic for the computer evaluation of those functions. These approximations can be good under several criteria, the most desirable being probably that the relative error is as small as possible in the $L^{\infty}$ sense, i.e. everywhere on the interval under study. In the present paper, we investigate a simpler criterion, the $L^2$ case. Though finding a best polynomial $L^2$-approximation with real coefficients is quite easy, we show that if the coefficients are restricted to be floating point numbers to some precision, the problem becomes a general instance of the CVP problem, and hence is NP-hard. We investigate the practical behaviour of exact and approximate algorithms for this problem. The conclusion is that it is possible in a short amount of time to obtain a relative or absolute best $L^2$-approximation. The main applications are for large dimension, as a preliminary step of finding $L^{\infty}$-approximations and for functions with large variations, for which relative best approximation is by far more interesting than absolute.

Published
2007

27. Proceedings of the 7th Conference on Real Numbers and Computers (RNC'7)

Author

Hanrot, Guillaume, Zimmermann, Paul, Solving problems through algebraic computation and efficient software (SPACES), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), and Guillaume Hanrot, Paul Zimmermann

Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract

These are the proceedings of RNC7.

Published
2006

28. MPFR: A Multiple-Precision Binary Floating-Point Library With Correct Rounding

Author

Fousse, Laurent, Hanrot, Guillaume, Lefèvre, Vincent, Pélissier, Patrick, Zimmermann, Paul, Solving problems through algebraic computation and efficient software (SPACES), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), and INRIA

Subjects
CORRECT ROUNDING, ELEMENTARY FUNCTION, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], MULTIPLE-PRECISION ARITHMETIC, ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.0: General/G.1.0.4: Multiple precision arithmetic, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], PORTABLE SOFTWARE, FLOATING-POINT ARITHMETIC, IEEE-754 STANDARD
Abstract

This paper presents a multiple-precision binary floating-point library, written in the ISO C language, and based on the GNU MP library. Its particularity is to extend ideas from the IEEE-754 standard to arbitrary precision, by providing correct rounding and exceptions. We demonstrate how these strong semantics are achieved | with no signicant slowdown with respect to other tools | and discuss a few applications where such a library can be useful.

Published
2005

29. Quelques idées sur l'algorithmique des équations diophantiennes

Author

Hanrot, Guillaume, Solving problems through algebraic computation and efficient software (SPACES), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Nicole Berline, Alain Plagne, Claude Sabbah, and Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)

Subjects
algorithmic number theory, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], diophantine equations, [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT]
Published
2005

35. The Middle Product Algorithm, I

Author

Hanrot, Guillaume, Quercia, Michel, Zimmermann, Paul, Solving problems through algebraic computation and efficient software (SPACES), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), and INRIA

Subjects
DIVISION, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], SQUARE ROOT, INVERSION, NEWTON'S METHOD, MIDDLE PRODUCT
Abstract

We present new algorithms for the inverse, division, and square root of power series. The key trick is a new algorithm --- MiddleProduct or, for short, MP --- computing the n middle coefficients of a (2n-1)*n full product in the same number of multiplications as a full n*n product. This improves previous work of Brent, Mulders, Karp and Markstein, Burnikel and Ziegler. A forthcoming paper will study the floating-point case.

Published
2002

36. Sur l'équation diophantienne $(x^n - 1)/(x - 1)=y^q$, III

Author

Bugeaud, Yann, Hanrot, Guillaume, Mignotte, Maurice, Université Louis Pasteur - Strasbourg I, Polynomials, Combinatorics, Arithmetic (POLKA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Université Louis Pasteur - Strasbourg 1 (ULP), and Loria, Publications

Subjects
[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], superelliptic equations, diophantine equations, équations diophantiennes, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], équations superelliptiques
Abstract

Article dans revue scientifique avec comité de lecture.; Nous étudions dans ce travail l'équation du titre, introduite par Ljunggren et Nagell durant la première moitié du siècle. Nous présentons une méthode qui permet d'une part, à $n$ fixé, de donner une borne pour $q$, et par ailleurs, $n$ et $q$ étant donnés, d'obtenir des bornes pour $x$ et $y$ bien plus précises que celles provenant de la théorie des formes linéaires en logarithmes. Nous montrons également comment utiliser ces bornes même lorsqu'elles sont trop grandes pour permettre une énumération exhaustive des valeurs de $x$ possibles. En utilisant toutes ces techniques, nous sommes à même de résoudre complètement l'équation dans un bon nombre de cas, en particulier quand $5$ ou $7$ divise $n$, ou encore quand $n$ a un diviseur premier inférieur ou égal à $23$ distinct de $q$.

Published
2002

37. A long note on Mulders' short product

Author

Hanrot, Guillaume, Zimmermann, Paul, Solving problems through algebraic computation and efficient software (SPACES), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP), INRIA, and Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
KARATSUBA MULTIPLICATION, POWER SERIES, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], SHORT PRODUCT
Abstract

The short product of two power series is the meaningful part of the product of these objects, i.e., _i+j < n a_ib_j x^i+j. In , Mulders gives an algorithm to compute a short product faster than the full product in the case of Karatsuba's multiplication . This algorithm work by selecting a cutoff point k and performing a full kk product and two (n-k)(n-k) short products recursively. Mulders also gives an heuristically optimal cutoff point n. In this paper, we determine the optimal cutoff point in Mulders' algorithm. We also give a slightly more general description of Mulders' method.

Published
2002

38. Speeding up the inversion of power series

Author

Hanrot, Guillaume, Zimmermann, Paul, Polynomials, Combinatorics, Arithmetic (POLKA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
méthode de karatsuba, séries formelles, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], newton method, méthode de newton, karatsuba algorithm, power series
Abstract

Rapport interne.; We present a new algorithm to compute the $n$ middle coefficients of a $2n \times n$ product in $K(n)$ ring operations, where $K(n)$ is the number of operations needed by Karatsuba's algorithm for a full $n \times n$ product. Used in Newton iteration, and together with previous work of Mulders, Karp and Markstein, this algorithm enables one to compute an inverse in $\sim 0.904 \, K(n)$ operations, a quotient in $\sim 1.173 \, K(n)$ operations, and a square root in $\sim 0.891 \, K(n)$ operations. These results apply both to power series and polynomials.

Published
2000

39. Sur l'équation diophantienne $\frac{ x^n - 1}{x - 1} = y^q$, III

Author

Bugeaud, Yann, Hanrot, Guillaume, Mignotte, Maurice, Polynomials, Combinatorics, Arithmetic (POLKA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), INRIA, and Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)

Subjects
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], équation diophantiennes, équations superelliptiques
Abstract

Nous étudions dans ce travail l'équation du titre, introduite par Ljunggren et Nagell durant la première moitié du siècle. Nous présentons une méthode qui permet d'une part, à n fixé, de donner une borne pour q, et par ailleurs, n et q étant donnés, d'obtenir des bornes pour x et y bien plus précises que celles provenant de la théorie des formes linéaires en logarithmes. Nous montrons également comment utiliser ces bornes même lorsqu'elles sont trop grandes pour permettre une énumération exhaustive des valeurs de x possibles. En utilisant toutes ces techniques, nous sommes à même de résoudre complètement l'équation dans un bon nombre de cas, en particulier quand 5 ou 7 divise n, ou encore quand n a un diviseur premier inférieur ou égal à 23 distinct de q.

Published
1999

40. Existence of Primitive Divisors of Lucas and Lehmer Numbers

Author

BILU, Yuri, HANROT, Guillaume, VOUTIER, Paul, Polynomials, Combinatorics, Arithmetic (POLKA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), and INRIA

Subjects
diophantine equations, linear form in logarithms, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], thue equations, linear recurrence sequence
Abstract

We prove that for $n$ > 30, every $n$-th Lucas and Lehmer number has a primitive divisor. This allows us to list all Lucas and Lehmer numbers without a primitive divisor.

Published
1999

41. Un nouveau critère pour l'équation de Catalan

Author

Bugeaud, Yann, Hanrot, Guillaume, Polynomials, Combinatorics, Arithmetic (POLKA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), INRIA, and Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)

Subjects
équations diophantiennes, équation de Catalan, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], équations superelliptiques
Abstract

Nous présentons dans ce travail une méthode, issue de travaux de Bilu et de Bilu et Hanrot, qui permet, sous certaines conditions, de borner de façon bien plus précise que par la méthode de Baker les solutions d'équations diophantiennes superelliptiques. Cette méthode s'applique en particulier à l'équation de Catalan |x^p -y^q| = 1, où q > p sont deux premiers, et nous permet de prouver que cette dernière n'a pas de solution non triviale quand q ne divise pas h^-(\Q(\zeta_p)).

Published
1999

45. MPFR

Author

Fousse, Laurent, primary, Hanrot, Guillaume, additional, Lefèvre, Vincent, additional, Pélissier, Patrick, additional, and Zimmermann, Paul, additional

Published
2007
Full Text
View/download PDF

48. Primality Proving with Elliptic Curves.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Schneider, Klaus, Brandt, Jens, Théry, Laurent, and Hanrot, Guillaume

Abstract

Elliptic curves are fascinating mathematical objects. In this paper, we present the way they have been represented inside the Coq system, and how we have proved that the classical composition law on the points is internal and gives them a group structure. We then describe how having elliptic curves inside a prover makes it possible to derive a checker for proving the primality of natural numbers. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results