Revision history [back]

You probably want (p-3)/4 instead of (p-1)/4 in the definition of x1, since this affectation takes place only if the if clause failed, meaning that (p - 3) % 4 is zero.

The reason it works in Python is that in Python, if k is an integer, k / 4 returns the integer part of k over 4, while in Sage, it returns a rational. The error message said:

TypeError: unable to convert x (=1146...9104*(1205...3824*sqrt(42))) to an integer

which tells you a square root was being extracted, and this could only happen at the exponentiation step mp**((p-1)/4) (in your example, (p-1)/4 is a half-integer).

Note that you can force integer division by using // instead of /, so you could write x1 = mp**((p-1)//4) % p.

Combining these two tricks, your code becomes:

sage: def decriptograph(n,m):
....:         p, q = factor(n)
....:         p, q = p[0], q[0]
....:         mp, mq = m % p, m % q
....:         if (p - 3) % 4 or (q - 3) % 4:
....:                 return -1
....:         x1 = mp ** ((p - 3) // 4) % p
....:         return x1
....: 
sage: decriptograph(328419349,249500293)
5641