On Schönhage's algorithm and subquadratic integer gcd computation

DOI10.1090/S0025-5718-07-02017-0zbMath1165.11003WikidataQ55899112 ScholiaQ55899112MaRDI QIDQ5429518

Niels Moller

Publication date: 30 November 2007

Published in: Mathematics of Computation (Search for Journal in Brave)

zbMATH Keywords

complexity; GCD algorithm; subquadratic algorithm; Schönhage's algorithm

Mathematics Subject Classification ID

11Y16: Number-theoretic algorithms; complexity

11A05: Multiplicative structure; Euclidean algorithm; greatest common divisors

Related Items

An O(M(n) logn) Algorithm for the Jacobi Symbol, Phragmén's voting methods and justified representation, Complexity of computation in finite fields, Scheduling results applicable to decision-theoretic troubleshooting, Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms, Towards faster polynomial-time lattice reduction, Holonomic gradient method for two-way contingency tables, Statistics of Different Reduction Types of Fermat Curves, Faster deterministic integer factorization, ALGORITHMS TO IDENTIFY ABUNDANTp-SINGULAR ELEMENTS IN FINITE CLASSICAL GROUPS, A multimodular algorithm for computing Bernoulli numbers, The Erdős–Moser equation $1^{k}+2^{k}+\dots+(m-1)^{k}=m^{k}$ revisited using continued fractions

Uses Software

• gmp

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers
• Computational problems associated with Racah algebra
• Fast computation of continued fraction expansions.
• Two Fast GCD Algorithms
• The accelerated integer GCD algorithm
• Acceleration of Euclidean algorithm and extensions
• Algorithmic Number Theory
• Euclid's Algorithm for Large Numbers