Interpolation

algebra/interpolation.h and algebra/poly.h together provide the univariate-polynomial utilities that sumcheck and the low-degree test both lean on: fixed-size polynomial containers, three representation bases (Lagrange, Newton, monomial), fast conversion between them, and a sumcheck-optimised variant that elides the p(1) coefficient whenever the caller knows it is not needed.

When to reach for it

• You are writing a sumcheck prover or verifier and need to evaluate a low-degree polynomial given at a few sample points.
• You are moving a polynomial between evaluation and coefficient form and want a cost-aware API — inversion-heavy on general points, O(n) on arithmetic-progression points.
• You are extending a gadget (sha, ecdsa, mac) with a new quadratic check and need a compact Poly<N, Field> to carry it through.

Design overview

Polynomials have three standard bases:

• Lagrange: a list of evaluations (p(0), p(1), \ldots, p(N-1)). Easy to construct from samples.
• Newton (forward-difference): coefficients of the Newton basis polynomials, good for incremental extension and for evaluating via Horner.
• Monomial (power): coefficients of 1, x, x^2, \ldots — what .eval_monomial(x) consumes.

Interpolation<N, Field> is a stateless template with methods that convert in-place between bases, plus evaluation primitives. Poly<N, Field> wraps an N-tuple with convenience methods that call into Interpolation under the hood. The number of points N is a compile-time template parameter so the compiler can specialize inner loops.

Conversion between bases costs one of two regimes:

• Arithmetic-progression points ({0, 1, \ldots, N-1}, the usual case): an O(N) pass using cached inverse differences.
• Arbitrary points: O(N^2) because each Lagrange coefficient needs a field inversion over the pairwise-difference product.

SumcheckPoly<N, Field> is the same container but with a convention that index 1 holds a placeholder — not the value p(1) — because the sumcheck inner loop computes that coefficient separately from the accumulated sum-over-cube. Arithmetic is adjusted to skip index 1 on add/sub/mul.

API surface

Interpolation<N, Field> — conversions and evaluation

template <size_t N, class Field>
class Interpolation {
 public:
  using Elt = typename Field::Elt;
  using PolyN = Poly<N, Field>;
 
  // Evaluation basis ↔ Newton basis.
  // X holds the N arbitrary evaluation points.
  static void newton_of_lagrange_inplace(PolyN& A, const PolyN& X,
                                         const Field& F);
 
  // Newton basis ↔ monomial basis.
  static void monomial_of_newton_inplace(PolyN& A, const PolyN& X,
                                         const Field& F);
 
  // Lagrange → monomial (two-step convenience).
  static PolyN monomial_of_lagrange(const PolyN& L, const PolyN& X,
                                    const Field& F);
 
  // Evaluate in Newton basis at an arbitrary point x.
  static Elt eval_newton(PolyN& Newton, const PolyN& X, const Elt& x,
                         const Field& F);
};

newton_of_lagrange_inplace pre-caches 1/(X[k] - X[k-i]) to amortise field inversions; when the evaluation points form an arithmetic sequence the cache hits on most inverse computations and the conversion runs in effectively O(N^2) multiplications with very few inversions.

Poly<N, Field> — wrapped polynomial container

template <size_t N, class Field>
class Poly {
 public:
  Elt t_[N];  // values at 0, 1, ..., N-1 (Lagrange basis)
 
  Elt eval_lagrange(Elt r, const Field& F) const;   // evaluate at arbitrary r
  Elt eval_monomial(Elt r, const Field& F) const;   // interpret t_[] as monomial coeffs
  Elt eval_newton(const Elt& x, const Field& F) const;  // evaluate in Newton basis
  void newton_of_lagrange(const Field& F);           // in-place Lagrange → Newton
 
  // Promote a two-point linear polynomial to N points (assumes arithmetic progression).
  static T extend(const Poly<2, Field>& f, const Field& F);
};

extend is a static factory: it takes a two-point polynomial (a line f[0], f[1]) and returns a new Poly<N, Field> whose remaining N - 2 entries are filled by extending the arithmetic progression — the inner-loop trick that makes the sumcheck prover O(N) per round instead of O(N \log N).

SumcheckPoly<N, Field> — the same, minus p(1)

template <size_t N, class Field>
class SumcheckPoly {
 public:
  Elt t_[N];  // t_[1] is a placeholder — do not read.
  void add(const SumcheckPoly& b, const Field& F);  // skips t_[1]
  void sub(const SumcheckPoly& b, const Field& F);  // skips t_[1]
  void mul_scalar(Elt s, const Field& F);           // skips t_[1]
 
  // Convert to a full Poly by supplying the missing p(1) explicitly.
  Poly<N, Field> to_poly(const Elt& p1) const;
};

The p(1) value is reconstructed by the sumcheck verifier from the round constraint (p(0) + p(1) = claim), so the prover never stores it. This saves one field multiplication per round, which matters at the round counts sumcheck reaches. To evaluate a SumcheckPoly at an arbitrary point, convert it first: call to_poly(p1) to obtain a Poly<N, Field>, then use eval_lagrange or eval_newton on the result.

See it used

• longfellow-zk/lib/algebra/interpolation_test.cc — interpolation_test.cc 
• longfellow-zk/lib/algebra/poly_test.cc — poly_test.cc 
• longfellow-zk/lib/sumcheck/prover.h — uses SumcheckPoly directly in the round loop.

Related

• Prime Fields — supplies the Elt type.
• FFT & Convolution — used when N is large enough that the O(N^2) Lagrange path becomes unacceptable.
• Sumcheck — the main consumer of SumcheckPoly.