Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Integer Division

Integer division returns the quotient of two numbers, rounded down, e.g. . This is different from the division in a prime field, where is the field element that gives 7 when multiplied by 2.

IntDiv

template IntDiv(n) {
  // ensures that `quot * in[1] + rem` can not wrap around the field
  assert(n <= 125);
  signal input in[2];
  signal output out;

  // divisor must be non-zero
  signal is_non_zero <== IsZero()(in[1]);
  0 === is_non_zero;

  // compute the quotient and remainder outside the circuit
  var quot_hint = in[0] \ in[1];
  var rem_hint = in[0] % in[1];
  signal quot <-- quot_hint;
  signal rem <-- rem_hint;

  // quotient & remainder must be n-bit numbers, otherwise a dishonest prover can
  // pick a "negative" remainder (a large field element) that still passes the
  // `rem < in[1]` check, or a quotient that is a field division `in[0] / in[1]`
  _ <== Num2Bits(n)(quot);
  _ <== Num2Bits(n)(rem);

  // constrain the division operation
  // in[0] / in[1] is defined as the unique pair (q, r) s.t.
  // in[0] = in[1] * q + r and 0 <= r < |in[1]|
  in[0] === quot * in[1] + rem;

  component remIsLess = LessThan(n);
  remIsLess.in <== [rem, in[1]];
  remIsLess.out === 1;

  out <== quot;
}

Doing integer division within a circuit is more costly than what one might one expect! Consider two -bit numbers and . An integer division implies the following equation:

where is the quotient, and is the remainder such that . As an example, consider the division . We have:

giving us the quotient and remainder . Notice that if we allowed , we could have:

which would be wrong! This is why we constrain the remainder with LessThan, to ensure .

However, that check alone is not enough. Remember that we are working in a prime field, where a “negative” number such as is actually a very large number . Consider the following:

This is a quotient with a remainder , which is wrong since should give . Is ? It should not be in the field, as is a very large number there; however, LessThan(n) is only correct for -bit inputs! It computes , which is an -bit number with its ’th bit unset, so it says that . A dishonest prover could then claim that .

To prevent this, we range-check both the quotient and the remainder using Num2Bits(n):

  • With , the remainder can not be “negative” anymore, and LessThan(n) can safely check .
  • With , the quotient can not be a field element like , which would satisfy in the field for any .

Finally, we must make sure that can not wrap around the field, otherwise the equation would only hold “modulo ” instead of over the integers. As and are -bit numbers, and can be at most bits (otherwise LessThan fails), the result is less than . The assert(n <= 125) ensures that this is less than the prime of BN254, which is around .

With these checks, the circuit has a unique solution for given and : the quotient and remainder of the usual integer division.

Constraint Count

IntDiv(n) has non-linear constraints, e.g. 50 for 16-bit numbers. Almost all of them come from the bit decompositions: the two range checks of the quotient & the remainder, and the -bit decomposition within LessThan.