Modulus Using Binary Exponentiation

The Modulus Using Binary Exponentiation equation is an efficient technique for calculating the result of raising a base to a large exponent and taking the modulus of the result.

INSTRUCTIONS: Enter the following

• (a) Base
• (x) Exponent
• (m) Modulus

Result (n): The result is returned as the result of the large integer mod m

Example

n = 42³¹³ mod 19

• a = 42
• x = 313
• m = 19

313 = (100111001)₂ >>> 2⁸, 2⁵, 2⁴, 2³, 2⁰ = 256, 32, 16, 8, 1

42⁶⁷ mod 19 = (42²⁵⁶ x 42³² x 42¹⁶, 42⁸, 42¹) mod 19 = [(42²⁵⁶ mod 19)(42³² mod 19)(42¹⁶ mod 19)(42⁸ mod 19)(42¹ mod 19)] mod 19 = (9 x 17 x 6 x 5 x 4) mod 19 = 18360 mod 19

= 6