Probabilistic analyses of the plain multiple gcd algorithm

DOI10.1016/J.JSC.2015.08.007zbMATH Open1346.68308OpenAlexW1709787211MaRDI QIDQ898274FDOQ898274

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

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

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)

Cites Work

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

Cited In (9)

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