ZK101 - 零知识学习零知识

乘法循环群是什么？

他是一个全部由生成元 $g$ 的幂运算构成的群。

为什么要用乘法循环群？因为乘法循环群有一个很厉害的性质（离散对数）: 给定生成元 $g$ 以及有限域的元素 $y$ ，但我们没有高效的算法找到 $x$ 使得 $g^x=y$ ，这一个小小的性质可以认为是很多 ZK 证明系统的根基。

⚠️

以下我们讨论的乘法循环群都是基于素数大小的，因此是WIKI-循环群，有些乘法循环群不是循环群，这不是我们讨论的范围。

简单理解乘法循环群

一个小小的例子：[1,3,2,6,4,5]，在这个数组中，你是否能发现什么计算规律？
看起来是没有什么计算规律的，但是他的生成方式是具有规律的。
这是一个以3为生成元，7 为模数，阶为 6 的乘法群，并且具有循环性质。

生成元(g)：通过 $g^n \bmod p$ 可以生成群中的所有元素。
模数(p)：任何计算都需要 mod p。群阶(n)：可以叫次，群的大小。直接等于群元素的数量。
元素 $g$ 的阶：使得 $g^n = e$ 成立的最小正整数 n, $e$ 是群的单位元。

请看图

解释如下：

\begin{align*} 3^0 \bmod 7 &= 1 \bmod 7 = 1 \\ 3^1 \bmod 7 &= 3 \bmod 7 = 3 \\ 3^2 \bmod 7 &= 9 \bmod 7 = 2 \\ 3^3 \bmod 7 &= 27 \bmod 7 = 6 \\ 3^4 \bmod 7 &= 81 \bmod 7 = 4 \\ 3^5 \bmod 7 &= 243 \bmod 7 = 5 \\ 3^6 \bmod 7 &= 729 \bmod 7 = 1 \text{ \# 回到起点} \\ 3^7 \bmod 7 &= 2,187 \bmod 7 = 3 \text{ \# 循环中} \end{align*}

更详细的乘法循环群概念可以参考WIKI-整数模 n 乘法循环群

逆元

在乘法循环群中，每个元素都有一个逆元。逆元就是两个数相乘等于1的数。

比如在模7的乘法循环群中 [1,3,2,6,4,5]：

3 的逆元是 5，因为 $3 \times 5 = 15 ≡ 1 (mod 7)$
2 的逆元是 4，因为 $2 \times 4 = 8 ≡ 1 (mod 7)$

相信你已经看出来了，在乘法循环群中，对于任何k， $(g^k)(g^{n-k}) = g^n = 1$ ，（注意，k从0开始）比如：

$3^0=1$ 的逆元是 $3^6=1$
$3^1=3$ 的逆元是 $3^5=5$
$3^2=2$ 的逆元是 $3^4=4$
$3^3=6$ 的逆元是 $3^3=6$

其实这里，就是费马小定理。对于任何元素 $\theta$ ， $\theta^{-1} = \theta^{p-2} = \theta^{n-1}$ 。(p为模数，n为阶)

💡

逆元的存在让我们可以在乘法循环群中进行”除法”运算。比如要计算 a÷b，我们可以用 a 乘以 b 的逆元。

乘法循环群的作用

在乘法循环群运算是，使用以下规则。只要根据以下规则，我们的计算的结果就是确定的。

加法： $a+b = g^a \times g^b = g^{(a+b)}$
乘法： $a \times b = (g^x)^y = g^{(a \cdot b)}$
逆元： $a^{-1} = g^{-a}$
除法： $$a / b = a \times b^-1

除法就是乘法的逆运算，因此我们可以用乘法和逆元来实现除法。

这里有人可能会联想到离散对数问题：给定生成元 $g$ 和有限域元素 $y$ ，找到 $x$ 使得 $g^x=y$ 是一个困难的问题。这个问题在密码学中有着重要的应用。需要注意到，除法并不能简化离散对数难题。如果群阶很大（254bit），那么我们无法在多项式时间内求出正确的指数 $x$ 。

📒

计算对数是一个典型的单向函数——正向计算简单，但反向计算极其困难。这种特性与域的大小和生成元的选择密切相关。由于群的循环特性，反向计算还面临着结果不唯一的问题。

以上面的例子来说，如果我们想找到哪个指数可以得到结果3，通过暴力枚举可以得到多个答案：1、7、13、19等。这些答案都是正确的，因为它们在模运算下得到相同的结果。

当我们将域的大小扩大到密码学所需的规模（通常是256位或更大），这个计算变得几乎不可能完成。即使使用最先进的计算机，暴力破解的难度也堪比破解比特币私钥——这正是密码学中离散对数问题的安全性所在。

乘法循环群的一些小计算

当我们在一个乘法循环群中，是可以轻松的找到一个指定大小的乘法子群的。

乘法子群的大小必须整除原来群的大小。根据拉格朗日定理，群的任何子群的阶必须整除群的阶。

找到一个指定大小的乘法子群

我们以模数为13，生成元为2为例子，创建一个阶为13的乘法子群。

指数	0	1	2	3	4	5	6	7	8	9	10	11	12
计算式	$2^0$	$2^1$	$2^2$	$2^3$	$2^4$	$2^5$	$2^6$	$2^7$	$2^8$	$2^9$	$2^{10}$	$2^{11}$	$2^{12}$
$2^n {mod} 13$	1	2	4	8	3	6	12	11	9	5	10	7	1

根据观察，上面有 12 个元素（最后一个元素是1，表示循环，实际上前11个元素已经组成了一个乘法子群）。

那么，根据刚刚拉格朗日定理，我们是可以找到阶为，6，4，3，2，1的乘法子群的。我们只需要将生成元扩大相同倍数即可。因此，对应的生成元就是 $2^2$ ， $2^3$ ， $2^4$ ， $2^6$ 。

原序列	0	1	2	3	4	5	6	7	8	9	10	11	12
计算式	$2^0$	$2^1$	$2^2$	$2^3$	$2^4$	$2^5$	$2^6$	$2^7$	$2^8$	$2^9$	$2^{10}$	$2^{11}$	$2^{12}$
$2^n {mod} 13$	1	2	4	8	3	6	12	11	9	5	10	7	1
$2^{2^n} {mod} 13$	1		4		3		12		9		10		1
$2^{3^n} {mod} 13$	1			8			12			11			1
$2^{4^n} {mod} 13$	1				3				9				1
$2^{6^n} {mod} 13$	1						12						1

当我们给生成元进行一次平方，新的生成元生成的循环群的大小就会是原来的一半。这是一个很简单的构建一个任意大小的子群的办法。

更简单点！

我们说简单的计算规则！当 $F_{13}$ 时，有效元素为12。那么所有可以整除12的数，我们都计算出来。
结果是：2,3,4,6。(结果中去掉1和12，这两个绕回来了。)

对应的，我们可以生成的子群大小就是 12/2=6, 12/3=4, 12/4=3, 12/6=2。

对应的生成元就是: $2^2,2^3,2^4,2^6$ 。

具体的数据就和上面的表格一样。可以验证一下。

附加内容：特殊多项式乘积

在乘法循环群中，下列等式永远成立，n为群的阶，g为生成元。生成一个乘法子群。

\prod\limits_{i=0}^{n-1} (x-g^i) = x^n - 1

为什么？我们暂时不研究这种奇妙的性质是怎么达成的，我们现在主要是验证这个等式是否成立。

继续使用 $n=6$ ， $g=3$ ，模数为7作为例子。

根据上面的内容， $3^6=1$ ，这里先留着，等会用。

\prod\limits_{i=0}^{5} (x-3^i) = x^{6} - 1

首先我们知道，根据因式分解，如果 $a$ 是一个根，那么 $(x-a)$ 就是因式之一。
因此，我们直接从群中抽取一个元素带入等式 $x^{6} - 1$ 。比如， $x=3^4$ 。然后配合刚刚的 $3^6=1$ ，进行化简。

\begin{align*} x^{6} - 1 &= (3^{4})^{6} - 1 \\ &= (3^6)^4 - 1 \\ &= 1^4 - 1 \\ &= 0 \end{align*}

当我们代入所有元素，结果发现都成立。具体的计算方式就不在这里展开，有兴趣可以多多讨论交流。

0 - 有限域环状太空城 2 - 多项式数学中的函数