Multiplications in fast exponentiation
You compute by left-to-right binary (square-and-multiply) exponentiation, run exactly as follows: read the exponent's bits from the most significant down; initialize the running result to , which consumes the leading -bit for free (no multiply); then for each remaining lower bit, square the running result, and — only where that bit is — also multiply by . Counting every squaring and every multiply-by-, exactly how many multiplications does the whole computation take?
Show hints (2)+
- Write : count its bit-length and its number of -bits.
- Squarings ; extra multiplies ; add them.
Answer
Reveal answer →Final answer
8
Want the full step-by-step worked solution? It's part of Premium — along with a worked solution for every question in the bank.
Asked at: Jane Street, Two Sigma