Ask Your Question
0

power_mod strange...

asked 2020-01-27 11:01:37 +0100

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 11:19:39 +0100

rburing gravatar image

updated 2020-01-27 11:25:24 +0100

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 16:04:20 +0100

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 11:01:37 +0100

Seen: 1,086 times

Last updated: Jan 27 '20