Greatest common divisor
A greatest common divisor is a common divisor maximal under divisibility, conventionally selected as positive for integers or monic for polynomials.
Elliptic Curve Cryptography for Developers
The greatest common divisor of polynomials is a highest-degree polynomial that divides each given polynomial, defined up to multiplication by a nonzero constant.
- How it is used
- Supports irreducible-polynomial searches and polynomial-field operations needed for elliptic-curve slopes and pairings.
- How deep it goes
- Explains zero cases, degree ordering, remainder iteration, termination, and C-style implementation, stopping short of a numeric worked polynomial.
- Examples
- Uses a simple Euclidean remainder progression and C listings for initialization, the main loop, termination, and cleanup.
- What you can do after
- Build it from scratch using polynomial division remainders and handle zero inputs, degree ordering, constants, and resource cleanup.
Read how Elliptic Curve Cryptography for Developers explains greatest common divisor →
Modern C, Third Edition
The greatest common divisor of two positive integers is the greatest positive integer that divides both of them.
- How it is used
- Uses gcd as a concrete example for recursion, function calls, local variables, and translating mathematical statements into algorithms.
- How deep it goes
- Defines gcd, states two recursive identities, and implements Euclid’s algorithm, while noting that the initial interface assumes valid positive arguments.
- Examples
- Demonstrates recursive gcd2(18, 30) calls and a C implementation using assertions, remainder calculation, and a zero-remainder base case.
- What you can do after
- Build it from scratch in C by applying Euclid’s remainder rule recursively to positive integer arguments.
Read how Modern C, Third Edition explains greatest common divisor →
Related concepts
- polynomial contentequivalent to · The content of a polynomial is the common factor of its coefficients, typically normalized according to the coefficient domain.
- Euclid's algorithmproduced by · Euclid's algorithm computes the greatest common divisor of two integers by repeatedly replacing them with a divisor and the remainder.
- common-factors attackused by · A cryptanalytic attack that factors RSA moduli by finding a prime factor shared by two public keys.
- pure functionkind of · A pure function is a function whose output is determined solely by its explicit inputs and whose evaluation has no externally observable side effects.
- remainder operationuses · A remainder operation returns the residual left after dividing one value or algebraic expression by another under the applicable division rules.
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.