Question

Computing modular exponentiation efficiently is inevitable for the practicability of RSA. Compute the following exponentiations xe mod m applying the square and-multiply algorithm: 1. x = 2, e = 79, m = 101 2. x = 3, e = 197, m = 101

Answer 1

x = 2, e = 79, m = 101
Using the square and-multiply algorithm:
Initialize y = 1
Convert e to binary form: e = 1001111
For i = 7 to 0, do the following:
y = (y * y) mod m = (y^2) mod m
If the i-th binary digit of e is 1, then y = (y * x) mod m = (y * 2) mod m
The final value of y is the result of the modular exponentiation: x^e mod m = y = 28
x = 3, e = 197, m = 101
Using the square and-multiply algorithm:
Initialize y = 1
Convert e to binary form: e = 110000001
For i = 8 to 0, do the following:
y = (y * y) mod m = (y^2) mod m
If the i-th binary digit of e is 1, then y = (y * x) mod m = (y * 3) mod m
The final value of y is the result of the modular exponentiation: x^e mod m = y = 67