关于陪集元素的选取

[dddjjjiie]

在 "理解 PLONK（四）：算术约束与拷贝约束" 这一小节中, 文章提到采用互相不等的二次非剩余 $k_i$ 生成陪集 $k_i \mathbf{H}$, 其中 $H$ 为乘法循环群, 这种方式存在问题. 考虑以下情形:

有限域 $F_{17}$ 上的乘法群 $F_{17}^* = \{g^0, \cdots, g^{15}\}$, 其中生成元 $g = 3$, 令 $h = g^4$, 则 $H = \{g^0, g^4, g^8, g^{12}\} = \{h^0, h^1, h^2, h^3\}$ 为乘法循环群.

如果令 $k_1 = g, k_2 = g^5$, 显然 $k_1, k_2$ 都是奇数, 即它们都是二次非剩余, 则有 $k_1 H = \{g^1, g^5, g^9, g^{13}\}$, $k_2 H = \{g^5, g^9, g^{13}, g^1\}$, 有 $k_1 H = k_2 H$.

对于 $k$ 的选取, 一个有效取值范围为 $\{g^0, g^1, g^2, g^3\}$, 即 $\{g^i\}$, $i \in [0, | F_{17}^* | / DL(g, h))$, 其中 $DL(g, h)$是元素 $h$ 关于 $g$ 的离散对数, 在此 $DL(g, h) = 4$, 且 $| F_{17}^* |$ 为乘法群的阶, 其值为16.