Live briefing
Everything about Binary GCD algorithm
Algorithm for computing the greatest common divisor
The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor (GCD) of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Binary GCD algorithmA 5-minute orientation
- Pick up a classic book: Algorithm Design and ApplicationsThe most-reprinted book on the subject
- Read the landmark paper: (1 +i) - ary GCD Computation inZ[ i ]as an Analogue to the Binary GCD AlgorithmCited 11 times
- Go sideways: Greatest common divisorA closely related topic
- Go sideways: Extended Euclidean algorithmA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
(1 +i) - ary GCD Computation inZ[ i ]as an Analogue to the Binary GCD Algorithm
Analysis of a Left-Shift Binary GCD Algorithm
Memory Tampering Attack on Binary GCD Based Inversion Algorithms
Existence of a limiting distribution for the binary GCD algorithm
Binary GCD algorithm for computing error locator polynomials in Reed-Solomon decoding
GCD of Aunu Binary Polynomials of Cardinality Seven Using Extended Euclidean Algorithm
Multi-exponentiation algorithm based on binary GCD computation and its application to side-channel countermeasure
📚 Books worth reading
Algorithm Design and ApplicationsMichael T. Goodrich, Roberto Tamassia · 2014
প্রোগ্রামিং কনটেস্টমোঃ মাহবুবুল হাসান · 2016
From Mathematics to Generic ProgrammingAlexander A. Stepanov, Daniel E. Rose · 2015
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Greatest common divisor In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the…
- Extended Euclidean algorithm In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest…
- Euclidean algorithm In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers…
- Modular multiplicative inverse In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent…
- Polynomial greatest common divisor In algebra, the greatest common divisor (frequently abbreviated GCD or gcd) of two polynomials is a polynomial, of the highest possible degree, which is…
- Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way…
- Montgomery modular multiplication In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing…
- Shanks's square forms factorization Shanks' square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method. The…