Summary: Seeking a method to generate a polynomial from specified coordinates, enabling coefficient iteration and optional point evaluation
I am currently developing a basic JavaScript/TypeScript algorithm for KZG commitments, which involves multiplying coefficients of a polynomial derived from a given string with the Structured Reference String (SRS) raised to the appropriate power.
Essentially, I need to loop through all the coefficients of this newly created polynomial (or at least that's my current understanding– any suggestions are welcome).
My objective is as follows:
- Input a string
- Convert the string into XY-coordinates on a plane
- Determine the polynomial passing through these coordinates
- **Iterate over the polynomial’s coefficients **<-- where I'm encountering a roadblock
- (optional) Evaluate the polynomial at a specific point Z <-- it would be ideal if this functionality can coexist with the previous requirement
I’m facing challenges at step 4).
While I know how to build a polynomial from a given string in JS/TS using Lagrange Interpolation, extracting its coefficients proves difficult. These coefficients are essential for subsequent multiplication with SRS.
Below is my Lagrange Interpolation algorithm - capable of solving 5), but lacking an apparent method for obtaining exact coefficients:
type Point = { x: number; y: number };
function lagrangeInterpolation(points: Point[], newX: number) {
const n = points.length;
let newY = 0;
for (let i = 0; i < n; i++) {
let { x, y } = points[i];
let term = y;
for (let j = 0; j < n; j++) {
if (i !== j) {
let { x: xj } = points[j];
term = (term * (newX - xj)) / (x - xj);
}
}
newY = newY + term;
}
return newY;
}
Would another interpolation algorithm facilitate precise coefficient calculations?
I couldn't locate any JS libraries addressing this issue directly. The closest contenders were:
- polynomial -> drawback: lacks a built-in method for returning coefficients or processing a Lagrange-like polynomial for regex-based coefficient extraction.
- nerdamer-prime -> downside: can simplify any polynomial but doesn’t guarantee term order by x power, complicating coefficient retrieval via regex; also lacks direct coefficient access.