Euclid's algorithm
Euclid's algorithm computes the greatest common divisor of two integers by repeatedly replacing them with a divisor and the remainder.
Elliptic Curve Cryptography for Developers
The Euclidean algorithm computes the greatest common divisor of two elements by repeatedly replacing a pair with the divisor and remainder.
- How it is used
- Supports polynomial division, gcd computation, irreducible-polynomial discovery, and inversion for elliptic-curve extension fields.
- How deep it goes
- Descends from quotient-and-remainder notation to coefficient-level C loops, edge checks, gcd iteration, and extended inversion.
- Examples
- Demonstrates simple polynomial divisions, degree-based equations, a C division routine, and an inversion main loop.
- What you can do after
- Build it from scratch as a polynomial quotient-remainder routine and use it to implement gcd and modular inversion.
Read how Elliptic Curve Cryptography for Developers explains Euclid's algorithm →
Modern C, Third Edition
Euclid's algorithm is an algorithm for computing the greatest common divisor by repeatedly replacing a pair of integers with a smaller equivalent pair.
- How it is used
- Uses recursion to turn mathematical gcd identities into a compact C algorithm.
- How deep it goes
- Defines gcd, derives subtraction and modulus recurrences, and traces a recursive implementation while stopping short of a full interface.
- Examples
- Uses gcd2 in C, equations for subtraction and remainder, and the recursive call sequence for gcd2(18,30).
- What you can do after
- Build it from scratch as a recursive C function for positive, ordered integer inputs.
Read how Modern C, Third Edition explains Euclid's algorithm →
Modern C
Euclid's algorithm is an algorithm for computing the greatest common divisor of two integers by repeatedly applying remainder operations.
- How it is used
- Uses Euclid's algorithm as a compact example for recursion, function calls, and translating mathematical statements into C algorithms.
- How deep it goes
- Explains the gcd definition, recurrence, preconditions, base case, and recursive C implementation, while deferring detailed assert treatment.
- Examples
- Uses gcd2(18, 30), a recursive call diagram, and short C listings as concrete demonstrations.
- What you can do after
- Build it from scratch as a recursive C function with explicit argument checks, a zero base case, and remainder-based recursion.
Related concepts
- greatest common divisorproduces · A greatest common divisor is a common divisor maximal under divisibility, conventionally selected as positive for integers or monic for polynomials.
- polynomial divisionimplements · Polynomial division expresses a dividend as a divisor multiplied by a quotient plus a remainder of lower degree than the divisor.
- mpz_invertused by · mpz_invert is a GMP function that computes a modular multiplicative inverse when one exists.
- polynomial functionconfigured by · A polynomial function is a function expressible as a finite sum of constant multiples of nonnegative integer powers of one or more variables.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.