python-3.xmodulohomomorphism

Math power function with modulo arithmetic in Python


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.


Solution

  • 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.