算术电路与布尔电路相互转换

布尔电路 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}\)门和上述加法即可实现。

其实就是模拟我们计算机所做的事情。