Modular exponentiation of large number

Question

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?

• Expected Output - 1 or p-1

• SAGE Output - 1

• Python Output - 1047939464127281862631850078334726680804120494559424004614779

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)

Answer 1

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