Given a field element , these gadgets decompose it into -bit windows where each a -bit value.

This is done using a running sum We initialize the running sum and compute subsequent terms This gives us:

Strict mode

Strict mode constrains the running sum output to be zero, thus range-constraining the field element to be within bits.

In strict mode, we are also assured that gives us the last window in the decomposition.

Lookup decomposition

This gadget makes use of a -bit lookup table to decompose a field element into -bit words. Each -bit word is range-constrained by a lookup in the -bit table.

The region layout for the lookup decomposition uses a single advice column , and two selectors and

Short range check

Using two -bit lookups, we can range-constrain a field element to be bits, where To do this:

  1. Constrain to be within bits using a -bit lookup.
  2. Constrain to be within bits using a -bit lookup.

The short variant of the lookup decomposition introduces a selector. The same advice column has here been renamed to for clarity:

where Note that is assigned to a fixed column at keygen, and copied in at proving time. This is used in the gate enabled by the selector to check that was shifted correctly:

Combined lookup expression

Since the lookup decomposition and its short variant both make use of the same lookup table, we combine their lookup input expressions into a single one:

where and are the same cell (but distinguished here for clarity of usage).

Short range decomposition

For a short range (for instance, where ), we can range-constrain each word using a degree- polynomial constraint instead of a lookup: