True or false: "Square and Multiply is an algorithm to multiply very quickly."

False — Square and Multiply (SAM) is an algorithm for efficient modular exponentiation, not multiplication. It computes $a^m \mod N$ efficiently.

What SAM actually does:

• Computes $a^m \mod N$ using only ~$\log_2(m)$ squarings and ~$\log_2(m)/2$ multiplications
• For a 3072-bit RSA exponent: ~3071 squarings + ~1535 multiplications ≈ 4600 operations
• Without SAM: $2^{3072}$ sequential multiplications — completely impossible

How it works:

1. Convert exponent $m$ to binary
2. Process each bit left-to-right: Square for every bit, additionally Multiply by $a$ for each "1" bit
3. Reduce mod N after every operation

The key insight: SAM exploits the binary representation of the exponent to turn an exponential number of multiplications into a linear number. It doesn't make individual multiplications faster — it reduces how many are needed.

Go deeper:

• Exponentiation by squaring (Wikipedia) — what SAM really does — fast exponentiation, not multiplication.