密码学数学基础（四）指数与原根

四、指数与原根

4.1 指数、原根、及其性质

定义4.1：设\(m\ge1\)，\((a,m)=1\)。使\(a^d\equiv1\pmod m\)成立的最小的正整数\(d\)称为\(a\)对模\(m\)的指数（阶），记作\(\delta_m(a)\)。当\(\delta_m(a)=\varphi(m)\)时，称\(a\)是模\(m\)的原根。

下面讨论指数的性质，在此之前先给出两组例子，可以结合例子理解定理。

例4.1：

• \(m=13\)

\(a\)	1	2	3	4	5	6	7	8	9	10	11	12
\(\delta_{13}(a)\)	1	12	3	6	4	12	12	4	3	6	12	2

• \(m=2^4\)

\(a\)	1	3	5	7	9	11	13	15
\(\delta_{16}(a)\)	1	4	4	2	2	4	4	2

定理4.1：以下四条性质都假设\(m\ge1\)，\((a,m)=1\)。

• \(a,a^2,\cdots,a^{\delta_m(a)}\)模\(m\)两两不同余；

• 对任意整数\(d\)，如果\(a^d\equiv1\pmod m\)，则\(\delta_m(a)\mid d\)。特别地，\(\delta_m(a)\mid\varphi(m)\)；

• 若\(a^i\equiv a^j\pmod m\)，则\(i\equiv j\pmod{\delta_m(a)}\)；

• \(\delta_m(a)=\delta_m(a^{-1})\)。

证明：

• 采用反证，假设存在\(1\le i<j\le\delta_m(a)\)使得\(a^i\equiv a^j\pmod m\)，则\(a^{j-i}\equiv1\pmod m\)，显然\(j-i<\delta_m(a)\)，这与指数的最小性矛盾，故原命题成立；

• 标准证明略。因为\(\delta_m(a)\)已经是满足等式的最小的\(d\)了，其他的\(d\)肯定是\(\delta_m(a)\)的倍数。特别地，由欧拉定理有\(a^{\varphi(m)}\equiv1\pmod m\)，因此当\(d=\varphi(m)\)时有\(\delta_m(a)\mid\varphi(m)\)；

• 由第2条性质，易知成立；

• 设\(\delta=\delta_m(a)\)，因为\(a^{-1}\)是\(a\)的逆，根据逆的定义有\(a\cdot a^{-1}\equiv1\pmod m\)，所以 \[ (a\cdot a^{-1})^\delta\equiv a^\delta\cdot(a^{-1})^\delta\equiv(a^{-1})^\delta\equiv1\pmod m \] 假设还存在\(d<\delta\)使得\((a^{-1})^d\equiv1\pmod m\)成立，则反过来有 \[ (a\cdot a^{-1})^d\equiv a^d\cdot(a^{-1})^d\equiv a^d\equiv1\pmod m \] 这与\(\delta_m(a)\)的定义矛盾，因此\(\delta\)也是\(a^{-1}\)的指数。

定理4.2：设\(k\)是正整数，则有 \[ \delta_m(a^k)=\frac{\delta_m(a)}{(k,\delta_m(a))} \]

证明：记\(\delta=\delta_m(a)\)，\(\delta'=\frac{\delta}{(\delta,k)}\)，\(\delta''=\delta_m(a^k)\)。

• 由题可知\(a^\delta\equiv1\pmod m\)，\((a^k)^{\delta''}\equiv a^{k\delta''}\equiv1\pmod m\)，由定理4.1第2条可得\(\delta\mid k\delta''\)，所以 \[ \delta'=\frac{\delta}{(\delta,k)}\Bigg|\frac{k\delta''}{(\delta,k)} \] 又因为\((\frac{\delta}{(\delta,k)},\frac{k}{(\delta,k)})=1\)，因此\(\delta'\mid\delta''\)；

• 另一方面，\(\delta\mid k\delta'\)，所以\(a^{k\delta'}\equiv(a^k)^{\delta'}\equiv1\pmod m\)，因此\(\delta''\mid\delta'\)。

综上\(\delta'=\delta''\)。

根据上述定理，可以得到定理4.3～4.5三条推论。

定理4.3：当\((k,\delta_m(a))=1\)时，\(\delta_m(a^k)=\delta_m(a)\)。

定理4.3即定理4.2的特殊情况，该结论十分重要。

定理4.4：在模\(m\)的一个既约剩余系中，至少有\(\varphi(\delta_m(a))\)个数对模\(m\)的指数等于\(\delta_m(a)\)。

证明：根据定理4.3，本定理就是要找有多少个\(k\)满足\((k,\delta_m(a))=1\)，显然它等于模\(\delta_m(a)\)的既约剩余类的数量，即\(\varphi(\delta_m(a))\)。之所以是至少，是因为\(a^k\)不一定能生成模\(m\)的剩余系中所有的元素，可能还有\(b\)（\(b\ne a^k\)）使得\(\delta_m(b)=\delta_m(a)\)，可以结合例4.1的第2个例子理解。

定理4.5（原根个数）：若\(g\)为模\(m\)的原根，则模\(m\)的原根个数为\(\varphi(\varphi(m))\)，并且 \[ \{g^k\mid(k,\varphi(m))=1,1\le k<\varphi(m)\} \] 即为所有原根的集合。

证明：将定理4.4中的\(\delta_m(a)\)替换为\(\varphi(m)\)即可得到原根个数为\(\varphi(\varphi(m))\)。此处没有至少，是因为\(g\)的指数为\(\varphi(m)\)，根据定理4.1第1条，\(g^k\)能生成模\(m\)的剩余系中所有的元素，因此不存在\(b\)（\(b\ne g^k\)）使得\(\delta_m(b)=\delta_m(g)\)。注意该定理的前提是模\(m\)有原根\(g\)，像例4.1的第二个例子是没有原根的，因此不适用该定理。

定理4.6：\(\delta_m(ab)=\delta_m(a)\delta_m(b)\)的充要条件是\((\delta_m(a),\delta_m(b))=1\)。

证明：先用两个例子理解一下，例4.1的第一个例子\(m=13\)。

• \(\delta_{13}(3)=3,\delta_{13}(4)=6\)，它们的指数不互素，显然有\(3^3\equiv4^6\equiv1\pmod{13}\)，因此\(3^1\equiv4^2\pmod{13}\)，所以\(3\times4\equiv4^3\pmod{13}\)，易知\(\delta_{13}(3\times4)=2\)；
• \(\delta_{13}(8)=4,\delta_{13}(9)=3\)，它们的指数互素，同理有\(8^1\equiv9^{3/4}\pmod{13}\)，所以\(8\times9\equiv9^{7/4}\pmod{13}\)，\(\frac{7}{4}\)只有乘\(12\)才是\(3\)的倍数，因此\(\delta_{13}(8\times9)=\delta_{13}(7)=12\)。

应该能从上面的例子找到一点感觉，下面正式开始证明。

设\(\delta=\delta_m(ab)\)，\(\delta'=\delta_m(a)\)，\(\delta''=\delta_m(b)\)，\(\eta=[\delta_m(a),\delta_m(b)]\)。

• 充分性：由\(1\equiv(ab)^\delta\equiv(ab)^{\delta\delta''}\equiv a^{\delta\delta''}\pmod m\)，可得\(\delta'\mid\delta\delta''\)，根据题意有\((\delta',\delta'')=1\)，因此\(\delta'\mid\delta\)，同理可得\(\delta''\mid\delta\)，所以\(\delta'\delta''\mid\delta\)。另一方面，\((ab)^{\delta'\delta''}\equiv1\pmod m\)，所以\(\delta\mid\delta'\delta''\)。综上\(\delta=\delta'\delta''\)。
• 必要性：因为\((ab)^\eta\equiv1\pmod m\)，所以\(\delta\mid\eta\)，由\(\delta=\delta'\delta''\)可得\(\delta'\delta''\mid\eta\)；另外显然\(\eta\mid\delta'\delta''\)。所以\(\delta'\delta''=\eta\)，即\((\delta',\delta'')=1\)。

接下来的几个定理与下一节的证明密切相关。

定理4.1第2条给出\(\delta_m(a)\mid\varphi(m)\)，当模为\(2\)的幂时，代入有\(\delta_{2^l}(a)\mid2^{l-1}\)，下面的定理4.7说明了该结论可以进一步强化。

定理4.7：\(\delta_{2^l}(a)\mid2^{l-2},\ l\ge3\)。

证明：该定理等价于：对于任意一个奇数\(a\)，有 \[ a^{2^{l-2}}\equiv1\pmod{2^l} \] 设\(a=2t+1\)，使用归纳法：

• 当\(l=3\)时，\(a^2\equiv4t(t+1)+1\equiv1\pmod{2^3}\)，成立；

• 假设当\(l=n\)（\(n\ge3\)）时定理成立，即 \[ a^{2^{n-2}}-1\equiv0\pmod{2^n} \]

• 当\(l=n+1\)时，有 \[ a^{2^{n-1}}-1\equiv(a^{2^{n-2}}-1)(a^{2^{n-2}}+1)\equiv0\pmod{2^n} \] 定理也成立，得证。

该定理同时也说明了：模\(2^l\)（\(l\ge3\)）无原根。

定理4.8：

• 若\(n\mid m\)，则\(\delta_n(a)\mid\delta_m(a)\)；
• 若\((m_1,m_2)=1\)，则\(\delta_{m_1m_2}(a)=[\delta_{m_1}(a),\delta_{m_2}(a)]\)。

证明：

• 由\(a^{\delta_m(a)}\equiv1\pmod m\)可得\(a^{\delta_m(a)}\equiv1\pmod n\)，因此\(\delta_n(a)\mid\delta_m(a)\)；
• 记\(\delta'=[\delta_{m_1}(a),\delta_{m_2}(a)]\)，由第1条有\(\delta_{m_1}(a)\mid\delta_{m_1m_2}(a)\)，\(\delta_{m_2}(a)\mid\delta_{m_1m_2}(a)\)，所以\(\delta'\mid\delta_{m_1m_2}(a)\)。另一方面，\(a^{\delta'}\equiv1\pmod{m_j},\ j=1,2\)，由\((m_1,m_2)=1\)可得\(a^{\delta'}\equiv1\pmod{m_1m_2}\)，因此\(\delta_{m_1m_2}(a)\mid\delta'\)。综上\(\delta_{m_1m_2}(a)=\delta'\)。

上述定理可以推广成如下更一般的形式。

定理4.9：若\(m=2^{\alpha_0}p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}\)，其中\(p_i\)是两两不同的奇素数，则\(\delta_m(a)\mid\lambda(m)\)，其中 \[ \lambda(m)=[2^{c_0},\varphi(p_1^{\alpha_1}),\cdots,\varphi(p_r^{\alpha_r})],\quad c_0= \begin{cases} 0&\alpha_0=0,1\\ 1&\alpha_0=2\\ \alpha_0-2&\alpha_0\ge3 \end{cases} \] 称为卡迈克尔（Carmichael）函数。

证明：推广定理4.8第2条可得 \[ \delta_m(a)=[\delta_{2^{\alpha_0}}(a),\delta_{p_1^{\alpha_1}}(a),\cdots,\delta_{p_r^{\alpha_r}}(a)] \] 根据定理4.7有\(\delta_{2^{\alpha_0}}(a)\mid2^{c_0}\)，另外\(\delta_{p_i^{\alpha_i}}(a)\mid\varphi(p_i^{\alpha_i})\)，所以 \[ [\delta_{2^{\alpha_0}}(a),\delta_{p_1^{\alpha_1}}(a),\cdots,\delta_{p_r^{\alpha_r}}(a)]\mid[2^{c_0},\varphi(p_1^{\alpha_1}),\cdots,\varphi(p_r^{\alpha_r})]=\lambda(m) \]

4.2 原根的存在和判定定理

定理4.10（原根存在定理）：模\(m\)有原根的充要条件是\(m=1,2,4,p^\alpha,2p^\alpha\)，其中\(p\)是奇素数，\(\alpha\ge1\)。

必要性证明：

转换为证明它的逆否命题：如果\(m\ne1,2,4,p^\alpha,2p^\alpha\)，则模\(m\)没有原根。

当\(m\ne1,2,4,p^\alpha,2p^\alpha\)时，可以分为以下两种情况：

• \(m=2^\alpha\)（\(a\ge3\)）：定理4.7已证；

• \(m=2^{\alpha_0}p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}\)（\(\alpha_0\ge2,r\ge1\)或\(\alpha_0\ge0,r\ge2\)）：将\(m\)代入卡迈克尔函数\(\lambda(m)\)可得 \[ \lambda(m)=[2^{c_0},p_1^{\alpha_1-1}(p_1-1),\cdots,p_1^{\alpha_r-1}(p_r-1)] \] 每一项至少能提出公因数\(2\)，因此\(\lambda(m)<\varphi(m)\)。结合定理4.9的\(\delta_m(a)\le\lambda(m)\)，可得\(\delta_m(a)<\varphi(m)\)，即模\(m\)没有原根。

充分性证明：

充分性证明较为复杂，可参考此处。大致思路为：

• 证明\(m=p\)时有原根；
• 证明\(m=p^\alpha,2p^\alpha\)时有原根；
• 证明其余情况没有原根。

求原根是一个十分困难的问题，没有一般方法。但在已知模数因式分解的情况下有如下较为简单的判定方法。

定理4.11（原根判定定理）：设\(m=1,2,4,p^\alpha,2p^\alpha\)，其中\(p\)是奇素数，\(\varphi(m)\)的所有不同的素因子为\(q_1,\cdots,q_s\)。那么\(g\)是模\(m\)的原根的充要条件是 \[ g^\frac{\varphi(m)}{q_j}\not\equiv1\pmod m,\quad j=1,\cdots,s \]

证明：

必要性显然，下面用反证法证明充分性。

假设存在一个\(g\)，满足\(g^\frac{\varphi(m)}{q_j}\not\equiv1\pmod m\)，但不是模\(m\)的原根，则存在\(t<\varphi(m)\)使得\(g^t\equiv1\pmod m\)。由裴蜀定理，存在一组\(x,y\)满足\(xt=y\varphi(m)+(t,\varphi(m))\)，则有 \[ 1\equiv g^{xt}\equiv g^{y\varphi(m)+(t,\varphi(m))}\equiv g^{(t,\varphi(m))}\pmod m \] 由假设知\((t,\varphi(m))\le t<\varphi(m)\)，因此存在\(\varphi(m)\)的素因子\(p\)使得\((t,\varphi(m))\mid\frac{\varphi(m)}{p}\)，则\(g^\frac{\varphi(m)}{p}\equiv g^{(t,\varphi(m))}\equiv1\pmod m\)，与假设矛盾，故原命题成立。

例4.2：证明\(2\)是模\(p=61\)的原根。

解：\(\varphi(p)=60=2^2\times3\times5\)。因为 \[ \begin{align} 2^\frac{60}{2}=2^{30}&\not\equiv1\pmod{61}\\ 2^\frac{60}{3}=2^{20}&\not\equiv1\pmod{61}\\ 2^\frac{60}{5}=2^{12}&\not\equiv1\pmod{61} \end{align} \] 所以\(2\)是模\(p=61\)的原根。

4.3 离散对数、既约剩余系的构造

如果模\(m\)的原根存在，则任一原根可以生成模\(m\)的既约剩余系，因此既约剩余系中的元素一定能表示成原根的某次方。

定义4.2：设\(g\)为模\(m\)的原根，给定\(a\)，如果\((a,m)=1\)，则存在唯一的\(\gamma\)，\(0\le\gamma<\varphi(m)\)，使得\(a\equiv g^\gamma\pmod m\)，称\(\gamma\)是\(a\)对模\(m\)的以\(g\)为底的离散对数（或指标），记作\(\gamma_{m,g}(a)\)或\(\text{ind}_{m,g}(a)\)，当模\(m\)与原根\(g\)很明确时也可以简记为\(\gamma_g(a),\gamma(a)\)或\(\text{ind}_g(a),\text{ind}(a)\)。

离散对数有如下性质。

定理4.12：设\(g\)是模\(m\)的原根，\(a,b\in\mathbb Z^*_m\)。

• \(g^h\equiv a\pmod m\)的充要条件是\(h\equiv\gamma_{m,g}(a)\pmod{\varphi(m)}\)；

• \(\gamma_{m,g}(ab)\equiv\gamma_{m,g}(a)+\gamma_{m,g}(b)\pmod{\varphi(m)}\)；

• 设\(g'\)是不同于\(g\)的原根，则 \[ \gamma_{m,g}(a)\equiv\frac{\gamma_{m,g'}(a)}{\gamma_{m,g'}(g)}\pmod{\varphi(m)} \]

说明：

• \(h=\gamma_{m,g}(a)\)是在模\(\varphi(m)\)的意义下的，因为\(g^{\varphi(m)}\equiv1\pmod m\)，加上或减去\(\varphi(m)\)没有影响；
• 即对数相加的公式；
• 即对数的换底公式。

下面的定理是关于离散对数与指数的关系的。

定理4.13：设\(g\)是模\(m\)的原根，\((a,m)=1\)，则 \[ \delta_m(a)=\frac{\varphi(m)}{(\gamma_{m,g}(a),\varphi(m))} \] 对每个正除数\(d\mid\varphi(m)\)，在模\(m\)的既约剩余系中恰有\(\varphi(d)\)个元素对模\(m\)的指数等于\(d\)。特别地，\(d=\varphi(m)\)时，恰有\(\varphi(\varphi(m))\)个原根。

证明：由定理4.2有 \[ \delta_m(a^k)=\frac{\delta_m(a)}{(k,\delta_m(a))} \] 令\(a=g,k=\gamma_{m,g}(a)\)，代入可得公式成立。

先体会一下后面那句话，如例4.1的第1个例子：指数\(d=4\)时，\(\varphi(4)=2\)，所以恰有2个元素的指数是\(4\)；\(d=6\)时，\(\varphi(6)=2\)，所以恰有2个元素的指数是\(6\)。下面给出证明。

根据定理4.2，元素\(g^i\)的指数等于\(d\)的充要条件是 \[ d=\delta_m(g^i)=\frac{\varphi(m)}{(i,\varphi(m))},\quad0\le i<\varphi(m) \] 即\((\varphi(m),i)=\frac{\varphi(m)}{d}\)，设\(i=t\cdot\frac{\varphi(m)}{d},0\le t<d\)，两边同时除以\(\frac{\varphi(m)}{d}\)则上式等价于\((d,t)=1\)，因此有\(\varphi(d)\)个\(t\)满足上式。

该定理应证了定理4.5。同时也要注意与定理4.4区分，定理4.4没有原根存在的前提，因此只能说至少。

原根存在的情况可以用原根生成既约剩余系，那原根不存在的情况该怎么办呢？比如模\(2^l\)（\(l\ge3\)）。下面的定理直接给出了模\(2^l\)（\(l\ge3\)）的既约剩余系构造方法，知道即可，证明省略。

定理4.14：在模\(m=2^l\)，\(l\ge3\)的既约剩余系中，如果存在一个元素\(g_0\)满足\(\delta_{2^l}(g_0)=2^{l-2}\)（事实上这样的\(g_0\)一定存在，如\(g_0=5\)），则 \[ \pm g_0^0,\pm g_0^1,\cdots,\pm g_0^{2^{l-2}-1} \] 为模\(m=2^l\)的一个既约剩余系。那么任给一个\(a\)，\((a,2)=1\)，\(a\)可以唯一地表示为 \[ a\equiv(-1)^{\gamma^{(-1)}}g_0^{\gamma^{(0)}},\quad0\le\gamma^{(-1)}<2,0\le\gamma^{(0)}<2^{l-2} \] 称\(\gamma^{(-1)},\gamma^{(0)}\)为\(a\)对模\(2^l\)的以\(-1,g_0\)为底的指标组。

最后来看一般既约剩余系的构造。

定理4.15：设模\(m=2^{\alpha_0}p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}\)，\(p_j(1\le j\le r)\)是两两不同的奇素数，\(g_j\)为模\(p_j^{\alpha_j}\)的原根，则 \[ M_0M_0^{-1}(-1)^{\gamma^{(-1)}}g_0^{\gamma^{(0)}}+M_1M_1^{-1}g_1^{\gamma^{(1)}}+\cdots+M_rM_r^{-1}g_r^{\gamma^{r}} \] 构成模\(m\)的一组既约剩余系。其中\(0\le\gamma^{(j)}<\varphi(p_j^{\alpha_j})\)，\(m=M_02^{\alpha_0}=M_jp_j^{\alpha_j}\)，\(M_jM_j^{-1}\equiv1\pmod{p_j^{\alpha_j}}\)。

上述定理中一些参数的取值没有详细给出，可以结合中国剩余定理理解，知道即可，证明省略。看下面的例子就懂了。

例4.3：求模\(m=2^3\times5^2\times7^2\times11^2\)的既约剩余系。

解：求得 \[ \begin{align} M_0&=5^2\times7^2\times11^2\equiv1\pmod{2^3},\quad M_0^{-1}\equiv1\pmod{2^3}\\ M_1&=2^3\times7^2\times11^2\equiv7\pmod{5^2},\quad M_1^{-1}\equiv-7\pmod{5^2}\\ M_2&=2^3\times5^2\times11^2\equiv-6\pmod{7^2},\quad M_2^{-1}\equiv8\pmod{7^2}\\ M_3&=2^3\times5^2\times7^2\equiv-1\pmod{11^2},\quad M_3^{-1}\equiv-1\pmod{11^2}\\ \end{align} \] 可以验证模\(5^2,7^2,11^2\)的原根分别为\(2,3,2\)，模\(2^3\)的原根取\(5\)。因此模\(m\)的既约剩余系为 \[ \begin{align} x=&5^2\times7^2\times11^2\times1\times(-1)^{\gamma^{(-1)}}\times5^{\gamma^{(0)}}+\\ &2^3\times7^2\times11^2\times(-7)\times2^{\gamma^{(1)}}+\\ &2^3\times5^2\times11^2\times8\times3^{\gamma^{(2)}}+\\ &2^3\times5^2\times7^2\times(-1)\times2^{\gamma^{(3)}} \end{align} \] 其中\(0\le\gamma^{(-1)}<2\)，\(0\le\gamma^{(0)}<2\)，\(0\le\gamma^{(1)}<20\)，\(0\le\gamma^{(2)}<42\)，\(0\le\gamma^{(3)}<110\)。

4.4 n次剩余

定义4.3：设\(m\ge2\)，\((a,m)=1\)，\(n\ge2\)。如果同余方程 \[ x^n\equiv a\pmod m \] 有解，则称\(a\)是模\(m\)的n次剩余；如果无解，就称\(a\)是模\(m\)的n次非剩余。

下面的定理给出了原根存在时n次剩余的充要条件。

定理4.16：设\(m\ge2\)，\((a,m)=1\)，模\(m\)有原根\(g\)，那么同余方程\(x^n\equiv a\pmod m\)有解的充要条件是 \[ (n,\varphi(m))\mid\gamma_{m,g}(a) \] 且方程有解时，恰有\((n,\varphi(m))\)个解。

证明：若\(x\equiv x_1\pmod m\)是方程的解，\(x_1\)与\(m\)必定互素，则必有\(y_1\)使得\(x_1\equiv g^{y_1}\pmod m\)，进而\(g^{ny_1}\equiv x_1^n\equiv a\pmod m\)。由定理4.12第1条可得 \[ ny_1\equiv\gamma_{m,g}(a)\pmod{\varphi(m)} \] 这是一个一次同余方程，由一次同余方程有解的充要条件（定理3.5）可得\((n,\varphi(m))\mid\gamma_{m,g}(a)\)，且解的个数为\((n,\varphi(m))\)。

需要说明的是，该定理从理论上给出了原根存在时求解同余方程\(x^n\equiv a\pmod m\)的方法，但实际上当模数非常大时，求\(\varphi(m)\)和\(\gamma_{m,g}(a)\)都是非常困难的问题。

例4.4：解同余方程\(x^{10}\equiv13\pmod{17}\)。

解：模\(17\)的原根为\(3\)，\(\gamma_{17,3}(13)=4\)，由上述定理可知同余方程有解，转换为 \[ 10y\equiv4\pmod{16} \] 该一次同余方程的解为\(2\)和\(-6\)，因此原方程的解为\(x\equiv3^2\equiv9\pmod{17}\)和\(x\equiv3^{-6}\equiv8\pmod{17}\)。

4.5 SageMath

sage: R = Zmod(13)
sage: a = R(4)
sage: a.multiplicative_order()	# 求a的指数
6
sage: primitive_root(13)		# 求模13的原根
2
sage: a.log(2)					# 求以2为底a的离散对数
2

# 求n次同余方程的一个根
sage: R = Zmod(17)
sage: a = R(13)
sage: a.nth_root(10)
9