Field Arithmetic: M31 → CM31 → QM31

Overview

The Circle STARK verifier operates over a three-level algebraic extension tower built on the Mersenne-31 prime. This page covers the mathematical definitions, Solidity implementation details, packing conventions, and test vectors for each level.

All arithmetic is implemented in M31Lib.sol (311 lines).

1. M31 — The Base Field

Definition

This is the largest Mersenne prime that fits in 31 bits. Elements are integers in $[0, p)$.

Why Mersenne-31?

Mersenne primes enable shift-based modular reduction. For any product $x = a \times b$ (at most 62 bits):

Proof: Write $x = h \cdot 2^{31} + \ell$. Then $x = h \cdot (p+1) + \ell = h \cdot p + h + \ell \equiv h + \ell \pmod{p}$.

The result may be $\geq p$, requiring at most one subtraction. This is dramatically cheaper than general modular reduction.

Solidity Implementation

// M31 addition: single add + conditional subtract
function m31Add(uint32 a, uint32 b) internal pure returns (uint32) {
    uint256 sum = uint256(a) + uint256(b);
    if (sum >= P) sum -= P;
    return uint32(sum);
}

// M31 multiplication: Mersenne reduction
function m31Mul(uint32 a, uint32 b) internal pure returns (uint32) {
    uint256 product = uint256(a) * uint256(b);
    uint256 lo = product & P;     // low 31 bits
    uint256 hi = product >> 31;   // high bits
    uint256 r = lo + hi;
    if (r >= P) r -= P;
    return uint32(r);
}

// M31 inversion via Fermat: a^(p-2) mod p
function m31Inv(uint32 a) internal pure returns (uint32) {
    require(a != 0, "M31: division by zero");
    return m31Exp(a, P - 2);
}

Test Vectors

2. CM31 — Complex Extension

Definition

Elements are $a + bi$ where $a, b \in \mathbb{F}_p$ and $i^2 = -1$.

This is the Gaussian integers modulo $p$. The polynomial $x^2 + 1$ is irreducible over $\mathbb{F}_p$ because $-1$ is a quadratic non-residue modulo $p$ (since $p \equiv 3 \pmod 4$).

Packing Convention

CM31 is packed into uint64:

• Low 32 bits: real part ($a$)
• High 32 bits: imaginary part ($b$)

function cm31Pack(uint32 real, uint32 imag) internal pure returns (uint64) {
    return uint64(real) | (uint64(imag) << 32);
}

Arithmetic

Multiplication: Standard complex multiplication

4 M31 multiplications + 1 addition + 1 subtraction.

Conjugation: $(a + bi) \mapsto (a - bi)$. Negates only the imaginary part.

Inversion: Uses the norm identity

3. QM31 — Quartic Extension (SecureField)

Definition

Elements are $a + bu$ where $a, b \in \mathbb{F}_{p^2}$ (CM31) and $u^2 = 2 + i$.

QM31 is Stwo's SecureField — the field used for all random challenges, ensuring they are drawn from a space of size $\sim 2^{124}$.

Packing Convention

QM31 is packed into uint128:

• Low 64 bits: first CM31 component ($a$)
• High 64 bits: second CM31 component ($b$)

Which expands to four M31 values:

• Bits [0..31]: $m_0$ (real part of $a$)
• Bits [32..63]: $m_1$ (imaginary part of $a$)
• Bits [64..95]: $m_2$ (real part of $b$)
• Bits [96..127]: $m_3$ (imaginary part of $b$)

Complex Conjugation

Stwo defines complex conjugation for QM31 as negating the entire second CM31:

For $q = (m_0, m_1, m_2, m_3)$:

function _conjQ(uint128 q) internal pure returns (uint128) {
    return M31Lib.qm31Pack(
        M31Lib.qm31First(q),                      // Keep first CM31 unchanged
        M31Lib.cm31Neg(M31Lib.qm31Second(q))       // Negate ENTIRE second CM31
    );
}

This matters because the complex conjugate appears in every DEEP quotient line equation — a wrong conjugate corrupts the entire FRI input.

4. Circle Point Arithmetic

Group Operation

$(x_1, y_1) \circ (x_2, y_2) = (x_1 x_2 - y_1 y_2, \; x_1 y_2 + y_1 x_2)$

The identity is $(1, 0)$. The generator is $G = (2, 1268011823)$ with $|G| = 2^{31} = p + 1$.

Doubling (x-coordinate only)

For FRI line domains, only the x-coordinate after doubling is needed:

5. Gas Costs

QM31 multiplication is the dominant cost in the verifier — it appears in every quotient accumulation and every FRI fold.