Probabilistic analyses of the plain multiple gcd algorithm

DOI10.1016/J.JSC.2015.08.007MaRDI QIDQ898274zbMATH OpenOpenAlexFDO

Authors Valérie Berthé, Loïck Lhote, Brigitte Vallée

Publication date 8 December 2015

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2015.08.007

zbMATH Keywords

analysis of algorithmsgenerating functionstransfer operatoranalytic combinatoricslimit lawsPerron formuladynamical analysisLandau theorembeta lawgcd algorithms

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Analysis of algorithms (68W40) Combinatorial probability (60C05) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• Multiple GCDs. Probabilistic analysis of the plain algorithm
• Probabilistic computation of integer polynomial GCDs
• On computation of the greatest common divisor of several polynomials over a finite field.
• Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms
• Gaussian laws for the main parameters of the Euclid algorithms

Cites work

• scientific article; zbMATH DE number 3581610 (Why is no real title available?)
• scientific article; zbMATH DE number 473229 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 1503600 (Why is no real title available?)
• Algorithmic Number Theory
• Analysis of Euclidean algorithms for polynomials over finite fields
• Analytic combinatorics
• Continued fraction algorithms, functional operators, and structure constants
• Euclidean algorithms are Gaussian
• Euclidean dynamics
• Fast computation of continued fraction expansions.
• GCD of random linear combinations
• Gaussian laws for the main parameters of the Euclid algorithms
• Multiple GCDs. Probabilistic analysis of the plain algorithm
• On continued fraction expansions in positive characteristic: equivalence relations and some metric properties
• On the reduction of a random basis
• On the thermodynamic formalism for the Gauss map
• Riemann's zeta function
• The exact length of the Euclidean algorithm in [ X ]
• The number of steps in the Euclidean algorithm
• The number of steps in the Euclidean algorithm
• The statistics of continued fractions for polynomials over a finite field
• Thermodynamic Formalism

Cited in

(9)

• Asymptotic analysis of regular sequences
• Analysis of summatory functions of regular sequences: transducer and Pascal's rhombus
• Gaussian behavior of quadratic irrationals
• Analysis of generalized continued fraction algorithms over polynomials
• Storage efficient algorithm for Hermite normal form using LLL
• Probabilistic computation of integer polynomial GCDs
• The Brun gcd algorithm in high dimensions is almost always subtractive
• Algorithms and Computation
• Multiple GCDs. Probabilistic analysis of the plain algorithm

This page was built for publication: Probabilistic analyses of the plain multiple gcd algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898274)