Square and multiply
Square and multiply is an exponentiation algorithm that repeatedly squares and conditionally multiplies according to the exponent’s binary representation.
Hacking Cryptography
The square-and-multiply method is an efficient exponentiation algorithm that repeatedly squares and selectively multiplies according to the exponent bits.
- How it is used
- Implements modular exponentiation efficiently while exposing a potential timing and power side channel.
- How deep it goes
- Defines the bit-scanning procedure, explains its binary arithmetic, and connects conditional multiplication to exponent-revealing traces.
- Examples
- Uses exponent 42, its binary form 101010, a step table, and an RSA power trace.
- What you can do after
- Evaluate exponentiation implementations for operation-pattern leakage from secret exponent bits.
Read how Hacking Cryptography explains square and multiply →
Elliptic Curve Cryptography for Developers
Square-and-multiply is an exponentiation algorithm that repeatedly squares and conditionally multiplies according to the binary representation of the exponent.
- How it is used
- Computes high powers of polynomials modulo prime polynomials for field extensions, irreducibility tests, and elliptic-curve pairings.
- How deep it goes
- Explains binary decomposition, modular reductions, operation counts, a worked example, and C-style routines, but not side-channel behavior.
- Examples
- Works through x^5 modulo x^2+x+3 over mod 43 and supplies polynomial exponentiation flow and C-style listings.
- What you can do after
- Build it from scratch using modular polynomial multiplication, binary exponent scanning, conditional multiplication, and explicit temporary cleanup.
Read how Elliptic Curve Cryptography for Developers explains square and multiply →
Related concepts
- modular exponentiationimplements · Modular exponentiation is the computation of an integer power followed by reduction modulo a specified integer.
- Montgomery ladderalternative to · The Montgomery ladder is a regular algorithm for scalar multiplication that performs a consistent sequence of additions and doublings to reduce dependence on secret scalar bits.
- binary representationuses · Binary representation expresses information or values using a base-two positional system with two symbols, conventionally zero and one.
- power functionimplements · Exponentiation is the mathematical operation of raising a base to a specified exponent or power.
- irreducible polynomialconfigures · An irreducible polynomial is a nonconstant polynomial that cannot be factored into lower-degree nonconstant polynomials over the specified coefficient field.
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.