Semi-Primitive Roots and Information Security

Zhongqi Zhou

Hubei Coal Geology Bureau, Wuhan, China.

DOI: 10.4236/oalib.1113181                

Abstract

In this paper, a new concept is proposed: semi-primitive root. The basic theory system of semi-primal roots is established, and the congruence equations and propositions of indefinite equations are solved by the theory of semi-primal roots. The security problem of using the same value to digitally sign multiple different information in discrete logarithm encryption is solved.

Keywords

Semi-Primitive Roots, Solving Congruence Equations, Proving Propositions of Indeterminate Equations, Encryption and Digital Signatures, Information Security

1. 引言

文中提出了一个新的概念：半原根。此概念是相对原根提出来的，所以，半原根得出的很多结论与原根的相类似。文章前半部分，建立了半原根的基本理论体系。后半部分给出了半原根的三方面的应用：

1) 用半原根理论解同余方程。

2) 用半原根理论证明不定方程的有关命题。

3) 用半原根加密和解密，解决了离散对数加密时用同一个值对多个不同的信息进行数字签名的安全问题。

2. 半原根的定义

设$m\ge 3,\left(g,m\right)=1$ ，若$g^{\frac{\phi \left(m\right)}{2}}\equiv 1\left(\mathrm{mod}m\right)$ 且$1\le k<\frac{\phi \left(m\right)}{2},g^k\bcancel{\equiv }\pm 1\left(\mathrm{mod}m\right)$ 时称$g$ 为$m$ 的半原根。

为区别起见，将$\left(a,m\right)=1$ ，$a^{\phi \left(m\right)}\equiv 1\left(\mathrm{mod}m\right)$ 且当$1\le k<\phi \left(m\right)$ 时，$a^k\bcancel{\equiv }1\left(\mathrm{mod}m\right)$ 则称$a$ 为$m$ 的原根。

3. 半原根存在的必要条件

设$g$ 是$m=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_r^{{\alpha }_r}$ 的半原根，$p_1,p_2,\cdots p_r$ 为不同的素数，因$\left(g,m\right)=1$ ，所以

$\left(g,p_i^{{\alpha }_i}\right)=1,1\le i\le r$ ，则

$g^{\phi \left(p_i^{{\alpha }_i}\right)}\equiv 1\left(\mathrm{mod}{p}_i^{{\alpha }_i}\right)$

令$h=\left[\phi \left(p_1^{{\alpha }_1}\right),\cdots ,\phi \left(p_r^{{\alpha }_r}\right)\right]$ ，则

$g^h\equiv 1\left(\mathrm{mod}{p}_i^{{\alpha }_i}\right)$ 和$g^h\equiv 1\left(\mathrm{mod}m\right)$

所以$\frac{\phi \left(m\right)}{2}|h$ ，或者

$\frac{\left(\phi \left(p_1^{{\alpha }_1}\right)\phi \left(p_2^{{\alpha }_2}\right)\cdots \phi \left(p_r^{{\alpha }_r}\right)\right)}{2}|\left[\phi \left(p_1^{{\alpha }_1}\right),\phi \left(p_2^{{\alpha }_2}\right),\cdots ,\phi \left(p_r^{{\alpha }_r}\right)\right]$

而$\phi \left(2^k\right)=2^{k-1},\phi \left(p_i^{{\alpha }_i}\right)=p^{{\alpha }_i-1}\left(p_i-1\right)$ ，于是，$m$ 的不同奇素因子不能多于2个，若偶素因子2与两个奇素因子$p,q$ 同时存在，那么，2的幂次不能大于1，且$\left(p-1,q-1\right)=2$ ；如果偶素因子2与一个奇素因子同时存在，且2的幂次大于2，则奇素因子不能为$4n+1$ ；若只有两个奇素因子$p,q$ 同时存在，则$\left(p-1,q-1\right)=2$ 。

4. 哪些数有半原根

根据以上半原根存在的必要条件，并用证明存在原根的数的充分条件相类似的方法可以证明以下形式的数存在半原根：

$2^k$ $k\ge 2$

$2^k{p}^{\alpha }$ $p$ 为素数，$p\equiv -1\left(\mathrm{mod}4\right),0\le k\le 2$ 。

$4p^{\alpha }$ $p$ 为素数，$\alpha \ge 1$ 。

$p^{\alpha }{q}^{\beta }$ $p,q$ 均为素数，$\alpha \ge 1,\beta \ge 1,\left(p-1,q-1\right)=2$ 。

$2p^{\alpha }{q}^{\beta }$ $p,q$ 均为素数，$\alpha \ge 1,\beta \ge 1,\left(p-1,q-1\right)=2$ 。

下面仅就$m=p^r$ 和$m=p^r{q}^s$ 存在半原根进行证明，其余的证明可参考文献[1]：

1) 设$g$ 模$p$ 之阶为$\lambda$ ，并设$g^{\lambda }=1+tp,{\left(g-p\right)}^{\lambda }=1+\mu p$ ，则$t$ 和$\mu$ 这两个数中

至少有一个不是$p$ 之倍数。

证：若$p\bcancel{|}t$ ，则结论已明，若$p|t$ ，则

${\left(g-p\right)}^{\lambda }\equiv g^{\lambda }-\lambda p{g}^{\frac{p-3}{2}}\equiv 1-\lambda p{g}^{\frac{p-3}{2}}\left(\mathrm{mod}{p}^2\right)$

即

${\left(g-p\right)}^{\lambda }=1-\lambda p{g}^{\frac{p-3}{2}}+p^{2}x=1+\left(px-\lambda g^{\frac{p-3}{2}}\right)p$

则$\mu =px-\lambda g^{\frac{p-3}{2}}$ 。由于$\left(\lambda ,p\right)=\left(g,p\right)=\left(g^{\frac{p-3}{2}},p\right)=1$ ，所以$p\bcancel{|}\mu$ ，得证。

2) $p\equiv -1\left(\mathrm{mod}4\right)$ 为奇素数，$m=p^r$ ，设$r>1$ ，$g$ 是$p$ 的半原根，并设$g^{\frac{p-1}{2}}=1+tp$ ，${\left(g-p\right)}^{\frac{p-1}{2}}=1+\mu p$ ，则

① 若$p\bcancel{|}t$ 则$g$ 是$p^r$ 的半原根。

② 若$p|t$ ，则$g-p$ 是$p^r$ 的半原根。

证：① 设$p\bcancel{|}t$ ，由$g^{\frac{p-1}{2}}=1+tp$

得 ${\left(g^{\frac{p-1}{2}}\right)}^p={\left(1+tp\right)}^p=1+t{p}^2+\frac{p\left(p-1\right)}{2}{t}^2{p}^2+\cdots$

则 ${\left(g^{\frac{p-1}{2}}\right)}^p=1+t{p}^2\left(\mathrm{mod}{p}^3\right)$

${\left(g^{\frac{p-1}{2}}\right)}^{p^{r-2}}\equiv 1+t{p}^{r-1}\left(\mathrm{mod}{p}^r\right)$ (1)

${\left(g^{\frac{p-1}{2}}\right)}^{p^{r-1}}\equiv 1\left(\mathrm{mod}{p}^r\right)$ (2)

设$g$ 模$p^r$ 其阶为$n$ ，即$g^n\equiv 1\left(\mathrm{mod}{p}^r\right)$ ，则$n|p^{r-1}\left(p-1\right)=\phi \left(p^r\right)$ ，因$g^n\equiv 1\left(\mathrm{mod}{p}^r\right)$ 和$g^n\equiv 1\left(\mathrm{mod}p\right)$ ，所以$\frac{p-1}{2}|n$ ，如果$n<p^{r-1}\left(\frac{p-1}{2}\right)$ ，则$n$ 必须是$\frac{p^{r-2}\left(p-1\right)}{2}$ 的约数，则应有$g^{p^{r-2}\left(\frac{p-1}{2}\right)}\equiv 1\left(\mathrm{mod}{p}^r\right)$ ，但根据(1)和$p\bcancel{|}t$ ，此不可。如果$n>\frac{p^{r-1}\left(p-1\right)}{2}$ ，那么必有：$g^{p^{r-1}\left(p-1\right)}\equiv 1\left(\mathrm{mod}{p}^r\right)$ ，但根据(2)此亦不可。只有$n=\frac{p^{r-1}\left(p-1\right)}{2}=\frac{\phi \left(p^r\right)}{2}$ 。再若$g^k\equiv -1\left(\mathrm{mod}{p}^r\right)$ ，$0<k<\frac{\phi \left(p^r\right)}{2}$ ，则有$g^{2k}\equiv 1\left(\mathrm{mod}{p}^r\right)$ ，从而$\frac{p^{r-1}\left(p-1\right)}{2}|2k$ ，因$2k<\phi \left(p^r\right)$ ，只有$k=\frac{\phi \left(p^r\right)}{4}$ ，因$p$ 有半原根，$p\equiv -1\left(\mathrm{mod}4\right)$ ，$k=\frac{\phi \left(p^r\right)}{4}=\frac{p^r\left(p-1\right)}{4}$ 不为整数，故$g$ 是$p^r$ 的半原根。

② 若$p|t$ ，则由1)得知：$p\bcancel{|}\mu$ ，因$g-p$ 也是$p$ 的半原根，同理可证，$g-p$ 是$p^r$ 的半原根。

3) $m=p^r{q}^s$ ，$p,q$ 均为奇质数，$r,s$ 为自然数。若$g$ 既是$p$ 的半原根，也是$q$ 的原根，且$\left(\phi \left(p\right),\phi \left(q\right)\right)=2$ ，则$g$ 是$m$ 的半原根。

证：因为$g$ 是$p$ 的半原根，根据(2)可知$g$ 或$g-p$ 为$p^r$ 的半原根，所以就有$g^{\frac{p^{r-1}\left(p-1\right)}{2}}\equiv 1\left(\mathrm{mod}{p}^r\right)$ ，也有$g^{\frac{p^{r-1}\left(p-1\right)q^{s-1}\left(q-1\right)}{2}}\equiv 1\left(\mathrm{mod}{p}^r\right)$ 。又因$g$ 也是$q$ 的原根，那么，$g$ 或$g-q$ 为$g^s$ 的原根，所以有$g^{q^{s-1}\left(q-1\right)}\equiv 1\left(\mathrm{mod}{q}^s\right)$ ，也有$g^{\frac{p^{r-1}\left(p-1\right)q^{s-1}\left(q-1\right)}{2}}\equiv 1\left(\mathrm{mod}{q}^s\right)$ ，所以$g^{\frac{p^{r-1}\left(p-1\right)q^{s-1}\left(q-1\right)}{2}}\equiv 1\left(\mathrm{mod}{p}^r{q}^s\right)$ 。若存在：$n$ $<$ $\frac{\phi \left(m\right)}{2}$ 使得$g$ 模$m$ 之阶为$n$ ，即$g^n\equiv 1\left(\mathrm{mod}m\right)$ ，就会有$g^n\equiv 1\left(\mathrm{mod}{p}^r\right)$ 和$g^n\equiv 1\left(\mathrm{mod}{q}^s\right)$ ，所以有$\frac{p^r\left(p-1\right)}{2}|n$ 和$q^{s-1}\left(q-1\right)|n$ 。即$\left[\frac{p^{r-1}\left(p-1\right)}{2},\frac{q^{s-1}\left(q-1\right)}{2}\right]\le n$ 因$\left(\phi \left(p\right),\phi \left(q\right)\right)=2$ ，所以$n\ge \frac{p^{r-1}\left(p-1\right)q^{s-1}\left(q-1\right)}{2}$ ，显然与原设矛盾。故$g$ 模$m$ 之阶为$\frac{\phi \left(m\right)}{2}$ 。再若存在$n<\frac{\phi \left(m\right)}{2}$ ，使得$g^n\equiv -1\left(\mathrm{mod}m\right)$ ，就会有$g^{2n}\equiv 1\left(\mathrm{mod}m\right)$ 。

则$\frac{\phi \left(m\right)}{2}|2n$ ，因$n<\frac{\phi \left(m\right)}{2}$ ，只有$n=\frac{\phi \left(m\right)}{4}=\frac{p^{r-1}\left(p-1\right)q^{s-1}\left(q-1\right)}{4}$ 或$g^{\frac{p^{r-1}\left(p-1\right)q^{s-1}\left(q-1\right)}{4}}\equiv -1\left(\mathrm{mod}m\right)$ ，并推出：$g^{\frac{p^{r-1}\left(p-1\right)q^{s-1}\left(q-1\right)}{4}}\equiv -1\left(\mathrm{mod}p\right)$ 。但由于$g$ 是$p$ 的半原根，所以$g^{\frac{p-1}{2}}\equiv 1\left(\mathrm{mod}p\right)$ ，$g^{\frac{\phi \left(m\right)}{2}}\equiv 1\left(\mathrm{mod}p\right)$ 。

当$g$ 为奇数时：$\left(g^{\frac{\phi \left(m\right)}{4}}+1,g^{\frac{\phi \left(m\right)}{4}}-1\right)=2$

当$g$ 为偶数时：$\left(g^{\frac{\phi \left(m\right)}{4}}+1,g^{\frac{\phi \left(m\right)}{4}}-1\right)=1$

又因$p$ 为奇素数，所以$g^{\frac{\phi \left(m\right)}{4}}\bcancel{\equiv }-1\left(\mathrm{mod}p\right)$ ，故$g^{\frac{\phi \left(m\right)}{4}}\bcancel{\equiv }-1\left(\mathrm{mod}m\right)$ 。

得证。

5. 半原根的相关定理

定理1. 若$a$ 是$m$ 的半原根，则$\pm a,\pm a^2,\cdots ,\pm a^{\frac{\phi \left(m\right)}{2}}$ 为$m$ 的简化剩余系。

证：$\pm a,\pm a^2,\cdots \pm a^{\frac{\phi \left(m\right)}{2}}$ 共有$\phi \left(m\right)$ 个数，如果$\pm a^i\equiv \pm a^j\left(\mathrm{mod}m\right),1\le i<j\le \frac{\phi \left(m\right)}{2}$ ，则会有$a^{j-i}\equiv 1\left(\mathrm{mod}m\right)$ 或$a^{j-i}\equiv -1\left(\mathrm{mod}m\right)$ ，由于$j-i<\frac{\phi \left(m\right)}{2}$ ，由半原根的定义，因此不可；如果$a^i\equiv -a^i\left(\mathrm{mod}m\right)$ ，因$\left(a,m\right)=1$ ，则会有$2\equiv 0\left(\mathrm{mod}m\right)$ ，也不可。

定理2. 设$m\ge 3$ 为正整数，$\overline{\phi \left(m\right)}$ 为所有小于$m$ 且与$m$ 互素的正整数之积，如果$m$ 存在半原根，则

$\overline{\phi \left(m\right)}\equiv {\left(-1\right)}^{\frac{\phi \left(m\right)}{2}}\left(\mathrm{mod}m\right)$

证：设$a$ 是$m$ 的半原根，因$\pm a,\pm a^2,\cdots ,\pm a^{\frac{\phi \left(m\right)}{2}}$ 是$m$ 的简化剩余系，则有

$a{a}^2\cdots a^{\frac{\phi \left(m\right)}{2}}\left(-a\right)\left(-a^2\right)\cdots \left(-a^{\frac{\phi \left(m\right)}{2}}\right)\equiv \overline{\phi \left(m\right)}\left(\mathrm{mod}m\right)$

${\left(-1\right)}^{\frac{\phi \left(m\right)}{2}}\times a^{\frac{\phi \left(m\right)}{2}\left(\frac{\phi \left(m\right)}{2}+1\right)}\equiv \overline{\phi \left(m\right)}\left(\mathrm{mod}m\right)$

因$a^{\frac{\phi \left(m\right)}{2}\left(\frac{\phi \left(m\right)}{2}+1\right)}\equiv 1\left(\mathrm{mod}m\right)$ ，所以

$\overline{\phi \left(m\right)}\equiv {\left(-1\right)}^{\frac{\phi \left(m\right)}{2}}\left(\mathrm{mod}m\right)$

定理3. 设$n\ge 0,k\ge 3$ ，则$8n+3,8n+5$ 均为$2^k$ 的半原根。

证：先设$8n+3<2^k$ ，$8n+5<2^k$ ，此时$n$ 可取$2^{k-3}$ 个数，$n$ 分别为：$0,1,2,\cdots ,2^{k-3}-1$ ，共$2\times 2^{k-3}=2^{k-2}$ 个数。而${\left(8n+1\right)}^{2^{k-3}}\equiv 1\left(\mathrm{mod}{2}^k\right)$ ，${\left(8n+7\right)}^{2^{k-3}}\equiv 1\left(\mathrm{mod}{2}^k\right)$ 。因$2^{k-3}<\frac{\phi \left(2^k\right)}{2}$ ，所以，$8n+1,8n+7$ 均不为$2^k$ 的半原根。而不大于$2^k$ 的$8n+1$ 和$8n+7$ 的数也有$2^{k-2}$ 个，根据下面“半原根的个数”知$2^k$ 的半原根有$\phi \left(\phi \left(2^k\right)\right)=2^{k-2}$ 个，且无偶数，所以$8n+3,8n+5$ 均为$2^k$ 的半原根。

又因当$8m+3,8m+5$ 均大于$2^k$ 时，总可以找到$i$ 使得

$m\equiv i\left(\mathrm{mod}{2}^{k-3}\right)$ ，$0\le i\le 2^{k-3}-1$ 。

即有

$8n+3\equiv 8m+3\left(\mathrm{mod}{2}^k\right),8n+5\equiv 8m+5\left(\mathrm{mod}{2}^k\right)$ 。所以全体$8n+3,8n+5$ 均为$2^k$ 的半原根，得证。

定理4. 设$g$ 为$m$ 的半原根，$a,b,c$ 均为已知整数，$\left(a,m\right)=\left(b,m\right)=\left(c,m\right)=1$ ，

$1\le i,j,k\le \frac{\phi \left(m\right)}{2}$ ，则同余式

$a{c}^x\equiv b\left(\mathrm{mod}m\right)$ (5)

① 当$a\equiv \pm g^i,b\equiv \pm g^j,c\equiv g^k\left(\mathrm{mod}m\right)$ ，则(5)式有解的充要条件为$d=\left(k,\frac{\phi \left(m\right)}{2}\right)|\left(j-i\right)$ ；

② 当$a\equiv \pm g^i,b\equiv \pm g^j,c\equiv -g^k\left(\mathrm{mod}m\right)$ ，则同余式有解的充要条件$x\equiv 0\left(\mathrm{mod}2\right)$ 且$d=\left(k,\frac{\phi \left(m\right)}{2}\right)|\left(j-i\right)$ ；

③ 当$a\equiv \pm g^i,b\equiv \mp g^j,c\equiv -g^k\left(\mathrm{mod}m\right)$ ，则同余式有解的充要条件$x\equiv 1\left(\mathrm{mod}2\right)$ 且$d=\left(k,\frac{\phi \left(m\right)}{2}\right)|\left(j-i\right)$ ；

④ $a\equiv \pm g^i,b\equiv \mp g^j,c\equiv g^k\left(\mathrm{mod}m\right)$ ，则同余式无解。

证：① (5)式可变形为：

$kx\equiv j-i\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ ， (6)

(6)有解的充要条件为$d=\left(k,\frac{\phi \left(m\right)}{2}\right)|\left(j-i\right)$ ，且若有解，恰有$d$ 个不同余的解，

(5)式也有$d$ 个不同余的解。

② (5)式可变为：

$x\left(in{d}_g\left(-1\right)+k\right)\equiv j-i\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$

或

$in{d}_g{\left(-1\right)}^x+xk\equiv j-i\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ ， (7)

当$x\equiv 0\left(\mathrm{mod}2\right)$ 且$d=\left(k,\frac{\phi \left(m\right)}{2}\right)|\left(j-i\right)$ ，则(7)有$d$ 个不同余的解，(5)也有$d$ 个不同余的解。当$x\equiv 1\left(\mathrm{mod}2\right)$ 或$d=\left(k,\frac{\phi \left(m\right)}{2}\right)\bcancel{|}\left(j-i\right)$ ，则(7)无解，(5)也无解。

③ (5)可变为：

$x\left(in{d}_g\left(-1\right)+k\right)\equiv in{d}_g\left(-1\right)+j-i\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$

或

$\left(x-1\right)\left(in{d}_g\left(-1\right)\right)+xk\equiv j-i\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ ， (8)

当$\left(x-1\right)\equiv 0\left(\mathrm{mod}2\right)$ 且有$d=\left(k,\frac{\phi \left(m\right)}{2}\right)|\left(j-i\right)$ ，则(8)有解且有$d$ 个不同余的解，(5)也有个不同余的解；当$\left(x-1\right)\bcancel{\equiv }0\left(\mathrm{mod}2\right)$ 或$d=\left(k,\frac{\phi \left(m\right)}{2}\right)\bcancel{|}\left(j-i\right)$ ，则(8)无解，(5)也无解。

④ (5)可变为：

$xk\equiv in{d}_g\left(-1\right)+j-i\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ 或

$in{d}_g\left(-1\right)\equiv j-i-xk\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ ， (9)

因$j,i,x,f$ 均为整数，所以(9)无解，(5)也无解。得证。

6. 半原根的个数

若$m$ 存在半原根，其个数必为$\phi \left(\phi \left(m\right)\right)$ 个。

我们知道：存在半原根的$m$ 必为以下形式的数：

$2^k$ $\left(k\ge 2\right)$

$p^{\alpha },2p^{\alpha }$ $p$ 为奇素数，$p\equiv -1\left(\mathrm{mod}4\right)$ ，$\alpha$ 自然数。

$4p^{\alpha }$ $p$ 为奇素数，$\alpha$ 自然数。

$p^{\alpha }{q}^{\beta },2p^{\alpha }{q}^{\beta }$ $p,q$ 为奇素数，$\left(p-1,q-1\right)=2$ ，$\alpha ,\beta$ 为自然数。

现分别加以证明：

① 设$m=2^k$ ($k\ge 2$ )

当$k=2$ 时，$m=4$ ，其半原根仅有一个1，而$\phi \left(\phi \left(4\right)\right)=1$ 。

当$k=3$ 时，$m=8$ ，其半原根为3和5，而$\phi \left(\phi \left(8\right)\right)=2$ 。

当$k>3$ 时，设$g$ 为$m$ 的半原根，则$g,g^2,\cdots ,g^{\frac{\phi \left(m\right)}{2}}$ 模$m$ 两两互不同余，若$\left(i,\frac{\phi \left(m\right)}{2}\right)=1,i=1,2,\cdots ,\frac{\phi \left(m\right)}{2}-1$ ，则$g^i$ 模$m$ 之阶也为$\frac{\phi \left(m\right)}{2}$ ，而不大于$\frac{\phi \left(m\right)}{2}$ 且与$\frac{\phi \left(m\right)}{2}$ 互质的数有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个，即在$g,g^2,\cdots ,g^{\frac{\phi \left(m\right)}{2}}$ 中共有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个$g^i$ 关于$m$ 之阶为$\frac{\phi \left(m\right)}{2}$ 。若${\left(g^i\right)}^{\frac{\phi \left(m\right)}{2}}\equiv 1\left(\mathrm{mod}m\right)$ $\left(i,\frac{\phi \left(m\right)}{2}\right)=1$ ，还存在$n<\frac{\phi \left(m\right)}{2}$ ，使${\left(g^i\right)}^n\equiv -1\left(\mathrm{mod}m\right)$ ，则${\left(g^i\right)}^{2n}\equiv 1\left(\mathrm{mod}m\right)$ ，就会有$\frac{\phi \left(m\right)}{2}|2n$ ，可得$n=\frac{\phi \left(m\right)}{4}=2^{k-3}$ ，或${\left(g^i\right)}^{2^{k-3}}\equiv -1\left(\mathrm{mod}{2}^k\right)$ ，由于$g$ 为奇数，$g^i$ 也为奇数，设$g^i=2q+1$ ，$q$ 为整数，则${\left(g^i\right)}^{2^{k-3}}={\left(2q+1\right)}^{2^{k-3}}=1+2^{k-2}q+2^{k-2}{q}^2\left(2^{k-3}-1\right)+2^{k}t$ ，$t$ 为整数。

若${\left(g^i\right)}^{2^{k-3}}\equiv -1\left(\mathrm{mod}{2}^k\right)$ ，则有$2\left(1+2^{k-3}\left(q+q^2\left(2^{k-3}-1\right)\right)\right)\equiv 0\left(\mathrm{mod}{2}^k\right)$ ，显然不可，即$g^i$ 为$m$ 的半原根。

又因$\frac{\phi \left(m\right)}{2}$ 为偶数，显然有：${\left(-g^i\right)}^{\frac{\phi \left(m\right)}{2}}\equiv 1\left(\mathrm{mod}m\right)$ ，

若存在$n<\frac{\phi \left(m\right)}{2}$ ，使${\left(-g^i\right)}^n\equiv \pm 1\left(\mathrm{mod}m\right)$ ，此时若$n$ 为偶数，则有${\left(g^i\right)}^n\equiv 1\left(\mathrm{mod}m\right)$ 此不可；若$n$ 为奇数，则有${\left(g^i\right)}^n\equiv \mp 1\left(\mathrm{mod}m\right)$ ，也不可，所以，$-g^i$ 也为$m$ 的半原根，显然在$\pm g$ ，$\pm g^2$ ，$\cdots$ ，$g^{\frac{\phi \left(m\right)}{2}}$ 中再无其他半原根，所以$2^k$ 共有$2\phi \left(\frac{\phi \left(2^k\right)}{2}\right)=\phi \left(\phi \left(2^k\right)\right)$ 个半原根。

② 设$m=p^{\alpha }$ ，$p$ 为奇素数，$p\equiv -1\left(\mathrm{mod}4\right)$ ，$\alpha$ 为自然数。并设$g$ 为$m$ 的半原根，则

$g$ ，$g^2$ ，$\cdots$ ，$g^{\frac{\phi \left(m\right)}{2}}$ 模$m$ 两两互不同余，设$i=1,2,\cdots ,\frac{\phi \left(m\right)}{2}-1$ 。若$\left(i,\frac{\phi \left(m\right)}{2}\right)=1$ ，则$g^i$ 模$m$ 之阶为$\frac{\phi \left(m\right)}{2}$ ，且有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个，再若存在$n<\frac{\phi \left(m\right)}{2}$ ，使得${\left(g^i\right)}^n\equiv -1\left(\mathrm{mod}m\right)$ ，就有$n=\frac{\phi \left(m\right)}{4}=\frac{p^{\alpha -1}\left(p-1\right)}{4}$ ，因$p\equiv -1\left(\mathrm{mod}4\right)$ ，则$n$ 不为整数，故不可，即$g^i$ 为$m$ 之半原根，且在$g$ ，$g^2$ ，$\cdots$ ，$g^{\frac{\phi \left(m\right)}{2}}$ 中共有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个半原根。因$\frac{\phi \left(m\right)}{2}$ 为奇数，若有${\left(-g^i\right)}^{\frac{\phi \left(m\right)}{2}}\equiv 1\left(\mathrm{mod}m\right)$ ，则${\left(g^i\right)}^{\frac{\phi \left(m\right)}{2}}\equiv -1\left(\mathrm{mod}m\right)$ ，因$g^i$ 为$m$ 之半原根，此不可。即$-g^i$ 不为$m$ 之半原根，显然，在$g$ ，$g^2$ ，$\cdots$ ，$g^{\frac{\phi \left(m\right)}{2}}$ 中，仅有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个为$m$ 的半原根，又因当$p\equiv -1\left(\mathrm{mod}4\right)$ 时，有$\phi \left(\phi \left(m\right)\right)=\phi \left(\frac{\phi \left(m\right)}{2}\right)$ ，故$p^{\alpha }$ 有$\phi \left(\phi \left(p^{\alpha }\right)\right)$ 个$m$ 的半原根。

$m=2p^r$ 的半原根个数，$p$ 为奇素数，$p\equiv -1\left(\mathrm{mod}4\right)$ ，可仿②证明之。

③ 设$m=4p^{\alpha }$ ，$p$ 为奇素数，$\alpha$ 为自然数，设$g$ 为$m$ 的半原根，同上理，在$g$ ，$g^2$ ，$\cdots$ ，$g^{\frac{\phi \left(m\right)}{2}}$ 中有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个数模$m$ 之阶为$\frac{\phi \left(m\right)}{2}$ ，设$\left(i,\frac{\phi \left(m\right)}{2}\right)=1$ ，$i=1,2,\cdots ,\frac{\phi \left(m\right)}{2}-1$ 。若存在$n<\frac{\phi \left(m\right)}{2}$ ，使得：${\left(g^i\right)}^n\equiv -1\left(\mathrm{mod}m\right)$ ，则必有：${\left(g^i\right)}^{2n}\equiv 1\left(\mathrm{mod}m\right)$ ，也必有：$n=\frac{\phi \left(m\right)}{4}=\frac{p^{\alpha -1}\left(p-1\right)}{2}$ ，若$p\equiv 1\left(\mathrm{mod}4\right)$ ，因$g$ 为奇数，$n$ 为偶数，则${\left(g^i\right)}^n\bcancel{\equiv }-1\left(\mathrm{mod}4p^{\alpha }\right)$ ；

若$p\equiv -1\left(\mathrm{mod}4\right)$ ，${\left(g^i\right)}^n\equiv g^{\frac{p^{\alpha -1}\left(p-1\right)i}{2}}\equiv 1\left(\mathrm{mod}{p}^r\right)$ ，从而有${\left(g^i\right)}^n\bcancel{\equiv }-1\left(\mathrm{mod}{p}^{\alpha }\right)$ ，也有${\left(g^i\right)}^{\frac{p^{\alpha -1}\left(p-1\right)}{2}}\bcancel{\equiv }-1\left(\mathrm{mod}4p^{\alpha }\right)$ 。若$g$ 为$p^{\alpha }$ 的原根，则$g$ $\equiv 1\left(\mathrm{mod}4\right)$ ，所以${\left(g^i\right)}^{\frac{p^{\alpha -1}\left(p-1\right)}{2}}\equiv 1\left(\mathrm{mod}4\right)$ ，${\left(g^i\right)}^{\frac{p^{\alpha -1}\left(p-1\right)}{2}}\bcancel{\equiv }-1\left(\mathrm{mod}4p^{\alpha }\right)$ 。即$g^i$ 为$m$ 的半原根，且在$g$ ，$g^2$ ，$\cdots$ ，$g^{\frac{\phi \left(m\right)}{2}}$ 中共有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个。

显然${\left(-g^i\right)}^{\frac{\phi \left(m\right)}{2}}\equiv 1\left(\mathrm{mod}m\right)$ ，若存在$n<\frac{\phi \left(m\right)}{2}$ ，使${\left(-g\right)}^n\equiv \pm 1\left(\mathrm{mod}m\right)$ 则当$n$ 为偶数时，${\left(g^i\right)}^n\equiv \pm 1\left(\mathrm{mod}m\right)$ ，当为奇数时，${\left(g^i\right)}^n\equiv \mp 1\left(\mathrm{mod}m\right)$ ，均不可，故在$g$ ，$g^2$ ，$\cdots$ ，$g^{\frac{\phi \left(m\right)}{2}}$ 中也有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个$m$ 的半原根。又因$\phi \left(\phi \left(m\right)\right)=2\phi \left(\frac{\phi \left(m\right)}{2}\right)$ ，故$4p^{\alpha }$ 共有$\phi \left(\phi \left(4p^{\alpha }\right)\right)$ 个半原根。

④ 设$m=p^{\alpha }{q}^{\beta }$ ，$\left(p-1,q-1\right)=2$ ，$\alpha ,\beta$ 为自然数，设$g$ 是$m$ 的半原根，则$g$ ，$g^2$ ，$\cdots$ ，$g^{\frac{\phi \left(m\right)}{2}}$ 模$m$ 两两互不同余，若$\left(i,\frac{\phi \left(m\right)}{2}\right)=1$ ，$i=1,2,\cdots ,\frac{\phi \left(m\right)}{2}-1$ 。则$g^i$ 模$m$ 之阶为$\frac{\phi \left(m\right)}{2}$ ，而不大于$\frac{\phi \left(m\right)}{2}$ 且与$\frac{\phi \left(m\right)}{2}$ 互质的数有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个，即在$g$ ，$g^2$ ，$\cdots$ ，$g^{\frac{\phi \left(m\right)}{2}}$ 中，共有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个$g^i$ 关于$m$ 之阶为$\frac{\phi \left(m\right)}{2}$ 。再若${\left(g^i\right)}^{\frac{\phi \left(m\right)}{2}}\equiv 1\left(\mathrm{mod}m\right)$ ，$\left(i,\frac{\phi \left(m\right)}{2}\right)=1$ 时，还存在$n<\frac{\phi \left(m\right)}{2}$ ，使${\left(g^i\right)}^n\equiv -1\left(\mathrm{mod}m\right)$ ，则应有$n=\frac{\phi \left(m\right)}{4}=\frac{p^{\alpha -1}\left(p-1\right)q^{\beta -1}\left(q-1\right)}{4}$ ，即有${\left(g^i\right)}^{\frac{\phi \left(m\right)}{4}}\equiv -1\left(\mathrm{mod}m\right)$ ，但因$\left(\phi \left(p^{\alpha }\right),\phi \left(q^{\beta }\right)\right)=2$ ，则必有$p\equiv -1\left(\mathrm{mod}4\right),q\equiv -1\left(\mathrm{mod}4\right)$ 或$p\equiv -1\left(\mathrm{mod}4\right),q\equiv 1\left(\mathrm{mod}4\right)$ 或$p\equiv 1,q\equiv -1\left(\mathrm{mod}4\right)$ 。现设$p\equiv -1\left(\mathrm{mod}4\right),q\equiv -1\left(\mathrm{mod}4\right)$ ，则${\left(g^{q^{\beta -1}\left(q-1\right)}\right)}^{\frac{p^{\alpha }\left(p-1\right)i}{4}}\equiv 1\left(\mathrm{mod}{p}^r\right)$ ，${\left(g^i\right)}^{\frac{\phi \left(m\right)}{4}}\equiv 1\left(\mathrm{mod}{p}^r\right)$ ，则有${\left(g^i\right)}^{\frac{\phi \left(m\right)}{4}}\bcancel{\equiv }-1\left(\mathrm{mod}m\right)$ ，同理若$p\equiv -1,q\equiv 1\left(\mathrm{mod}4\right)$ ，也有${\left(g^i\right)}^{\frac{\phi \left(m\right)}{4}}\bcancel{\equiv }-1\left(\mathrm{mod}m\right)$ 。

再若$p\equiv -1,q\equiv -1\left(\mathrm{mod}4\right)$ ，则$g$ 为$p^{\alpha }$ 的半原根或为$q^{\beta }$ 的半原根，不妨设$g$ 为$p^{\alpha }$ 的半原根，则$g^{\frac{p^{\alpha -1}\left(p-1\right)}{2}}\equiv 1\left(\mathrm{mod}{p}^{\alpha }\right)$ ，也有${\left(g^{\frac{p^{\alpha -1}\left(p-1\right)}{2}}\right)}^{\frac{q^{\beta -1}\left(q-1\right)i}{2}}\equiv 1\left(\mathrm{mod}{p}^{\alpha }\right)$ ，即${\left(g^i\right)}^{\frac{\phi \left(m\right)}{4}}\equiv 1\left(\mathrm{mod}{p}^{\alpha }\right)$ ，则${\left(g^i\right)}^{\frac{\phi \left(m\right)}{4}}\bcancel{\equiv }-1\left(\mathrm{mod}m\right)$ 。

同理若$g$ 是$q^{\beta }$ 的半原根，也有${\left(g^i\right)}^{\frac{\phi \left(m\right)}{4}}\bcancel{\equiv }-1\left(\mathrm{mod}m\right)$ ，也就是说$g^i$ 为$m$ 的半原根，且在$g$ ，$g^2$ ，$\cdots$ ，$g^{\frac{\phi \left(m\right)}{2}}$ 中有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个$m$ 的半原根。

显然，${\left(-g^i\right)}^{\frac{\phi \left(m\right)}{2}}\equiv 1\left(\mathrm{mod}m\right)$ ，若存在$n<\frac{\phi \left(m\right)}{2}$ ，使得${\left(-g^i\right)}^n\equiv \pm 1\left(\mathrm{mod}m\right)$ ，当$n$ 为偶数时有${\left(g^i\right)}^n\equiv \pm 1\left(\mathrm{mod}m\right)$ ；当为奇数时有${\left(g^i\right)}^n\equiv \mp 1\left(\mathrm{mod}m\right)$ ，均不可，即在$-g$ ，$-g^2$ ，$\cdots$ ，$-g^{\frac{\phi \left(m\right)}{2}}$ 中也有$\phi \left(\frac{\phi \left(m\right)}{2}\right)$ 个$m$ 的半原根。又因$\phi \left(\phi \left(p^{\alpha }{q}^{\beta }\right)\right)=2\phi \left(\frac{\phi \left(p^{\alpha }{q}^{\beta }\right)}{2}\right)$ ，故在$\pm g$ ，$\pm g^2$ ，$\cdots$ ，$g^{\frac{\phi \left(m\right)}{2}}$ 中有$\phi \left(\phi \left(m\right)\right)$ 个半原根。

⑤ 设$m=2p^{\alpha }{q}^{\beta }$ ，仿④可证：$m$ 的半原根有$\phi \left(\phi \left(m\right)\right)$ 个。

7. 半原根指数的性质

半原根指数和原根一样，也有类似对数的性质[2]，即下面的定理：

设$g$ 是$m$ 的半原根，如果$\left(a,m\right)=\left(b,m\right)=1$ ，我们有

① $in{d}_g\left(ab\right)\equiv in{d}_{g}a+in{d}_{g}b\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ ；

② $in{d}_g{a}^n\equiv nin{d}_{g}a\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right),n\ge 1$ ；

③ $in{d}_{g}1=0,in{d}_{g}g=1$ ；

④ 若$n\equiv 0\left(\mathrm{mod}2\right),nin{d}_g\left(-1\right)=0$ ；

若$n\equiv 1\left(\mathrm{mod}2\right),nin{d}_g\left(-1\right)=in{d}_g\left(-1\right)$ ；

⑤ 设$g_1$ 也是$m$ 的一个半原根，则

$in{d}_{g}a\equiv \left(in{d}_{g_1}a\right)\left(in{d}_g{g}_1\right)\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ 。

证① 设$ab\equiv g^{in{d}_g\left(ab\right)}\left(\mathrm{mod}m\right)$ ，$a\equiv g^{in{d}_{g}a}\left(\mathrm{mod}m\right),b\equiv g^{in{d}_{g}b}\left(\mathrm{mod}m\right)$ 。则有

$g^{in{d}_g\left(ab\right)}\equiv g^{in{d}_{g}a+in{d}_{g}b}\left(\mathrm{mod}m\right)$ ，故$in{d}_g\left(ab\right)\equiv in{d}_{g}a+in{d}_{g}b\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ 。

② 设$a^n\equiv g^{in{d}_g{a}^n}\left(\mathrm{mod}m\right),a\equiv g^{in{d}_{g}a}\left(\mathrm{mod}m\right)$ ，则有

$g^{in{d}_g{a}^n}\equiv a^n\equiv {\left(g^{in{d}_{g}a}\right)}^n=g^{nin{d}_{g}a}\left(\mathrm{mod}m\right)$ ，故$in{d}_g{a}^n\equiv nin{d}_{g}a\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ 。

③、④显然。

⑤ 由于$g_1\equiv g^k\left(\mathrm{mod}m\right),1\le k\le \frac{\phi \left(m\right)}{2},\left(k,\frac{\phi \left(m\right)}{2}\right)=1$ ，则

$g^{in{d}_{g}a}\equiv a\equiv g_1^{in{d}_{g_1}a}\equiv g^{kin{d}_{g_1}a}\left(\mathrm{mod}m\right)$

故有

$in{d}_{g}a\equiv kin{d}_{g_1}a=\left(in{d}_g{g}_1\right)\left(in{d}_{g_1}a\right)\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ 。

8. 半原根的应用

应用一：解同余方程

根据定理1知$m$ 的简化剩余系可由$m$ 的半原根的幂表出，那么，同原根一样，可以建立半原

根$g$ 为底的指数组来解模$m$ 的同余方程，在全体正整数中，存在半原根的数的数量要比存在原根的数多，所以利用半原根的指数组来解同余方程或利用半原根和原根的指数结合起来解同余方程(在100以内有85个数存在半原根或存在原根)，其范围比单纯用原根要宽泛得多。

例：解同余方程

$33x^3\equiv 19\left(\mathrm{mod}35\right)$ (1)

这个同余式是不能直接用原根指数组的方式来求解的，因为35不存在原根，而只能将其化成同余方程组来解。而$35=5\times 7,\left(\phi \left(5\right),\phi \left(7\right)\right)=2$ ，故35存在半原根，$\frac{\phi \left(35\right)}{2}=12$ ，计算可知2是35的半原根，并且有

$2^1\equiv 2,2^2\equiv 4,2^3\equiv 8,2^4\equiv 16,2^5\equiv 32,2^6\equiv 29,2^7\equiv 23,2^8\equiv 11,2^9\equiv 22,2^{10}\equiv 9,2^{11}\equiv 18,2^{12}\equiv 1\left(\mathrm{mod}35\right)$

$-2^1\equiv 33,-2^2\equiv 31,-2^3\equiv 27,-2^4\equiv 19,-2^5\equiv 3,-2^6\equiv 6,-2^7\equiv 12,-2^8\equiv 24,-2^9\equiv 13,$

$-2^{10}\equiv 26,-2^{11}\equiv 17,-2^{12}\equiv 34\left(\mathrm{mod}35\right)$

$in{d}_{2}n$ 表

个 十	0	1	2	3	4	5	6	7	8	9
0		12	1	I + 5	2		I + 6		3	10
1		8	I + 7	I + 9			4	I + 11	11	I + 4
2			9	7	I + 8		I + 10	I + 3		6
3		I + 2	5	I + 1	I + 12

注：表中第一纵行是$n$ 的十位数字，第一横行是$n$ 的个位数字，$I=in{d}_2\left(-1\right)$ 。

由(1)可得：$in{d}_{2}33+3in{d}_{2}x\equiv in{d}_{2}19\left(\mathrm{mod}\frac{\phi \left(35\right)}{2}\right)$

或为$3in{d}_{2}x\equiv in{d}_{2}19-in{d}_{2}33\left(\mathrm{mod}12\right)$ ，查$in{d}_{2}n$ 表可得：

$in{d}_{2}33=in{d}_2\left(-1\right)+1,in{d}_{2}19=in{d}_2\left(-1\right)+4$ ，则有

$3in{d}_{2}x\equiv in{d}_2\left(-1\right)+4-\left(in{d}_2\left(-1\right)+1\right)\left(\mathrm{mod}12\right)$

或$3in{d}_{2}x\equiv 3\left(\mathrm{mod}12\right),in{d}_{2}x\equiv 1\left(\mathrm{mod}4\right)$

$in{d}_{2}x\equiv 1,5,9\left(\mathrm{mod}12\right).$

再反查表得：$x\equiv 2,22,32\left(\mathrm{mod}35\right)$ 即为同余方程(1)的解。

应用二：证明相关不定方程的命题

1842年卡塔兰(Catalan, 1814~1894)提出了一个著名的猜想：$x^m-y^n=1,m>1,n>1$ 的整数解只有$x=3,m=2,y=2,n=3$ 。

1962年，我国著名数学家柯召首先在卡塔兰猜想方面取得了突破，他证明了下述不定方程：$x^2-y^n=1$ 只有一组解：$x=3,y=2,n=3$ 。而方程$x^m-y^2=1,m>1$ 没有正整数解。

2002年4月，米哈伊列斯库大幅使用分园域和伽罗华模证明了此猜想。

下面用半原根及其指数理论来证明：

不定方程

$n^x-2^y=1$ (2)

$x>1,y>1$ 的整数解只有$x=2,n=3,y=3$ 。

证：当$y\le 3$ 时，可以验证：$x=2,n=3,y=3$ 是(2)的整数解。

当$y>3$ 时，根据(2)有：

$n^x\equiv 1\left(\mathrm{mod}{2}^y\right)$ (3)

设$n=8m+3$ 和$n=8m+5$ 。根据定理3知，$n$ 为$2^y$ 的半原根。

对(3)两边取以$n$ 为底的指数得：

$in{d}_{n}1+xin{d}_{n}n\equiv in{d}_{n}1\left(\mathrm{mod}{2}^{y-2}\right)$ ，又根据定理4知(3)有唯一解，

$x\equiv 0\left(\mathrm{mod}{2}^{y-2}\right)$ 。

得到$x=2^{y-2}t$ ，$t$ 为整数。也就有：

$n^{2^{y-2}t}={\left(8m+3\right)}^{2^{y-2}t}={\left(2^{3}m+3\right)}^{2^{y-2}t}=1+2^{y}l$

$n^{2^{y-2}t}={\left(8m+5\right)}^{2^{y-2}t}={\left(2^{3}m+5\right)}^{2^{y-2}t}=1+2^{y}h$

$l,h$ 均为正整数。

但$3^{\frac{\phi \left(2^y\right)}{2}}={\left(3^2\right)}^{2^{y-3}}={\left(2^3+1\right)}^{2^{y-3}}>2^y+1$ 和$5^{\frac{\phi \left(2^y\right)}{2}}={\left(5^2\right)}^{2^{y-3}}={\left(2^3\times 3+1\right)}^{2^{y-3}}>2^y+1$ ，

所以当$y>3$ 时，${\left(8m+3\right)}^x-2^y=1$ 和${\left(8m+5\right)}^x-2^y=1$ 不存在整数解。

又因：$\left(8n\pm 1,2^y\right)=1$ ，有${\left(8n\pm 1\right)}^{\phi \left(2^y\right)}\equiv 1\left(\mathrm{mod}{2}^y\right)$ ，如果还有：

${\left(8m\pm 1\right)}^k\equiv 1\left(\mathrm{mod}{2}^y\right),k<\phi \left(2^y\right)$ ，则必有$k|\phi \left(2^y\right)=2^{y-1}$ 。如果$k\ge 2^{y-3}$ ，则$m\ge 1$ 时${\left(8m\pm 1\right)}^k>2^y+1$ 方程(2)无正整数解。那么$k$ 只能是$2^r$ ，$0<r<y-3$ 。而当$m\ge 1$ 时，设$m=2^{j}q$ ，$r\ge 0,q$ 为奇数，则

${\left(8m\pm 1\right)}^{2^r}={\left(2^{j+3}q\pm 1\right)}^{2^r}$ (4)

由(4)可知：

当$r\ge y-j-3$ 时，${\left(8m\pm 1\right)}^{2^r}>2^y+1$ ；

当$r<y-j-3$ 时，${\left(8m\pm 1\right)}^{2^r}\bcancel{\equiv }1\left(\mathrm{mod}{2}^y\right)$

则${\left(8m\pm 1\right)}^{2^r}\bcancel{\equiv }1\left(\mathrm{mod}{2}^y\right)$ 。所以${\left(8m\pm 1\right)}^x-2^y=1$ 无整数解。

再因${\left(8n+2l\right)}^x-2^y\ne 1$ ，$l$ 为整数。得证。

应用三：半原根所形成的离散对数公钥方案及数字签名

1) 加密和解密

用户A选取$m=p\times q$ ，$p$ 和$q$ 均为大素数，并$\left(p-1,q-1\right)=2$ ，此时$m$ 存在半原根，并选取$m$ 的一个半根$g$ ，用户A再选取一个整数$i,0\le i\le \frac{\phi \left(m\right)}{2}-1$ ，计算$b\equiv \pm g^i\left(\mathrm{mod}m\right)$ ，把$m,g,b$ 均公开，而i作为用户A的私密而保密，b为用户A的公钥。如果用户B将信息x发用户A，$\left(1\le x\le m-1\right)$ ，其加密和解密的方式为：[3]

① 加密：用户B随意选取一个整数$k,1\le k\le \frac{m}{3}<\frac{\phi \left(m\right)}{2}$ ，(当$p,q$ 均大于5时$\frac{m}{3}<\frac{\phi \left(m\right)}{2}$ )

并计算

$a\equiv \pm g^k\left(\mathrm{mod}m\right)$ 和$c\equiv b^{k}x\left(\mathrm{mod}m\right)$ 。

如果$k$ 为奇数

$a\equiv -g^k\left(\mathrm{mod}m\right)$ ，则将密文$\left(a,c,-1\right)$ 传给A；

$a\equiv g^k\left(\mathrm{mod}m\right)$ ，则将密文$\left(a,c,1\right)$ 传给A；

如果$k$ 为偶数

$a\equiv -g^k\left(\mathrm{mod}m\right)$ ，则将密文$\left(a,c,0\right)$ 传给A；

$a\equiv g^k\left(\mathrm{mod}m\right)$ ，则将密文$\left(a,c,2\right)$ 传给A。

② 解密：用户A收到密文后，根据$b\equiv \pm g^i\left(\mathrm{mod}m\right)$ 的情况(用户A自己知道)，用私钥i进

行加密：

当用户A收到$\left(a,c,-1\right)$ 后，用私钥i计算：

如果$b\equiv g^i\left(\mathrm{mod}m\right)$

$c{\left(-a\right)}^{-i}\equiv b^{k}x{\left(-\left(-g^k\right)\right)}^{-i}\equiv {\left(g^i\right)}^{k}x{\left(g^k\right)}^{-i}\equiv x\left(\mathrm{mod}m\right)$

如果$b\equiv -g^i\left(\mathrm{mod}m\right)$

${\left(-1\right)}^{1-i}c{a}^{-i}\equiv {\left(-1\right)}^{1-i}{\left(-g^i\right)}^{k}x{\left(-g^k\right)}^{-i}\equiv {\left(-1\right)}^{2\left(1-i\right)}x\equiv x\left(\mathrm{mod}m\right)$

当用户A收到$\left(a,c,1\right)$ 后，用私钥i计算：

如果$b\equiv g^i\left(\mathrm{mod}m\right)$

$c{a}^{-i}\equiv b^{k}x{\left(g^k\right)}^{-i}\equiv {\left(g^i\right)}^{k}x{\left(g^k\right)}^{-i}\equiv x\left(\mathrm{mod}m\right)$

如果$b\equiv -g^i\left(\mathrm{mod}m\right)$

$-c{a}^{-i}\equiv -b^{k}x{\left(g^k\right)}^{-i}\equiv -{\left(-g^i\right)}^{k}x{\left(g^k\right)}^{-i}\equiv x\left(\mathrm{mod}m\right)$

当用户A收到$\left(a,c,0\right)$ 后，用私钥i计算：

如果$b\equiv \pm g^i\left(\mathrm{mod}m\right)$

$c{\left(-a\right)}^{-i}\equiv b^{k}x{\left(-\left(-g^k\right)\right)}^{-i}\equiv {\left(\pm g^i\right)}^{k}x{\left(g^k\right)}^{-i}\equiv x\left(\mathrm{mod}m\right)$

当用户A收到$\left(a,c,2\right)$ 后，用私钥i计算：

如果$b\equiv \pm g^i\left(\mathrm{mod}m\right)$

$c{\left(a\right)}^{-i}\equiv b^{k}x{\left(g^k\right)}^{-i}\equiv {\left(\pm g^i\right)}^{k}x{\left(g^k\right)}^{-i}\equiv x\left(\mathrm{mod}m\right)$

以上计算可将用户B发来的密文恢复成明文x，由于用户以外的人不知道A的私钥i，而由

公钥$g,m,b$ 求i是困难的离散对数问题，所以，外人由密文很难算出明文。

2) 数字签名

用户A作数字签名和认证的过程为：

① 用户A随意取一个与$\frac{\phi \left(m\right)}{2}$ 互素的整数$r$ 并计算：

$c\equiv g^r\left(\mathrm{mod}m\right),1\le r<\frac{\phi \left(m\right)}{2}$ (5)

而由$b^c{c}^d\equiv g^x\left(\mathrm{mod}m\right)$ 得

${\left(g^r\right)}^d\equiv c^d\equiv \frac{g^x}{b^c}\equiv \frac{g^x}{{\left(g^i\right)}^c}\equiv g^{x-ic}\left(\mathrm{mod}m\right)$ (6)

对(6)两边取指数得

$rd\equiv \left(x-ic\right)\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$

或

$d\equiv \left(x-ic\right)r^{-1}\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right),0\le d<\frac{\phi \left(m\right)}{2}$

则$\left(c,d\right)$ 就是用户A在信息x上的签名，用户A将信息x和签名$\left(c,d\right)$ 同时发给用户B。

② 任何人都可认证信息x来自用户A，因为由用户A的公钥b和签名$\left(c,d\right)$ 并根据(5)和(6)可知

$b^c{c}^d\equiv g^{ic}{g}^{x-ic}\equiv g^x\left(\mathrm{mod}m\right)$

即由公开的$m,g,b$ 签名$\left(c,d\right)$ 和信息x直接验证同余式$b^c{c}^d\equiv g^x\left(\mathrm{mod}m\right)$ 成立，就可以认证信息x来自用户A。

我们知道：使用由原根所形成的离散对数同样也可用来作信息加密和数字签名，但此时用户A不能用同一个值r对两个不同的信息$x_1$ 和$x_2$ $\left(x_1\bcancel{\equiv }{x}_2\left(\mathrm{mod}\left(p-1\right)\right)\right)$ 同时做签名，否则，存在私钥被破译的风险。[4]

而使用由半原根所形成的离散对数来作加密和数字签名时，用户A则可用同一个值r对多个不同的信息$x_1,x_2,\cdots ,x_n$ 同时做签名而不致于被破译，这是由于：

$d_1\equiv \left(x_1-i{c}_1\right)r^{-1}\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ (7)

$d_2\equiv \left(x_2-i{c}_2\right)r^{-1}\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ (8)

如果$c_1\equiv g^r\equiv c_2\left(\mathrm{mod}m\right),\left(1\le c_1,c_2\le m-1\right)$

则由(7)-(8)可得

$r\left(d_1-d_2\right)\equiv x_1-x_2\left(\mathrm{mod}\frac{\phi \left(m\right)}{2}\right)$ (9)

由于$\frac{\phi \left(m\right)}{2}=\frac{\left(p-1\right)\left(q-1\right)}{2}$ ，当$p$ 和$q$ 都非常大时，分解$m=p\times q$ 是非常困难的[5]，所以求解(9)中的$r$ 也是极其困难的，因此，用同一个值$r$ 对多个不同的信息$x_1,x_2,\cdots ,x_n$ 同时做签名也是很安全的，这也是使用由半原根所形成的离散对数来做加密和数字签名最大的优势。

9. 猜想

$Q\left(m\right)$ 表示所有小于$m$ 的半原根之和，$R\left(m\right)$ 表示所有小于$m$ 的原根之和。

下面的$\mu \left(n\right)$ 表示$n$ 的麦比乌斯函数。$\phi \left(m\right)$ 为关于$m$ 的欧拉函数。

猜想：

1) 设$p>3,p\equiv -1\left(\mathrm{mod}4\right)$ 为素数，$m=p,2p$ 。则

$Q\left(m\right)\equiv \mu \left(\phi \left(m\right)\right)\times \left(p-1\right)\left(\mathrm{mod}m\right).$

2) 设$p\ge 3$ 为素数，$p\equiv -1\left(\mathrm{mod}4\right),r\ge 2,m=p^r,2p^r$ ，则

$Q\left(m\right)\equiv -\mu \left(p-1\right)\times \frac{\phi \left(m\right)}{p}\left(\mathrm{mod}m\right).$

3) a) 设$p,q$ 为奇素数，$\alpha ,\beta$ 为自然数，$\left(p-1,q-1\right)=2$ ，$k\ge 2$ 。

$m=3,6,2^k,p^{\alpha }\times q^{\beta },2p^{\alpha }\times q^{\beta }.$

b) 设$p$ 为奇素数，$\alpha$ 为自然数。

$m=4p^{\alpha },$

则

$Q\left(m\right)\equiv -\mu \left(\phi \left(m\right)\right)\left(\mathrm{mod}m\right).$

4) 任何大于1的自然数m都有下面的同余式：

$Q\left(m\right)+R\left(m\right)\equiv 0\left(\mathrm{mod}m\right).$

以上诸猜想，均已验证到$m=5000$ 。

10. 结束语

从上文中可以看出：存在半原根的数比存在原根的数范围要大，例如$p^{\alpha }{q}^{\beta },2p^{\alpha }{q}^{\beta }$ 和$2^k$ $\left(k\ge 2\right)$ 都存在半原根，而它们是不存在原根的，所以可以充分利用它们的半原根性质来解决原根不能解决的问题。作者相信，一定还能找到半原根在其他方面的应用，这将是提出半原根的最好结果。

Conflicts of Interest

The author declares no conflicts of interest.

Appendix (Abstract and Keywords in Chinese)

半原根与信息安全

摘要：文中提出了一个新的概念：半原根。建立了半原根的基本理论体系,并用半原根理论解同余方程和证明不定方程的命题；解决了离散对数加密时用同一个值对多个不同的信息进行数字签名的安全问题。

关键词：半原根，解同余方程，证明不定方程的命题，加密与数字签名，信息安全

Conflicts of Interest

The author declares no conflicts of interest.

References

[1]	Kenneth H. Rosen. 初等数论及其应用[M]. 夏鸿刚, 译. 北京: 机械工业部出版社, 2009: 255-258.
[2]	柯召, 孙琦. 数论讲义, 上册[M]. 北京: 高等教育出版社, 1986: 138-139.
[3]	游林. 初等数论及其在密码学中的应用与Maple实现[M]. 北京: 科学出版社, 2009: 189.
[4]	冯克勤. 数论与密码[M]. 北京: 科学出版社, 2007: 88-97.
[5]	纪建. 数论与应用[M]. 北京: 清华大学出版社, 2013: 217-225.