AlgoScope

Modular Multiplication

Double and add along the bits of b, reducing every partial result, so nothing exceeds 2m.

Mathematics, algorithm, intermediate
Bit is 1. Adding in, result 6.10110213i
Bit is 1. Adding in, result 6.10110213i

Number Theory Basics: Multiply by doubling and adding, mod 7

Decision, step 2 of 9

This bit is 1, so add the current doubling in: (0 + 6) mod 7 = 6.

How number theory basics works

Cost

Best
O(log b)
Average
O(log b)
Worst
O(log b)
Space
O(1)

Taught by the same lesson

Number Theory Basics covers these too, in the same run.