Track M31 collision probability for fused-constraint spread table LogUp

[rose2221]

Context

The spread table optimization (PR #284 ) uses a LogUp-style lookup argument with two random Fiat-Shamir challenges (sz and rs) appearing in denominators of the form:

1 / (sz - t_j - rs * spread(t_j))

for each table entry. With SPREAD_TABLE_BITS = 8, the spread table has 2^8 = 256 entries. This is the same technique used in #270 for binop tables.

Current State (bn254)

Over bn254 (p ≈ 2^254), the collision probability is negligible:

P(collision) ≈ 256 / 2^254 ≈ 2^-246

No concern here.

Future State (M31)

Over M31 (p = 2^31 - 1), the collision probability for a single challenge would be:

P(collision with 1 challenge) ≈ 2^8 / 2^31 ≈ 2^-23 ≈ 1 in 8,388,608

However, the spread table denominator depends on two independent challenges (sz and rs):

denominator = sz - t_j - rs * spread(t_j)

For a fixed table entry (t_j, spread(t_j)), this is a degree-1 polynomial in two variables. For a collision to occur, a specific linear relation must hold:

sz = t_j + rs * spread(t_j)

Fixing rs to any value, there is exactly one sz that causes a collision per entry — so the collision probability per entry is 1/p, giving:

P(any collision) ≈ 256 / (2^31 - 1) ≈ 2^-23 ≈ 1 in 8,388,608

Why This Matters

A collision means:

(sz - t_j - rs * spread(t_j)) = 0

for some table entry, which makes the fused constraint

(sz - t_j - rs * spread(t_j)) × quotient = multiplicity

trivially satisfiable regardless of the quotient value. This could compromise soundness if exploited.