CODEWITHSUNDEEP
pythoncryptographysagelargenumbermodular-arithmetic
edhi wiyoto
edhi wiyoto

Reputation: 23

Modular exponentiation of large number

I'm currently working with a large number for cryptography.

a = 3087646334 

p = 1606938044258990275541962092341162602522202993782792835301611

b = int((p-1)/2).

Euler's Criterion says that

a^b (mod p) = 1 or a^b (mod p) = p-1.

SAGE gives the correct answer and python gives wrong answer. Why is that?

The code is in below.

Sage

a = 3087646334 
p = 1606938044258990275541962092341162602522202993782792835301611
b = int((p-1)/2)

power_mod(a,b,p)

Python

a = 3087646334
p = 1606938044258990275541962092341162602522202993782792835301611
b = int((p-1)/2)

pow(a,b,p)

Upvotes: 2

Views: 972

Answers (1)

Kelly Bundy
Kelly Bundy

Reputation: 27640

Because you're using float division, which is inaccurate. Use b = (p-1) // 2 instead.

Upvotes: 2

Related Questions