Modular exponent algorithm

This algorithm has a polynomial run time in the size of the input to calculate powers in using modular arithmetic. This has not been sped up using Euler’s theorem (modular arithmetic).

Algorithm

resursive_mod_exp(x,y,N):
	Input: n-bit integers x,y,N >= 0
	Ouput: x^y mod N
1. if y = 0, return 1
2. z = resursive_mod_exp(x, floor(y/2), N)
3. if y is even return z^2 mod N
4. if y is off return xz^2 mod N

Run time

The algorithm runs for at most loops as is an -bit integer. Calculating multiplication of -bit integers takes . Therefore this algorithm runs in time.

Correctness

This derives from basic properties of modular arithmetic.