Polynomial<Logic>

Header: circuits/logic/polynomial.h

Thin wrapper around Logic that evaluates fixed-coefficient polynomials on wire-borne inputs. Used internally by the pluckers and EltMuxer.

template <class Logic>
class Polynomial {
 public:
  using Field = typename Logic::Field;
  using BitW  = typename Logic::BitW;
  using EltW  = typename Logic::EltW;
 
  explicit Polynomial(const Logic& l);
 
  void powers_of_x(size_t n, EltW xi[/*n*/], const EltW& x) const;
 
  template <size_t N> EltW eval       (const Poly<N, Field>& coef, const EltW& x) const;
  template <size_t N> EltW eval_horner(const Poly<N, Field>& coef, EltW x) const;
};

powers_of_x

Writes xi[k] = x^k for k ∈ [0, n). Uses the recurrence xi[k] = xi[k - k/2] · xi[k/2], which pairs up already-computed terms to reach every exponent in O(log n) depth while reusing subexpressions.

eval

Dot product with the coefficient vector:

result = Σ coef[i] · x^i

The coefficient array coef[i] is a compile-time Field::Elt, so each term emits one mul(Elt, EltW). Depth is dominated by powers_of_x.

eval_horner

Parallel Horner’s rule: halves the working set each iteration by pairing c[2i] and c[2i+1] and folding them together with x, then squaring x. This reaches O(log N) depth and often fewer multiplications than coefficient-wise dot product when N is large, at the cost of more computation on x.