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

complexityGCD algorithmsubquadratic algorithmSchönhage's algorithm

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05)

Related Items

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

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