algebraic sex intelligence or ASI for short

algebraic.py

A = -11780958793495227915671392185849473
B =  2967966474637168250591643503811845

T = 22760185083691921160273336139
V = -48454067936694480117959482723

p = 5213619424271520371687014113170182341777563603680354416779

s = 674628418031497608859095525797188659682765178381388426867

C = 3737
D = 122446


# ============================================================
# Verify removal of p
#
# A+B*S = (T-V*S)(C+D*S)
#
# Since T-V*s = 0 mod p, use conjugate embedding:
#
# C-Ds = (A-Bs)/(T+Vs) mod p
# ============================================================

lhs = (C - D*s) % p

den = (T + V*s) % p

rhs = ((A - B*s) * pow(den, -1, p)) % p

print("C-Ds =", lhs)
print("rhs  =", rhs)

assert lhs == rhs

print("p division verified")


# ============================================================
# Remaining cofactor
#
# N(C+D*S)=C^2+2D^2 = 3*q
# ============================================================

q = 10000003667

norm_remaining = C*C + 2*D*D

print()
print("Remaining norm =", norm_remaining)
print("Expected       =", 3*q)

assert norm_remaining == 3*q


product = ((C+D*s)*(C-D*s)) % p

print("(C+Ds)(C-Ds) mod p =", product)
print("3*q mod p          =", (3*q) % p)

assert product == (3*q) % p

print("remaining factors verified")


# ============================================================
# Remove the algebraic factor above 3
#
# Check both:
#
# (C+D*S)/(1+S)
# and
# (C+D*S)/(1-S)
#
# Choose the one that gives integers.
# ============================================================

print()

# Try divisor 1+S:
#
# 1/(1+S)=(1-S)/3
#
# quotient:
# ((C+2D)/3) + ((D-C)/3)S

if (C + 2*D) % 3 == 0 and (D-C) % 3 == 0:
    E = (C + 2*D)//3
    F = (D-C)//3
    divisor = "1+S"

# Try divisor 1-S:
#
# 1/(1-S)=(1+S)/3
#
# quotient:
# ((C-2D)/3) + ((C+D)/3)S

elif (C - 2*D) % 3 == 0 and (C+D) % 3 == 0:
    E = (C - 2*D)//3
    F = (C + D)//3
    divisor = "1-S"

else:
    raise Exception("No factor above 3 divides C+D*S")


print("Removed divisor:", divisor)
print("E =", E)
print("F =", F)

print("Element =", E, "+", F, "*S")


# ============================================================
# Verify remaining algebraic factor
# ============================================================

new_norm = E*E + 2*F*F

print()
print("New norm =", new_norm)
print("q        =", q)

assert new_norm == q

print("q algebraic factor verified")


# ============================================================
# Reconstruct C+D*S
# ============================================================

if divisor == "1+S":
    # (1+S)(E+F*S)
    C_check = E - 2*F
    D_check = E + F

else:
    # (1-S)(E+F*S)
    C_check = E + 2*F
    D_check = F - E


print()
print("Reconstruction:")
print("C check =", C_check)
print("D check =", D_check)

assert C_check == C
assert D_check == D

print("algebraic division by 3 verified")