Inputs
Any integer.
Non-negative integer.
Integer ≥ 2.
Try
Result
7^644 mod 645
1
7^644 ≡ 1 (mod 645)
- Bits in b
- 10
- Squarings
- 9
- Multiplies
- 4
- Naive cost
- 643
Square-and-multiply steps
Exponent b = in binary, :
Operation sequence:
The bits of b are read most significant first. The first bit only sets the accumulator to a mod n. Every bit after that squares the accumulator (S), and a 1 bit also multiplies it by a (SM). Every result along the way is reduced mod n.