Use logarithmic derivatives instead of exponentiation for range checks

[ThomasPiellard]

Currently for verifying in circuit that (f_i)_i is a subset of a table (s_i)_i, we record the f_i, use a hint to compute the multiplicity e_i of the f_i and we check using a random challenge x that Pi_i (x-s_i)^e_i = Pi_i (x-f_i). The e_i are themselves internal variables and this computation leads to a lot of exponentiations.

We should use the logarithmic derivatives (taken from Caulk) to rather check that Sum_i e_i / (x-s_i) = Sum_i 1 / (x-f_i). Those are rational functions, but as long as x is not in the set of poles (that is it does not belong to {f_1, .., f_n} ) Schwartz Zippel lemma (univariate case) works exactly as for polynomials (in fact for polynomials we just avoid the set of poles which is the infinity when sampling a random challenge).

This would save all the exponentiations by the e_i.

Here is the ref for the logarithmic derivative