Fermat’s Little Theorem
Fermat’s Little Theorem states that for a prime p and integer a not divisible by p, a^(p−1) is congruent to 1 modulo p.
Elliptic Curve Cryptography for Developers
Fermat's little theorem states that a number raised to the appropriate power modulo a prime satisfies a fixed congruence, and its field-extension analogue gives the corresponding finite-field exponent relation.
- How it is used
- Powers modular square-root tests, prime-field square-root algorithms, and exponent calculations in finite-field extensions.
- How deep it goes
- Defines the congruence and translates it into direct exponentiation and Tonelli–Shanks, with detailed code but no proof.
- Examples
- Uses square roots modulo 23 and polynomial powers modulo x² + x + 3 over the prime 43.
- What you can do after
- Apply modular exponentiation to test residues, compute selected square roots, and verify extension-field powers.
Read how Elliptic Curve Cryptography for Developers explains Fermat’s Little Theorem →
Hacking Cryptography
Fermat's little theorem states that for a prime p, every integer a not divisible by p satisfies a^(p−1) ≡ 1 modulo p.
- How it is used
- Supports probabilistic primality testing before generating large asymmetric-key numbers.
- How deep it goes
- Derives equivalent congruences and explains randomized testing, but stops short of a guaranteed primality method.
- Examples
- Uses equations 8.3 and 8.4, random candidate bases, and Carmichael numbers as a failure case.
- What you can do after
- Apply it via a probabilistic primality test that rejects candidates after one failed congruence.
Read how Hacking Cryptography explains Fermat’s Little Theorem →
Related concepts
- power methoduses · A modular square-root technique that obtains the root by exponentiating when the prime modulus is congruent to 3 modulo 4.
- modular square rootuses · A modular square root of a number a is a value x whose square is congruent to a modulo a specified modulus.
- field extensionused by · A field extension is a field that contains a given base field as a subfield and adds elements needed for further algebraic operations.
- irreducible polynomialaddresses · An irreducible polynomial is a nonconstant polynomial that cannot be factored into lower-degree nonconstant polynomials over the specified coefficient field.
- square rootaddresses · A square root is a value whose square equals a specified value; for a nonnegative real value, the principal square root is nonnegative.
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.