第四章 原根与指数

第 5 章 原根与指标（一） 内容● 指数 ● 原根● 有原根的整数 ● 指标（对数）（二） 重点● 原根及其意义 ● 有原根的整数的条件 ● 指标及其性质5.1 指数及其基本性质准备知识：（1） 欧拉定理：m ＞1，(a,m)＝1，则()m a ϕ≡1（mod m ）（2） 问题：①()m ϕ是否是使得上式成立的最小正整数？ ②该最小正整数有何性质？ (一) 指数和原根概念【定义5.1.1】（定义1）设m ＞1，(a,m)＝1，则使得e a ≡1（mod m ）成立的最小正整数e 叫做a 对模m 的指数（或阶），记作m ord (a)。

若a 的指数e ＝()m ϕ，则a 叫做模m 的原根。

(二) Diffie —Hellman 密钥交换算法全局公开量q 素数α q 的原根（α<q ）交换公开密钥 A →B ： A Y B →A ： B Y例如：● 素数q ＝353，原根α＝3● A 选 A X ＝97， 计算A Y ≡973≡40 mod 353 ● B 选 B X ＝233， 计算B Y ≡2333≡248 mod 353 ● A 与B 交换● A 计算密钥 K ≡97248≡160 mod 353 ● B 计算密钥 K ≡23340≡160 mod 353(三) 用定义求指数和原根【例1】（按定义求指数和原根）（例1）m ＝7，则ϕ(7)＝6。

且11≡1，32≡1，63≡1，34≡1，65≡1，26≡1（mod 7）故对模数7而言，1，2，3，4，5，6的指数分别为1，3，6，3，6，2。

列表表示为因此，3，【例2】（快速求指数）（例2）m ＝14＝2·7， ϕ(14)＝6，则11≡1，33≡－1，35≡－1，39≡1，311≡1，213≡1（mod7）列表故3，5【例3】（无原根的整数）（例3）m ＝15＝3·5， ϕ(15)＝8，则同理，可知模数m ＝9时，其原根为2，5；而整数8则没有原根。

信息安全数学基础习题答案[1]信息安全数学基础习题答案第一章整数的可除性1．证明：因为2|n 所以n=2k , k∈Z5|n 所以5|2k ，又（5，2）=1，所以5|k 即k=5 k1，k1∈Z7|n 所以7|2*5 k1 ,又（7，10）=1，所以7| k1即k1=7 k2，k2∈Z 所以n=2*5*7 k2即n=70 k2, k2∈Z因此70|n2．证明：因为a3-a=(a-1)a(a+1)当a=3k，k∈Z 3|a 则3|a3-a当a=3k-1，k∈Z 3|a+1 则3|a3-a当a=3k+1，k∈Z 3|a-1 则3|a3-a所以a3-a能被3整除。

3．证明：任意奇整数可表示为2 k0+1，k0∈Z（2 k0+1）2＝4 k02+4 k0+1=4 k0 (k0+1)+1由于k0与k0+1为两连续整数，必有一个为偶数，所以k0 (k0+1)=2k所以（2 k0+1）2=8k+1 得证。

4．证明：设三个连续整数为a-1,a,a+1 则(a-1)a(a+1)= a3-a由第二题结论3|（a3-a）即3|(a-1)a(a+1)又三个连续整数中必有至少一个为偶数，则2|(a-1)a(a+1)又（3，2）=1 所以6|(a-1)a(a+1) 得证。

5．证明：构造下列k个连续正整数列：(k+1)！+2, (k+1)！+3, (k+1)！+4,……, (k+1)！+(k+1), k∈Z对数列中任一数(k+1)！+i=i[(k+1)k…(i+1)(i-1)…2*1+1], i=2,3,4,…(k+1)所以i|(k+1)！+i 即(k+1)！+i为合数所以此k个连续正整数都是合数。

6．证明：因为1911/2＜14 ,小于14的素数有2，3，5，7，11，13经验算都不能整除191 所以191为素数。

因为5471/2＜24 ,小于24的素数有2，3，5，7，11，13，17，19，23经验算都不能整除547 所以547为素数。

主要利用的是欧拉定理 a (m) 1 (mod m)
5.1 阶与原根
对xk 1 (mod m) ，(a,m)=1,肯定有解，但最小解？
定义5.1.1
设 a, m Z,m > 1,(a, m) = 1，则使
a r 1 (mod m)
(1)
成 立 的 最 小 的 正 整 数 r， 称 为 a 对 模 m 的 阶 ， 记 为 ordm(a) ，在不致误会的情况下，简记为ord(a)。 例如：ordm(1)=1, ord2(-1)=1, ordm(-1)=1(m>2), ord17(3)=16 注意！！
则由(a, m) = 1得到 a j i 1 (mod m)，
这与j-i<n = ordm(a) ,与阶的定义矛盾，所以定理成立
╬ 特别的：g是原根<=>g0, g1, , g m 1是模m的缩系
思路：g1, g2,
一方面，
,
g1,
gg2(,m) 这, g（(mm)是）缩个系数，两所两以不当同1余≤，l≤所(m以)一时定，组成g缩l ≡系g；(m另) ，
定理5.2.2 若p奇素，g是模p的一个原根，则 g或g+p是模p2的原根，若g是模p2的原根， 则g是模p的原根，
定理5.2.3 模m有原根的必要条件是m = 2，4， p或2p，其中p是奇素数， 1
5.3 模素数原根的计算技巧
定理5.3.1
s
设奇素数p，p-1=
p1
i 1
pi
e，i pi素，若对（a,p）=1满足
3
6
3
6
2
5.1 阶与原根
定理5.1.1 阶的基本性质
① a n 1 (mod m)的充要条件是ordm(a)|n

数论算法讲义5章原根与指标在数论中，原根和指标是两个重要的概念。

原根是指与一个模n互素的整数a，使得对于任意正整数k，a^k(mod n)都不会等于1、指标是一种特殊的数论函数，可以用来判断一个数与模n是否互素。

5.1原根首先，我们需要了解模运算的概念。

在数学中，当我们求一个整数除以另一个整数的余数时，称为模运算。

例如，5 mod 3 = 2，表示5除以3的余数是2定义：设n>1为正整数，a是n的一个原根，是指a与n互素，并且对于任意正整数k，有a^k(mod n)≠1原根的存在性定理：对于每一个正整数n>1，都存在一个原根。

即对于任意正整数n>1，存在一个与n互素的正整数a，使得a是n的原根。

原根的性质：若a是n的原根，则a+kn也是n的原根，其中k为任意整数。

5.2指标指标是一种特殊的数论函数，用来判断一个数与模n是否互素。

指标的值只有0、1或-1三种可能。

定义：设a为整数，n为正整数。

a关于n的指标（或称勒让德符号）定义为1a与n互素0a能被n整除-1a不能被n整除，且与n互素指标的性质：（1）对于互素的整数a、b和正整数n，有以下三个基本性质：a) (ab/n) = (a/n)(b/n)b)(a^k/n)=(a/n)^kc)(1/n)=1（2）若a≡b(mod n)，则(a/n) = (b/n)（3）若a与n互素，则(a/n) ≡ a^(φ(n)/2) (mod n)，其中φ(n)为欧拉函数。

5.3应用原根和指标在密码学和计算机科学中有广泛的应用。

在密码学中，原根和指标被用于构造公钥密码系统，如Diffie-Hellman密钥交换协议和RSA加密算法。

原根可以用来生成随机数，从而提高密码的安全性。

指标则可以用来判断一个数是否为素数，从而加密和解密数据。

在计算机科学中，原根和指标被用于构造伪随机数生成器。

伪随机数生成器是根据确定性算法生成的一系列数字，看起来是随机的。

原根和指标可以用于生成伪随机数序列，从而模拟真正的随机数据。