Track M31 collision probability for combined AND/XOR lookup table optimization

[rose2221]

Context

The combined AND/XOR lookup table optimization introduced in PR #270 uses a LogUp-style lookup argument where a random Fiat-Shamir challenge γ appears in denominators of the form 1 / (γ - tᵢ) for each of the 65,536 table entries.

Current State (BN254) — No Issue

Over BN254 (p ≈ 2^254), the probability that γ collides with any table entry is:
P(collision) ≈ 65,536 / 2^254 ≈ 2^(-238)
This is cryptographically negligible.

Future Concern (M31)

If ProveKit migrates to M31 (p ≈ 2^31), the collision probability becomes:
P(collision) ≈ 65,536 / 2^31 ≈ 2^(-15) ≈ 1/32,768
This would need further investigation, a collision means γ = tᵢ for some table entry, which causes division by zero in the lookup argument and could compromise soundness. Whether this probability is tolerable depends on the target security level and usage context, but it warrants careful consideration before adopting this optimization over a smaller field.

Action Required

No action needed while using BN254. Revisit this optimization if/when migrating to M31 or other small-characteristic fields.