A Lagrange polynomial is a basis polynomial associated with interpolation roots. In SNARK construction, these polynomials provide coefficient functions for QAP components such as v_i(x), w_i(x), y_i(x), and h(x). Each polynomial is assembled from root differences: its denominator multiplies every r_i − r_j for j ≠ i, while its numerator omits the corresponding root factor. section 19.5.1
An implementation follows this flow:
- Compute p_i = product of r_i − r_j for every j ≠ i. section 19.5.1
- Generate coefficient combinations with an index table, then sum products of the negated roots. section 19.5.1
