信息安全数学基础5

引入概念：

设m是大于1的整数，a是与m互素的整数，则使得$$a^e \equiv 1 \pmod{m}$$

成立的最小正整数e交a模m的阶（order）,记作$ord_m(a)$

我们由欧拉定理知道，$ord_m(a) \le \varphi(m) $

eg:

设整数$m=7$,计算$a=1,2,3,4,5,6$的阶

解：

$$1^1 \equiv 1 \pmod{7},2^3 \equiv 1 \pmod{7},3^6 \equiv 1 \pmod{7}$$

$$4^3 \equiv 1 \pmod{7},5^6 \equiv 1 \pmod{7},6^2 \equiv 1 \pmod{7}$$

$ord_7(1)=1, \\ ord_7(2)=3,\\ ord_7(3)=6,\\ ord_7(4)=3,\\ ord_7(5)=6,\\ ord_7(6)=2$

这里，我们引出。

如果$ord_m(a)= \varphi(m)$,则a叫做模m的原根。在上面的例子中$ord_7(3)=6，ord_7(5)=6$,

所以，3，5是模m的原根。

不是每一个数都有原根。

阶的性质：

设m是大于1的整数，a是与m互素的整数，则整数d使得$$a^d \equiv 1 \pmod{m}$$

成立的充要条件是$$ord_m(a)|d$$

有个推论：$(a,m)=1，则ord_m(a) ; | ; \varphi(m)$,a模m的阶一定是$\varphi(m)的因子$

问题eg:

求整数5模17的阶$ord_{17}(5)$

解：

因为$\varphi(17)=16,16的因子有1,2,4,8,16$

$5^1 \equiv 5,5^2 =25 \equiv 8,5^4 \equiv64 \equiv -4,5^8 \equiv (-4)^2 \equiv 16 \equiv -1,5^{16} \equiv(-1)^2 \equiv 1 \pmod{7}$

所以整数5模17的阶$ord_{17}(5)=16$

设g是模m的一个原根，若$(a,m)=1$,则称同余式，$$g^x \equiv a \pmod{m},1 \le x \le \varphi(m)$$

的唯一解整数x为a模m以g为底的指数

即$ind_ga.或者ind_{g,m}(a)$

神TM知道为什么这么绕

问题eg：

设$m=7,$g=3为原根，计算指数表

解：

$$3^1 \equiv 3 \pmod{7},3^2 \equiv 2 \pmod{7},3^3 \equiv 6 \pmod{7}$$

$$3^4 \equiv 4 \pmod{7},3^5 \equiv 5 \pmod{7},3^6 \equiv 1 \pmod{7}$$

a	1	2	3	4	5	6
$ind_3a$	6	2	1	4	5	3

指数性质：

若g是模m的原根，$g^x \equiv g^y \pmod{m}$,当且仅当$x \equiv y \pmod{\varphi(m)}$

群环域，一张图就ok

Page View

Prev Home Next