Context
The decryption math formula for the El Gamal method is the following:
m = ab^(-k) mod p
Specifically in Python, I want to compute the following equivalent:
>>> m = (b**(-k) * a) % p
The issue in the above Python code is that the numbers inserted would overflow or result in 0.0 due to precision. Consider the following example:
>>> (15653**(-3632) * 923) % 262643
0.0
The expected answer for the above example is 152015.
More Examples
Attempts
I’ve tried to research a strategy to deal with this problem and found that using Python’s default pow(x,y,z), which differs from math.pow(), can help.
pow(x,y,z) is equivalent to x**y % z
However, I cannot use pow(x,y,z). I tried to use pow(15653, -3632, 262643), but I cannot multiply the result of pow(15653, -3632) by 923 to then, as a final step, mod by 262643.
In other words, instead of x**y % z, I am trying to perform (x**y * a ) % z, but there is clearly a 3-parameter limit or number of operations from pow(x,y,z).
What can I do to compute the math formula in Python?
>Solution :
Very easily: just multiply the two, and do an explicit mod:
>>> p = 262643
>>> pow(15653, -3632, p)
86669
>>> 86669 * 923 % p
152015
Done!