I am learning group homomorphism (a Math concept) with modulo arithmetic. Basically, I want to show that g^(2x+8y) mod n equals to (g^(2x) . g^(8y)) mod n.
I have the following python code:
g = 57
n = 1000004119
import galois
GF = galois.GF(n)
# Adjusted values
x = GF(261099267)
y = GF(684728868)
# Direct calculation in field
lhs0 = pow(g, int(GF(2) * x + GF(8) * y), n)
print(f"lhs0 (direct calculation): {lhs0}")
# Separate exponent computations
exp1 = int(GF(2) * x)
exp2 = int(GF(8) * y)
print(f"exp1: {exp1}, exp2: {exp2}")
# Separate pow computations
lhs1l = pow(g, exp1, n)
lhs1r = pow(g, exp2, n)
lhs1 = (lhs1l * lhs1r) % n
print(f"lhs1l: {lhs1l}, lhs1r: {lhs1r}, lhs1: {lhs1}")
# Validate all expected relationships
assert lhs0 == lhs1, f"Final mismatch, lhs0: {lhs0}, lhs1: {lhs1}"
The last assert statement will fail with
Final mismatch, lhs0: 366446438, lhs1: 887364586
Why is that?
Fyi, if I change the x and y values above to:
x = GF(420)
y = GF(888)
the assert statement will pass. What is going on underneath in the Python code?
I expect there is no overflow error in Python. If there is, what precaution should I take in large integer modulo arithmetic in Python? Thanks.
I learned, with my friend's help, that g^(2x+8y) mod n doesn't necessarily equal to (g^(2x) . g^(8y)) mod n when 2x + 8y > n.
Basically x + y = z must hold in the integer field, not just modular arithmetic (Galois field), in order for g^(x+y) mod n = g^x . g^y mod n to hold.
If x = GF(261099267), y = GF(684728868), then
2x + 8y = 6,000,029,478, which is larger than n (1,000,004,119).
But in the case of x = GF(420), y = GF(888), then
2x + 8y = 7,944, which is smaller than n. In this case the homomorphism relation holds.
This is indeed a number theory problem, not python incapability of handling large integers.