Written: , Published: , Author: Kimberlee Model, Tags: circuits, simple circuits,
In ZK Proofs it is difficult to compute some common operations because the typical GF(p) operations only allow two useful operations: addition and multiplication.
From these two simple operations, many others can be built, but many others cannot.
For example, exact equality or inequality can take advantage of Fermat’s Little Theorem, and from this we can build multiplexers to implement conditionals.
But comparative inequalities (less than, greater than, etc) are still impossible without further work.
In this post we’ll start by simulating Boolean logic in GF(p), then build up to comparison operations, and show how we can use these to simulate integer division.