# Decomposition

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: