Revision history [back]

For exponents there is the relation $x^a \equiv x^{a \mod \varphi(n)} \pmod n$ where $\varphi$ is Euler's phi function.

You confused $\varphi(n)$ with $n$. Here is a correction of your code, using $\varphi = {}$euler_phi:

x = 15
z = power_mod(x,3,23) #z=15^3 mod 23
inverse = inverse_mod(3,euler_phi(23)) #1/3 mod phi(23)
assert mod(3*inverse,euler_phi(23))==1 #ok
y = power_mod(z,inverse,23) # y = 15^(3/3) = 15
print(y)

Output:

15

For exponents there is the relation $x^a \equiv x^{a \mod \varphi(n)} \pmod n$ where if $\gcd(x,n)=1$; here $\varphi$ is Euler's phi function, and we use Euler's theorem.

You confused $\varphi(n)$ with $n$. Here is a correction of your code, using $\varphi = {}$euler_phi:

x = 15
z = power_mod(x,3,23) #z=15^3 mod 23
inverse = inverse_mod(3,euler_phi(23)) #1/3 mod phi(23)
assert mod(3*inverse,euler_phi(23))==1 #ok
y = power_mod(z,inverse,23) # y = 15^(3/3) = 15
print(y)

Output:

15