Spot checking polynomial identities

If a polynomial identity holds at a few random points, it’s very like true. We’ll make this statement more precise, but first let’s look at some applications. You may want to test an identity that naturally presents itself as a statement that two polynomials are equal. Or you might use something like the binomial coefficient trick to reframe a problem isn’t obviously an identity about polynomials. And with algebraic circuits, you can reformulate a wide range of computations as polynomial identities; this is widely used in zero-knowledge proofs. The theorem alluded to at the top of the post is the Schwartz-Zippel lemma. It is formulated in terms of the probability of a non-zero polynomial P evaluating to zero. To prove that two polynomials Q1 and Q2 are equal, you can show that P = Q1(x) − Q2(x) = 0. Schwartz-Zippel lemma Let F be a (typically large) finite field and let P be a non-zero polynomial in n variables P(x1, x2, x3, …, xn) of total degree d. If we choose the x‘s randomly from…