布尔电路 to 算术电路
在$(\mathbb{F},+,\cdot)$上考虑一个函数$f$，该函数可以由大小为多项式的布尔电路在其输入大小上计算，例如，在标准基础$\{ \mathsf{XOR}，\mathsf{AND}，\mathsf{NOT} \}$。要在$\mathbb {F}$上模拟计算，请将$0$编码为$0_ \mathbb {F}$(在$\mathbb {F}$中加法的中性)，将$1$编码为$1_ \mathbb {F}$(乘法的中性)。布尔门可以模拟如下：
要计算输入$(x，y)$的$\mathsf{OR}$门，返回$x+y - x \cdot y$
要计算输入$(x，y)$的$\mathsf{AND}$门，返回$x \cdot y$
要计算输入$(x，y)$的$\mathsf{XOR}$门，返回$x + y-2 \cdot x \cdot y$
要计算输入$x$的$\mathsf{NOT}$门，请返回$1_ \mathbb{F} -x$。
算术电路 to 布尔电路
考虑$\mathbb{F}$的任何元素$x$的二进制分解：$x = \sum_ {i = 0} ^ {\lceil \log | \mathbb {F} || \rceil-1} b_i \cdot 2 ^ i$，$b_i \in \{0_\mathbb{F}，1_\mathbb {F} \}$。
- $\mathbb {F}$上的加法: 通过$\mathsf{XOR}$门得到第$i$位的值，通过$\mathsf{AND}$门得到第$i$位的进位。
- $\mathbb {F}$上的乘法: 通过$\mathsf{AND}$门和上述加法即可实现。
其实就是模拟我们计算机所做的事情。