Exercise 2: Naive vs. Fast Multiplication Count for b = 10,000 — Possible Solution ==================================================================== NAIVE APPROACH ------------------------------ The naive approach needs exactly one multiplication per unit of the exponent: 10,000 multiplications. FAST APPROACH ------------------------------ 10000 in binary is 10011100010000 - 14 bits total, with 4 of those bits set to 1 (checked directly: 10011100010000 has four 1s). The fast approach needs one squaring per bit position (14 squarings, one for each of the 14 bits) plus one extra multiply for each bit that is actually 1 (4 extra multiplies). Total: 14 + 4 = 18 multiplications from squarings and bit-multiplies, though the very last squaring after the final bit is processed doesn't feed into anything further and could optionally be skipped - some implementations still perform it depending on the loop structure, in which case the count is 19 as computed directly. Both figures are dramatically smaller than the naive count either way. Rough estimate using log2(10000) is approximately 13.3, close to the bit-length count of 14 used above - the log2 estimate is a good rule of thumb even where the exact figure depends slightly on implementation details (how many of the exponent's own bits happen to be 1, and whether a final unused squaring is counted). RATIO ------------------------------ Using the naive count (10,000) against the fast count (18-19): 10000 / 19 ~ 526 RESULT ------------------------------ The naive approach needs roughly 500x more multiplications than the fast approach for this exponent - and this gap grows even more dramatically as the exponent gets larger, exactly as this chapter's own RSA-scale comparison showed. WHY THIS WORKS AS AN ANSWER ------------------------------ The fast count is derived from 10000's own actual binary representation (its bit length and its number of set bits) rather than only using the log2 approximation, while still connecting the exact count back to the log2 estimate this chapter also uses, and the ratio is computed directly from real numbers rather than estimated loosely.