Algebraic digit extraction in base $p$ (proposed by Holden and Linus)

How can we build a polynomial circuit that computes a specific function whose input is an integer in $[0, p^n)$? Here, $n$ is small and $p$ is a small prime. Here are some ideal properties:

• The circuit should have low multiplicative depth, i.e. the greatest number of multiplications on a path through the circuit (more important)
• The circuit should have a small number of gates (less important).

There are two versions of the problem, depending what operations gates can perform:

In version $p=2$, $n$ is between 4 and 8. A gate can:

• (Approximately) add two real numbers (cheap)
• (Approximately) multiply two real numbers (expensive)

We want to compute a specific base-$p$ digit of the input.

The final circuit should be numerically stable.

In version $p$, $n$ is between 8 and 32. A gate can:

• Add two integers mod $p^n$
• Multiply two integers mod $p^n$
• “Divide” an integer by $p$. If the integer is not divisible by $p$, this will cause an error; if it is, it will output one of the $p$ possible quotients (you have no control over which).

We want to compute the mod $p^e$ remainder of the input for some $e<n$.

See a partial solution here.

Motivation

Digit extraction is needed for “bootstrapping” in FHE. (See the explanation of Misheel’s problem.)