CTF比赛中遇到许多密码学的题目，往往最后都转化为相关的代数问题。因此，在这里就经常会用到的一些概念进行归纳总结。
原根(primitive root)
什么是原根
\(g\) 是模 \(n\) 的原根，如果所有与 \(n\) 互素的数，均与 \(g\) 的某个幂模 \(n\) 同余。换句话说，对于所有与 \(n\) 互素的 \(a\)，存在 \(k\) 使得 \(g^k \equiv a \bmod n\)。
原根存在性
对于一般的 \(n\) ，原根是不一定存在的。比如说，模8就不存在原根。但如果是模素数 \(p\) ，那么原根即generator是存在的。
原根的个数
如果原根存在，那么其个数为 \(\phi(\phi(n))\) 。这是因为，与 \(n\) 互素的数共 \(k=\phi(n)\) 个，其构成的群如果有generator，那么其个数为 \(\phi(k)\) 。
特别地，由于 \(\phi(p)=p-1\) ，因此模 \(p\) 有限域存在 \(\phi(p-1)\) 个原根。
如何计算原根
并不存在快速计算原根的通用公式。如果使用PARI/GP，则可以通过如下命令：
znprimroot(n)
以下，将介绍同余意义下的平方根、立方根。
平方根
存在性
对于一般的 \(a\) , 不一定存在 \(b\) ，使得 \(b^2 \equiv a \bmod n\) 。举例来说， \(3 \bmod 7\) 便不存在平方根。
唯一性
假设存在 \(a \bmod n\) 的平方根，那么可能不止一个平方根。比如， \(4 \bmod 6\) 有平方根 \(2 \bmod 6\) 和 \(4 \bmod 6\) ，而 \(3 \bmod 6\) 便只有一个平方根 \(3 \bmod 6\) 。再比如， \(4 \bmod 12\) 有4个平方根： \(2 \bmod 12\) , \(4 \bmod 12\) , \(8 \bmod 12\) , \(10 \bmod 12\)
事实上， \(a^2 \equiv (n-a)^2 \bmod n\) ，这是因为：
\[a^2-(n-a)^2 = (a+n-a)(a-n+a) = n(2a-n) \equiv 0 \bmod n\]特别地，对于模 \(p\) 来说，除了以上性质，我们还知道，其平方根总是成对出现的。假设 \(a^2 \equiv b^2 \bmod p\) ，那么 \(a^2-b^2=(a-b)(a+b)\equiv 0 \bmod p\) 。而 \(p\) 为素数，必有 \(a-b\) 与 \(p\) 互素。因此， \(a+b\equiv 0\bmod p\) 。又因为 \(1\lt a+b\lt 2p\) ，因此必有 \(a+b=p\) 。
此外，由于平方根至少是成对出现，因此所有可能的平方的总数是小于 \(n\) 的，这也说明了平方根不一定存在。
如何计算平方根
使用PARI/GP，可以计算模 \(p\) 的平方根如下：
sqrt(Mod(4,7))
当计算得到一个平方根 \(a\) 后，另一个则为 \(p-a\) 。
在RSA中，有时公钥会取3。当然实际没遇到过，只是在题目中见过。下面，将讨论计算模 \(p\) 立方根的相关问题。
立方根
存在性
与平方根类似，立方根也不总是存在的。比如， \(3 \bmod 7\) 便不存在立方根。
唯一性
在此，首先介绍另一个概念：root of unity modulo n. 顾名思义，k-th root of unity modulo n 指的便是 \(x\) 使得 \(x^k \equiv 1 \bmod n\) . 当然，1便是满足条件的，但是非平凡的则不一定存在。如 \(1\bmod 5\) 便不存在除了其本身以外的立方根。
现在，假设k-th root of unity modulo p是存在的，其值为 \(x\) 。如果我们已经知道了 \(b\bmod p\) 的一个 \(k\) 次根为 \(a\) ，那么：
\[(ax)^k = a^kx^k \equiv b \bmod p\]即 \(ax\) 也为 \(b\bmod p\) 的一个 \(k\) 次根。这便给出了一种由一个根求其他根的思路。
回到立方根，即 \(k=3\) 的情况，此时仍然假设 \(a\) 是 \(b\bmod p\)的立方根。
首先，如果 \(\phi(p)=p-1\) 不是3的倍数，即3与 \(p-1\) 互素，那么3对于模 \(p-1\) 的逆是存在的，即存在 \(d\) 使得 \(3d\equiv 1\bmod (p-1)\) 。那么，根据费马小定理可知：
\[b^d \equiv (a^3)^d = a^{3d} = a^{l(p-1)+1}\equiv = (a^{p-1})^la \equiv a \bmod p\]于是，类似于RSA解密的过程，此时可直接计算出 \(b\bmod p\) 的立方根 \(a\)，而且此立方根是唯一的。
接下来，如果 \(\phi(p)=p-1\) 是3的倍数，那么立方根若存在则有3个。为此，我们首先证明， 此时\(1\bmod p\) 的立方根有3个：
由于模 \(p\) 是存在原根的，假设为 \(g\) 。那么根据定义，存在 \(m\) 使得 \(a\equiv g^m\bmod p\) 。这里 \(a\bmod p\) 是我们要计算的 \(1\bmod p\) 的立方根。由此可知：
\[a^3 \equiv (g^m)^3=g^{3m} \equiv 1 \bmod p\]而由费马小定理和原根的性质可知，满足 \(g^k\equiv 1\bmod p\) 的所有 \(k\) ，必然是 \(p-1\) 的倍数，即 \(3m\) 是 \(p-1\) 的倍数。那么 \(m\) 可以取的值便是0, \((p-1)/3\) 和 \(2(p-1)/3\) 这3种，而 \(p-1\) 是3的倍数保证了这样的 \(m\) 是整数。由此可知， \(1\bmod p\) 的立方根为1, \(x\) , \(x^2\) ，其中 \(x\equiv g^{(p-1)/3}\bmod p\) 。
现在，假设 \(a_i\) 和 \(a_j\) 是 \(b\bmod p\) 的两个不同的立方根。由于模 \(p\) 是域，逆是存在的，所以 \(a_ja_i^{-1}\bmod p\) 存在且为 \(1\bmod p\) 的立方根。我们已知 \(1\bmod p\) 的立方根共3个，所以 \(b\bmod p\) 的立方根也是3个。
如何计算立方根
从前述的证明便可知，如果 \(p-1\) 不是3的倍数，那么直接通过费马小定理便可计算出唯一的立方根；如果 \(p-1\) 是3的倍数，那么首先找到一个立方根，其他的立方根可通过乘以 \(1\bmod p\) 的立方根得到。
对于PARI/GP来说，我们使用以下命令:
r=sqrtn(Mod(6,7),3,&z)
这里得到的 \(r\) 便是一个符合条件的立方根，而 \(z\) 则是 \(1\bmod p\) 的立方根。全部的3个立方根就是 \(r\) , \(rz\) , \(rz^2\) 。
此外，我们还可通过PARI的有限域多项式分解求出全部的立方根：
? factor(x^3-Mod(6,7))
[Mod(1, 7)*x + Mod(1, 7) 1]
[Mod(1, 7)*x + Mod(2, 7) 1]
[Mod(1, 7)*x + Mod(4, 7) 1]
上述结果中的\(-1\equiv 6\bmod 7\) , \(-2\equiv 5\bmod 7\) , \(-4\equiv 3\bmod 7\) 便为 \(6\bmod 7\) 的3个立方根。