Modular Multiplication
Double and add along the bits of b, reducing every partial result, so nothing exceeds 2m.
Number Theory Basics: Multiply by doubling and adding, mod 7
This bit is 1, so add the current doubling in: (0 + 6) mod 7 = 6.
Cost
- Best
- O(log b)
- Average
- O(log b)
- Worst
- O(log b)
- Space
- O(1)
Before this
Taught by the same lesson
Number Theory Basics covers these too, in the same run.