verify_normal_family_attack.py

#!/usr/bin/env python3
"""Dependency-free exact checks for the first Bethe--Calogero attack.

The A2 calculations are polynomial identities in X, Y, and g3.  A tiny
exact polynomial implementation is used so the certificate needs no CAS.
"""

from __future__ import annotations

from fractions import Fraction


Monomial = tuple[int, int, int]
Poly = dict[Monomial, Fraction]


def clean(poly: Poly) -> Poly:
    return {m: c for m, c in poly.items() if c}


def add(*polys: Poly) -> Poly:
    out: Poly = {}
    for poly in polys:
        for monomial, coefficient in poly.items():
            out[monomial] = out.get(monomial, Fraction()) + coefficient
    return clean(out)


def scale(poly: Poly, scalar: int | Fraction) -> Poly:
    scalar = Fraction(scalar)
    return clean({m: scalar * c for m, c in poly.items()})


def multiply(left: Poly, right: Poly) -> Poly:
    out: Poly = {}
    for (a, b, c), x in left.items():
        for (d, e, f), y in right.items():
            monomial = (a + d, b + e, c + f)
            out[monomial] = out.get(monomial, Fraction()) + x * y
    return clean(out)


def power(poly: Poly, exponent: int) -> Poly:
    out: Poly = {(0, 0, 0): Fraction(1)}
    base = poly
    n = exponent
    while n:
        if n & 1:
            out = multiply(out, base)
        base = multiply(base, base)
        n >>= 1
    return out


def sub(left: Poly, right: Poly) -> Poly:
    return add(left, scale(right, -1))


ONE: Poly = {(0, 0, 0): Fraction(1)}
X: Poly = {(1, 0, 0): Fraction(1)}
Y: Poly = {(0, 1, 0): Fraction(1)}
G3: Poly = {(0, 0, 1): Fraction(1)}
Z = scale(add(X, Y), -1)


def sum_of_squares(*values: Poly) -> Poly:
    return add(*(power(value, 2) for value in values))


S = add(power(X, 2), multiply(X, Y), power(Y, 2))
G2 = scale(S, 4)
P = multiply(multiply(X, Y), Z)
N1 = add(scale(X, 2), Y)
N2 = add(X, scale(Y, 2))


def wp2(value: Poly) -> Poly:
    """wp'' when wp=value: 6 value^2 - g2/2."""

    return add(scale(power(value, 2), 6), scale(G2, Fraction(-1, 2)))


def wp4(value: Poly) -> Poly:
    """wp'''' when wp=value."""

    return add(
        scale(power(value, 3), 120),
        scale(multiply(G2, value), -18),
        scale(G3, -12),
    )


# On the generic A2 critical curve, X+Y+Z=0 and
# X^2+XY+Y^2=g2/4.  The latter is built into G2 above.
assert add(X, Y, Z) == {}
assert sub(sum_of_squares(X, Y, Z), scale(G2, Fraction(1, 2))) == {}

# V2 is constant on the whole critical curve.
V2 = add(wp2(X), wp2(Y), wp2(Z))
assert sub(V2, scale(G2, Fraction(3, 2))) == {}

# The CM Hessian has rank-one Morse--Bott factorization H=2 n n^T.
H11 = add(wp2(X), wp2(Z))
H12 = wp2(Z)
H22 = add(wp2(Y), wp2(Z))
assert sub(H11, scale(power(N1, 2), 2)) == {}
assert sub(H12, scale(multiply(N1, N2), 2)) == {}
assert sub(H22, scale(power(N2, 2), 2)) == {}

# With s=wp'(a)=wp'(b)=-wp'(a+b), the Weierstrass cubic and
# the cubic having roots X,Y,Z give s^2=4XYZ-g3.
S2 = sub(scale(P, 4), G3)
weierstrass_s2 = add(scale(power(X, 3), 4), scale(multiply(G2, X), -1), scale(G3, -1))
assert sub(weierstrass_s2, S2) == {}

# The order-e2^2 effective obstruction is
# V4/360 - s^2/4.  It too is constant on the critical curve.
V4 = add(wp4(X), wp4(Y), wp4(Z))
E2 = add(scale(V4, Fraction(1, 360)), scale(S2, Fraction(-1, 4)))
assert sub(E2, scale(G3, Fraction(3, 20))) == {}

print("A2 critical coordinates: Z = -X - Y")
print("curve relation: X^2 + X*Y + Y^2 = g2/4")
print("V2 = sum wp'' = 3*g2/2")
print("Hessian = 2*n*n^T, n = (2*X+Y, X+2*Y)")
print("s^2 = 4*X*Y*Z - g3")
print("first normal equation: n dot xi = s/2")
print("effective e2^2 term = V4/360 - s^2/4 = 3*g3/20")
print("all exact polynomial identities passed")