The formulas were derived by reading the following academic article here
In the multipoint protocol, we had a polynomial of the form:
In our context, is an element in the domain, so naively we cannot compute this division in lagrange form. We also do not want to use monomial form, as we would need to interpolate our polynomials, which is exp
Simplifying the problem:
We have
In what follows, we re-derive all of the necessary formulas that will allows us to divide by a linear polynomial that vanishes on the domain in lagrange basis, where the domain can be arbitrary.
We briefly restate the formula for a lagrange polynomial:
The i'th lagrange polynomial evaluated at is 1 and 0 everywhere else on the domain
We introduce the polynomial .
We also introduce the derivative of .
You can derive this yourself by generalising the product rule: https://en.wikipedia.org/wiki/Product_rule#Product_of_more_than_two_factors
In general this derivative does not have a succinct/sparse form. We do however have a succinct form if the domain is the roots of unity!
Now note that
If we plug in into all the terms with will vanish, this is why the sum disappears into a single product.
We can use and to re-define our lagrange polynomial as :
Looking at the original lagrange formula, is the denominator and is the numerator.
The first barycentric form for a polynomial can now be defined as :
Note that our original problem was that the polynomial:
Had a term in the denominator. We will use the first barycentric form as a way to get rid of this.
First we rewrite using the first form:
We then note that:
I just re-arranged the formula for the first form to equal for
We can hence plug this into our previous equation:
Simplifying since we have a in the numerator and denominator:
Note that when the elements in the domain are roots of unity;
The nice simplification here is due to two reasons: roots of unity form a cyclic group, and we can succinctly represent the d'th roots of unity in a sparse equation which is nice to derivate.
We have now re-defined to not include !
We now summarise and state that:
When dealing with the point which vanishes on zero, the above formula becomes:
Note:
For the case that the evaluation does not vanish on the domain, we can use the original formula.
For all
We note that the terms of the sum are zero, except for when from the definition of the lagrange polynomial , hence we can simplify this to be:
If we use the formulas as shown above, will take steps due to the sum, and will take steps. We describe a way to reduce this complexity in the code.
Note that if we multiply by we get:
We can now substite in
Note that has a division which is many times more expensive than a field multiplication. We now show a way to precompute in such a way that we do not need to invert elements.
With the roots of unity, we were able to use the fact that they formed a group.
Again note that:
The expensive division occurs here . In our particular case, we note that the domain is the discrete interval this means we need only to precompute for . This is 510 values, so we would store . If this is too much space, one could halve the storage by not storing the negated points.
How would I lookup and store these values in practice?
First we imagine that we have stored the values in an array as such:
We first note that we can easily get from to in the array by jumping forward 255 indices. Our strategy will be to find then jump to if we need to.
Example
We want to compute .
In practice, we can use an if statement to check whether 255 or 0 is larger, and subtract accordingly.
With the roots of unity, we did not need this optimisation as equaled which was trivial to fetch from the domain due to the roots of unity forming a domain.
For our case, we will need to store precomputed values, if we want to efficiently compute in steps, and to also avoid inversions.
The strategy is that, we precompute and . Given that we have 256 points in the domain. This will cost us .
How would I lookup and store these values in practice?
Similar to the previous optimisation, we store in an array as such:
Example
We want to compute
In general:
Gotcha: You may produce an off by one error, by not realising that the second optimisation skips ahead 255 points for negative values, while the third optimisation skips ahead 256. This is because the second optimisation omits the value .
Suppose is a point outside of the domain.
Optimising: