Extended Euclidean algorithm
The extended Euclidean algorithm computes the greatest common divisor of elements and coefficients expressing it as their linear combination.
Hacking Cryptography
The extended Euclidean algorithm computes greatest common divisors and coefficients expressing them as linear combinations of integers.
- How it is used
- Computes RSA’s private exponent as the modular inverse of a coprime public exponent.
- How deep it goes
- Defines the EEA’s GCD role and demonstrates its RSA result, but does not detail the algorithm’s iterative steps.
- Examples
- Uses p = 193, q = 727, e = 17653, φ(n) = 139392, and d = 77533.
- What you can do after
- Evaluate RSA key generation by computing and verifying a modular inverse with the EEA.
Read how Hacking Cryptography explains extended Euclidean algorithm →
Elliptic Curve Cryptography for Developers
The extended Euclidean algorithm computes a greatest common divisor together with coefficients expressing it as a linear combination of the input elements.
- How it is used
- Applies polynomial inversion and division to extension-field elliptic-curve arithmetic and pairing algorithms.
- How deep it goes
- Derives initialization, quotient-remainder updates, normalization, termination, and the maintained invariant, but omits a full concrete computation.
- Examples
- Uses a simple polynomial inversion computation and the reduction of division to inversion followed by multiplication.
- What you can do after
- Apply polynomial inversion modulo an irreducible polynomial and implement division as inversion followed by multiplication.
Read how Elliptic Curve Cryptography for Developers explains extended Euclidean algorithm →
Related concepts
- algorithmkind of · An algorithm is a finite, precisely specified procedure for performing a computation, transforming inputs into outputs, or solving a problem.
- inverseproduces · An inverse is a value or operation that reverses the effect of another value or operation under a specified composition rule.
- private keyproduces · A private key is the secret component of an asymmetric cryptographic key pair used by its holder for operations such as authentication, decryption, or digital signing.
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.