Inversion
The (multiplicative) inverse of an element within a prime field is denoted as such that . An additive inverse of is shown as and it holds that . Inverting an element within the circuit is inefficient, so the inverse is computed off-circuit and a constraint is added to make sure their multiplications result in 1.
Inverse
template Inverse() {
signal input in;
signal output out;
assert(in != 0);
signal inv <-- in != 0 ? 1 / in : 0;
signal isZero <== 1 - (in * inv);
// if isZero, since in = 0 this holds
// otherwise, it holds due to in * 0 == 0
in * isZero === 0;
inv * isZero === 0;
out <== inv;
}
Zero does not have a multiplicative inverse though. The assert(in != 0) above only runs while computing the witness, and it does not add any constraint, so a malicious prover could still provide a witness with in = 0. So the circuit handles that case with constraints as well, very much like IsZero:
- If
inis not zero,in * isZero === 0forcesisZero = 0, which meansin * inv = 1, i.e.invis the inverse ofin. - If
inis zero, thenisZero = 1, andinv * isZero === 0forcesinv = 0.
So the circuit returns 0 for an input of 0, and it is up to the caller to make sure that this is acceptable, or that the input is non-zero.
There are two ways to find an inverse outside the circuit:
- Use Extended Euclidean Algorithm
- Use Fermat’s Little Theorem
Interested reader can check them out on the web!
Constraint Count
Inverse has 3 non-linear constraints: one for isZero, and one for each of the two checks.