Ask Your Question
0

power_mod strange...

asked 2020-01-27 04:01:37 -0500

Jingenbl gravatar image

where is the error?

x = 15

z = power_mod(x,3,23) #z=15^3 mod 23

inverse = inverse_mod(3,23) #1/3 mod 23

assert mod(3*inverse,23)==1 #ok

y = power_mod(z,inverse,23) # y = 15^(3/3) = 15

print(y)

18

Thanks a lot to everyone

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
1

answered 2020-01-27 04:19:39 -0500

rburing gravatar image

updated 2020-01-27 04:25:24 -0500

For exponents there is the relation $x^a \equiv x^{a \mod \varphi(n)} \pmod n$ 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
edit flag offensive delete link more
0

answered 2020-01-27 09:04:20 -0500

Jingenbl gravatar image

thank you so much. I will study this more closely

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-01-27 04:01:37 -0500

Seen: 77 times

Last updated: Jan 27