密码学数学基础第二讲 同余式(1)
- 格式：pdf
- 大小：1.31 MB
- 文档页数：21
下载文档原格式
合集下载
第二章II 同余方程
根据定理2.1.8，有 26－1≡ 0 (mod 7) 故 26≡1 (mod 7)，即2 (7) ≡1 (mod 7) 。
例2 设 m＝30, a＝7, 有 (a, m)＝(7, 30)＝1, (30)＝8。
模 30 的最小非负简化剩余系
1 , 7 , 11 , 13 , 17 , 19 , 23 , 29 有
两端作 k( (n) / (p)) 次幂得， ak (n)≡1 (mod p)
两端乘以 a 得到 a1＋k (n)≡a (mod p)
即
a ed≡a (mod p)
即
a ed≡a (mod p)
同理，
aed≡a (mod q)
因为 p 和 q 是不同的素数，根据例2.1.16，
由 因此，
a (m)－1≡0(mod m)
即
a (m)≡1 (mod m)
例2.4.3 设 m＝11, a＝2, 有 (2, 11)＝1, (11)＝10,
故 210≡1 (mod 11)
例2.4.4 设 m＝23, (a, 23)＝1, (23)＝22,
a22≡1 (mod 23)
定理 2.3.5 设 m 是一个正整数，a 是满足(a，m)＝1 的整数，则存在整数a, 1≤a＜m 使得 aa≡1 (mod m) 称 a 是 (mod m)下a 的逆元。(记a 为a－1读作a逆)
≡ 7×19×17×1×29×13×11×23 (mod 30) 有 78×1×7×11×13×17×19×23×29
≡1×7×11×13×17×19×23×29 (mod 30) 即 1×7×11×13×17×19×23×29 ×(78－1)≡0 (mod 30) 又，(1×7×11×13×17×19×23×29, 30)＝1， 有 78－1≡ 0 (mod 30)。故 78≡1 (mod 30) ， 即7 (30) ≡1 (mod 30) 。
例2 设 m＝30, a＝7, 有 (a, m)＝(7, 30)＝1, (30)＝8。
模 30 的最小非负简化剩余系
1 , 7 , 11 , 13 , 17 , 19 , 23 , 29 有
两端作 k( (n) / (p)) 次幂得， ak (n)≡1 (mod p)
两端乘以 a 得到 a1＋k (n)≡a (mod p)
即
a ed≡a (mod p)
即
a ed≡a (mod p)
同理，
aed≡a (mod q)
因为 p 和 q 是不同的素数，根据例2.1.16，
由 因此，
a (m)－1≡0(mod m)
即
a (m)≡1 (mod m)
例2.4.3 设 m＝11, a＝2, 有 (2, 11)＝1, (11)＝10,
故 210≡1 (mod 11)
例2.4.4 设 m＝23, (a, 23)＝1, (23)＝22,
a22≡1 (mod 23)
定理 2.3.5 设 m 是一个正整数，a 是满足(a，m)＝1 的整数，则存在整数a, 1≤a＜m 使得 aa≡1 (mod m) 称 a 是 (mod m)下a 的逆元。(记a 为a－1读作a逆)
≡ 7×19×17×1×29×13×11×23 (mod 30) 有 78×1×7×11×13×17×19×23×29
≡1×7×11×13×17×19×23×29 (mod 30) 即 1×7×11×13×17×19×23×29 ×(78－1)≡0 (mod 30) 又，(1×7×11×13×17×19×23×29, 30)＝1， 有 78－1≡ 0 (mod 30)。故 78≡1 (mod 30) ， 即7 (30) ≡1 (mod 30) 。
第2讲 同余RSA
⎛ ABCDEFGHIJKLMNOPQRSTUVWXYZ ⎞ f −1 = ⎜ ⎟ ⎝ HIJGBKLMNOAPQRESTFUVWXDYCZ ⎠
明文： m=“monoalphabeticsubstitutioncipher” 密文： c=“HJIJKGLAKEOQBYPSEPQBQSQBJIYBLAON”
东北大学数学系
朱和贵
设数n有1000进制表示
n=ak1000k+……+a11000+a0,，则7，11，13|n的 充要条件是它们能整除（a0+a2+…）- （a1+a3+…）
证明：因为， 1000=7*11*13-1≡-1(mod 7),因此，有
1000≡10003 ≡… ≡ -1(mod 7), 10002≡10004 ≡… ≡ 1(mod 7), 因此，ak1000k+……+a11000+a0 ≡ ak(-1)k+……+a1(-1)+a0 ≡(a0+a2+…)- (a1+a3+…) (mod 7),
东北大学数学系
朱和贵
单套字母替代法频率分析
字母 a b c d e f g h i j k l m 百分比 8.2 1.5 2.8 4.2 12.7 2.2 2.0 6.1 7.0 0.1 0.8 4.0 2.4 字母 n o p q r s t u v w x y z 百分比 6.8 7.5 1.9 0.1 6.0 6.3 9.0 2.8 1.0 2.4 2.0 0.1 0.1 另外最常出现的双字母组合为： th(3.15%)，he(2.51%)， an(1.72)，in(1.69%)，er(1.54%)， re(1.48%)，es(1.45%)， on(1.45%)，ea(1.31%)，ti(1.28)， at(1.24%)，st(a.21%)，en(1.20%)， nd(1.18%)等。 最常出现的三字母组合 （Trigram）为： the，ing，and，her，ere ，ent， tha，…。
明文： m=“monoalphabeticsubstitutioncipher” 密文： c=“HJIJKGLAKEOQBYPSEPQBQSQBJIYBLAON”
东北大学数学系
朱和贵
设数n有1000进制表示
n=ak1000k+……+a11000+a0,，则7，11，13|n的 充要条件是它们能整除（a0+a2+…）- （a1+a3+…）
证明：因为， 1000=7*11*13-1≡-1(mod 7),因此，有
1000≡10003 ≡… ≡ -1(mod 7), 10002≡10004 ≡… ≡ 1(mod 7), 因此，ak1000k+……+a11000+a0 ≡ ak(-1)k+……+a1(-1)+a0 ≡(a0+a2+…)- (a1+a3+…) (mod 7),
东北大学数学系
朱和贵
单套字母替代法频率分析
字母 a b c d e f g h i j k l m 百分比 8.2 1.5 2.8 4.2 12.7 2.2 2.0 6.1 7.0 0.1 0.8 4.0 2.4 字母 n o p q r s t u v w x y z 百分比 6.8 7.5 1.9 0.1 6.0 6.3 9.0 2.8 1.0 2.4 2.0 0.1 0.1 另外最常出现的双字母组合为： th(3.15%)，he(2.51%)， an(1.72)，in(1.69%)，er(1.54%)， re(1.48%)，es(1.45%)， on(1.45%)，ea(1.31%)，ti(1.28)， at(1.24%)，st(a.21%)，en(1.20%)， nd(1.18%)等。 最常出现的三字母组合 （Trigram）为： the，ing，and，her，ere ，ent， tha，…。
第2章 同余一
下面我们定义同余类的加法以及乘法，并揭示出其可能
的带式结构。
定义2.1.4 设a，b为模m的同余类，定义加法（“⊕”）为
a b a1 b1，其中 a1 a, b1 b ；
定义乘法（“”）为
d 1 2 4 5 10 20
a : ( a ,20)=d 1 ，3 ，7 ，9 ，11 ，13，17，19 2 ，6 ，14，18 4 ，8 ，12，16 5 ，15 10 20
定义2.1.3 n个整数 a1 , a2 , , an 叫作模n 的完全剩余系（简称 完系），是指 a1 , a2 , , an 彼此模 n 不同余。
1 1 10 10 1(mod11) × ≡×≡ ，
这意味着 1, 1 0 模11 的逆元均为本身；而 26× ≡ 34× ≡ 59× ≡ 78 1 × ≡ (mod11) ， 即 2, 3, 4, 5, 6, 7,8, 9 分成 11 3 4 2
−
= 对：2 和6 ，3 和4 ，5 和9 ，7 和8 ，
我们把形如ax =xa ≡ 1(mod m)的整数称为a模m的逆元 （简称a的逆）。
推广的Euclid算法
定理2.1.4` 设 m N ，若(a, m)=1，则a在模m的意义下 存在唯一的逆元； 若(a, m) ≠ 1，则a没有模m的逆元。
前述的性质并不十分困难，但却是重要的。我们可以 举出如下的例证： 整系数多项式同余方程 an xn a1x a0 0 mod m 是 同余理论中的一个核心课题，从前述的基本性质中，我们 至少可以推知以下的认识： (1)若 x0 为 f x 0 mod m 的解，则 y x0 mod m ，都 有 f y 0 mod m ，也就是整系数多项式同余方程的解数 是模的意义下的； (2) 一 次 同 余 方 程 ax ≡ b(mod m) ， 在 (a, m)=1 时 的 解 1 a 为 b mod m ，此时解数在模m的意义下为1； n (3)若 m, an 1，则an x a1x a0 0 mod m xn an1an1xn1 an1a1x an1a0 0 mod m 与 是同解方程； f x 0 mod ml 的解必为 f x 0 mod m 的解， (4)若 l N ， 这就为探讨解的结构提供了一种可能性。
密码学数学基础第二讲 同余式(1)
解同余式组???????????11mod67mod55mod43mod2xxxx117534321????mmmm7531153117311754321????????????mmmm13mod2123mod1111????????mm15mod1?235mod1122???????mm27mod47mod4537mod11133??????????mm211mod611mod75311mod11144??????????mm1155mod62753521153411173211175????????????????????x1155mod113912601650924770?????x定义1每一个这样的集合中的任意一个元素叫做该类中的代表元或剩余
定义3 模m的最小非负完全剩余系中所有与m互素的数组 成的集合叫做模m的最小非负简化剩余系。这个集合中元素的 个数为欧拉函数，记作 ( m) 。 例 模9的最小非负简化剩余系为 {1, 2, 4, 5, 7, 8}
( m) 的计算： ( p ) p 1, p为素数
1、若正整数m，n满足(m，n)=1，则有 ( mn) ( m) ( n) 2、设p为素数，a为正整数，则有 ( p ) p p
a b m (mod )； (3) 若 a b(mod m)，d|(a,b) ，则 d d d
a b(mod m) ， d |m ， (4) 若 d 0 ，则 a b(mod d ) ；
m (5) 若ac bc(modm) ，d=(c,m)，则 a b(mod )，进一步， d 若d (c, m) 1，则有 a b(mod m) ；
二、中国剩余定理
一次同余方程 ax b(mod n) a=1的情况
x b(mod n) 的所有解可以表示为其本身或 x b kn
定义3 模m的最小非负完全剩余系中所有与m互素的数组 成的集合叫做模m的最小非负简化剩余系。这个集合中元素的 个数为欧拉函数，记作 ( m) 。 例 模9的最小非负简化剩余系为 {1, 2, 4, 5, 7, 8}
( m) 的计算： ( p ) p 1, p为素数
1、若正整数m，n满足(m，n)=1，则有 ( mn) ( m) ( n) 2、设p为素数，a为正整数，则有 ( p ) p p
a b m (mod )； (3) 若 a b(mod m)，d|(a,b) ，则 d d d
a b(mod m) ， d |m ， (4) 若 d 0 ，则 a b(mod d ) ；
m (5) 若ac bc(modm) ，d=(c,m)，则 a b(mod )，进一步， d 若d (c, m) 1，则有 a b(mod m) ；
二、中国剩余定理
一次同余方程 ax b(mod n) a=1的情况
x b(mod n) 的所有解可以表示为其本身或 x b kn
同余定理知识点总结
同余定理知识点总结同余定理通常被描述为以下形式：如果整数a和b对于模m同余，即a ≡ b (mod m)，那么a和b除以模m的余数是相等的。
同余定理可以改写为a mod m = b mod m。
同余定理有两个基本的性质。
首先，它是一种等价关系，具有自反性、对称性和传递性。
其次，同余定理具有乘法和加法性质。
首先，我们来讨论同余定理的基本性质。
同余关系是一种等价关系，即它具有自反性、对称性和传递性。
自反性指的是对于任意的整数a，a ≡ a (mod m)。
这意味着任意整数都与自己对模m同余。
对称性指的是如果a ≡ b (mod m)，那么b ≡ a (mod m)。
传递性指的是如果a ≡ b (mod m)且b ≡ c (mod m)，那么a ≡ c (mod m)。
这三种性质构成了同余关系的一个等价关系，可以将整数划分为同余类，使得具有相同除模m余数的整数在同一个同余类中。
其次，同余定理具有乘法和加法性质。
对于任意的整数a、b、c和模m，如果a ≡ b (mod m)和c ≡ d (mod m)，那么有以下性质：a + c ≡ b + d (mod m)和a * c ≡ b * d (mod m)。
这两个性质表明了同余定理在乘法和加法下的保持性。
同余定理在数论和代数中有广泛的应用。
首先，同余定理常常被用来简化计算。
通过使用同余定理，我们可以将复杂的计算转化为求余数的简单计算，从而节省时间和精力。
其次，同余定理在代数方程的求解中有着广泛的应用。
例如，对于一个模线性方程a * x ≡ b (mod m)，我们可以通过同余定理将其转化为x的一元一次同余方程，从而求解出x的取值范围。
此外，同余定理在密码学领域也有着重要的应用。
加密算法中常常使用同余定理来进行模运算，从而实现数据的加密和解密。
在数论中，同余定理还有一些重要的推论。
首先，费马小定理和欧拉定理是同余定理的重要推论。
费马小定理描述了素数模意义下的幂运算规律，欧拉定理描述了任意模意义下的幂运算规律。
密码学数学基础exercise 1st
本讲内容
一、主要概念：Leabharlann 带余除法、同余、剩余系、剩余类环、逆元
二、重要定理：
唯一分解定理、中国剩余定理、欧拉定理、 Fermat小定理
三、基本计算：
辗转相除、模幂运算、一次同余式求解
一、主要概念：
带余除法、同余、剩余系、剩余类环、逆元 Z={x|x=0,±1,±2,…} m∈Z,且m≠0
x mq r
(mod 561) 。
三、基本计算：
模逆运算、一次同余式求解、模幂运算
| a ，模m的一次同余式 ax b(modm) 有解的 定理 设 m 充要条件是(a，m)|b。在有解时，它的解数等于(a，m)，若x0是 它的一个解，则它的(a，m)个解为
m xi x 0 i (modm), i 0,1,2,, (a, m) 1. (a, m) a 1 b m x0 ( ) ( )(mod ) mod m (a, m) ( a , m) ( a , m)
例5：Hill体制（C=MKmod26），设M的长度为2，密钥为
（1）若明文为DO[3，14]，试确定密文。 （2）若密文为CF[2，5]，试确定该加密的明文。
答案：
K
1
23 19 (mod 26) 8 19
明文：ID，即（8，3）
平方-乘 k的二进制表示为 k k0 k1 2 ①连续平方
练习
1、用辗转相除法求整数x，y，使得 387x 12y = (387, 12)。 2、 求313159被7除的余数。 3、解同余方程 87x 9 (mod 15)。
x 8(mod13) 4、解同余方程组： x 5(mod 8) x 13(mod 25) 。
一、主要概念：Leabharlann 带余除法、同余、剩余系、剩余类环、逆元
二、重要定理：
唯一分解定理、中国剩余定理、欧拉定理、 Fermat小定理
三、基本计算：
辗转相除、模幂运算、一次同余式求解
一、主要概念：
带余除法、同余、剩余系、剩余类环、逆元 Z={x|x=0,±1,±2,…} m∈Z,且m≠0
x mq r
(mod 561) 。
三、基本计算：
模逆运算、一次同余式求解、模幂运算
| a ，模m的一次同余式 ax b(modm) 有解的 定理 设 m 充要条件是(a，m)|b。在有解时，它的解数等于(a，m)，若x0是 它的一个解，则它的(a，m)个解为
m xi x 0 i (modm), i 0,1,2,, (a, m) 1. (a, m) a 1 b m x0 ( ) ( )(mod ) mod m (a, m) ( a , m) ( a , m)
例5：Hill体制（C=MKmod26），设M的长度为2，密钥为
（1）若明文为DO[3，14]，试确定密文。 （2）若密文为CF[2，5]，试确定该加密的明文。
答案：
K
1
23 19 (mod 26) 8 19
明文：ID，即（8，3）
平方-乘 k的二进制表示为 k k0 k1 2 ①连续平方
练习
1、用辗转相除法求整数x，y，使得 387x 12y = (387, 12)。 2、 求313159被7除的余数。 3、解同余方程 87x 9 (mod 15)。
x 8(mod13) 4、解同余方程组： x 5(mod 8) x 13(mod 25) 。
数论01二次同余式与平方剩余
平方非剩余
如果一个数$a$模$p$同余于$x^2$模$p$ ，则称$a$为$x^2$的平方非剩余。
判定法则
判定法则一
费马小定理，若$p$是质数，且$(a, p)=1$，则有$a^{p-1} equiv 1 pmod{p}$。
判定法则二
二次互反律，设$p, q$是两个不同的奇素数，且$(p, q)=1$，则有$(p equiv q pmod{4}) Leftrightarrow (q equiv p pmod{4})$。
03
具体的证明过程需要用到一些较为复杂的数学符号 和逻辑推导，这里不再赘述。
应用案例
01
02
03
在密码学中，二次同余 式与平方剩余的概念被 广泛应用于一些加密算 法的设计，如 RSA 算法
。
在数论研究中，这些概 念也是重要的工具，可 以帮助我们解决一些数
论中的难题。
在实际生活中，这些概 念在金融、物流等领域 也有一定的应用，例如 在电子支付和电子签名 的安全性验证等方面。
解释
这是一个关于 (x) 的二次方程，但它 的解必须满足同余条件，即解必须是 模 (m) 的同余类。
性质
性质1
如果 (a, b, c, m) 满足二次同余式的定义，那么对于任意整数 (x)，如果 (x^2 + bx + c equiv 0 (mod m)) 成立 ，那么 (ax^2 + bx + c equiv 0 (mod m)) 也一定成立。
THANKS
感谢观看
应用实例
在密码学中的应用
平方剩余在密码学中有重要的应用，例如RSA公钥密码算法中就使用了平方剩余的性质 。
在数论中的应用
平方剩余是数论中的一个重要概念，它在证明费马大定理、哥德巴赫猜想等数学问题中 发挥了重要作用。
同余问题知识点讲解
同余问题知识点讲解数论中的同余问题同余问题是数论中的一个重要知识点，也是各大数学竞赛和小升初考试必考的奥数知识点。
因此，学好同余问题对学生来说非常重要。
许多孩子都接触过同余问题，但也有不少孩子说“遇到同余问题就基本晕菜了！”。
同余问题主要包括带余除法的定义，三大余数定理（加法余数定理、乘法余数定理和同余定理），以及中国剩余定理和弃九法原理的应用。
带余除法的定义及性质一般地，如果a是整数，b是整数（b≠0），若有a÷b=q……r，也就是a＝b×q＋r，且0≤r＜b，我们称上面的除法算式为一个带余除法算式。
其中，当r=0时，我们称a可以被b整除，q称为a除以b的商或完全商；当r≠0时，我们称a不可以被b整除，q称为a除以b的商或不完全商。
一个完美的带余除法讲解模型可以将带余除法的概念用一个图形化的模型来解释。
假设有一堆书，共有a本，这个a可以理解为被除数。
现在要求按照b本一捆打包，那么b就是除数的角色。
经过打包后共打包了c捆，那么这个c就是商，最后还剩余d本，这个d就是余数。
这个图能够让学生清晰的明白带余除法算式中4个量的关系，并且可以看出余数一定要比除数小。
三大余数定理1.余数的加法定理a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。
例如：23，16除以5的余数分别是3和1，所以23+16=39除以5的余数等于4，即两个余数的和3+1.当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。
例如：23，19除以5的余数分别是3和4，故23+19=42除以5的余数等于3+4=7除以5的余数，即2.2.余数的乘法定理a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。
例如：23，16除以5的余数分别是3和1，所以23×16除以5的余数等于3×1=3.当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。
同余方程在密码学中的应用与破解
同余方程在密码学中的应用与破解密码学是一门研究如何保护信息安全的学科。
在密码学中，同余方程是一种重要的数学工具，被广泛应用于密码算法的设计和密码破解的攻击。
本文将探讨同余方程在密码学中的应用与破解，并介绍一些相关的数学概念和算法。
一、同余方程的基本概念同余方程是指形如a ≡ b (mod m)的方程，其中a、b和m都是整数。
这个方程的意思是a与b在模m下同余，即它们除以m所得的余数相等。
同余方程在密码学中的应用主要涉及到模运算和模反演。
在密码学中，模运算是一种常见的操作，它可以将一个数限制在一个固定的范围内。
例如，在RSA加密算法中，模运算被用来限制明文和密文的取值范围，从而保证计算结果不会溢出。
模反演是指找到一个整数x，使得ax ≡ 1 (mod m)。
在密码学中，模反演被广泛应用于公钥密码算法的密钥生成过程中。
例如，在RSA算法中，模反演被用来生成私钥d，从而实现公钥加密和私钥解密的功能。
二、同余方程在密码算法中的应用1. 公钥密码算法公钥密码算法是一种使用不同的密钥进行加密和解密的算法。
其中，公钥用于加密，私钥用于解密。
同余方程在公钥密码算法中的应用主要涉及到密钥生成和加密解密过程。
例如，RSA算法中的密钥生成过程就是基于同余方程的模反演。
在这个过程中，选择两个大素数p和q，计算它们的乘积n=p*q，并选择一个整数e，使得e与(p-1)*(q-1)互质。
然后，找到一个整数d，使得d*e ≡ 1 (mod (p-1)*(q-1))。
其中，e是公钥，(p,q)是私钥。
通过这个过程，可以得到一对公钥和私钥，用于加密和解密。
2. 散列函数散列函数是一种将任意长度的输入映射为固定长度输出的函数。
在密码学中，散列函数被广泛应用于消息认证码和数字签名等领域。
同余方程在散列函数中的应用主要涉及到数据压缩和冲突检测。
例如，MD5算法是一种常用的散列函数，它将任意长度的输入映射为128位的输出。
MD5算法的设计基于同余方程，利用模运算和模反演来实现数据的压缩和冲突检测。
同余方程与密码学
同余方程与密码学密码学是研究如何保护信息安全的一门学科。
在密码学中，同余方程是一种重要的数学工具，用于设计和破解密码算法。
本文将探讨同余方程在密码学中的应用及其原理。
一、同余方程的基本概念同余方程是数论中的一种基本运算，表示两个数之间在模n下的等价关系。
若两个整数a和b除以一个正整数m所得的余数相等，则称a 与b对模m同余，记作a≡b (mod m)。
其中，≡是同余符号。
二、同余方程的运算性质同余关系具有一些运算性质，方便我们在密码学中进行计算和推导。
1. 传递性：若a≡b (mod m)，b≡c (mod m)，则有a≡c (mod m)。
2. 对称性：若a≡b (mod m)，则有b≡a (mod m)。
3. 反身性：对于任意整数a，都有a≡a (mod m)。
4. 同余关系可以加减：若a≡b (mod m)，c≡d (mod m)，则有a+c≡b+d (mod m)，a-c≡b-d (mod m)。
5. 同余关系可以乘除：若a≡b (mod m)，c≡d (mod m)，则有ac≡bd (mod m)，若c和d互为模m的乘法逆元，则a/c≡b/d (mod m)。
三、同余方程在密码学中的应用同余方程在密码学中有多种应用，其中最重要的是在设计和分析密码算法时使用。
1. RSA算法RSA算法是一种常用的非对称加密算法，使用两个大质数p和q来生成公钥和私钥。
同余方程在RSA算法中起到了至关重要的作用。
在生成RSA的公钥和私钥时，需要解决求解同余方程的问题。
2. 模重构攻击模重构攻击是密码学中的一种攻击方法，即根据已知的加密文本和密钥信息，通过解同余方程来破解密码算法。
这种攻击方法主要利用了同余方程的可逆性，通过对同余方程进行逆向推导，找到加密算法的密钥信息。
3. 凯撒密码凯撒密码是一种替换密码，通过将明文的每个字母按照一定的位移规则进行替换来实现加密。
同余方程在凯撒密码中用于计算字符的移位位置，实现文本的加密和解密。
第二章同余与同余式（可编辑）
练习计算ord11 3 首先计算φ 11 10，所以指数可能为1,2,5,10 从小到大依次试算 31?3, 32?9, 35?1 mod 11 ，所以ord11 3 5 根据这个结论可以推出 ord11 14 5 ord11 4 可以推出ord11 -3 ord11 -1 * ord11 3 10 所以-3?8是原根，原根一共φ 10 4个所以8?23，83?29 ?72?6， 87?221?21?2，89?227?27?7，即2、6、7、8是原根总结寻找一个原根的技巧: ordm a |φ m m, n 1， a, mn 1，则ordmn a [ordm a ,ordn a ] ab, m 1， ordm a ,ordm b 1则ordm ab ordm a ordm b 奇素数p，p-1 练习求模41的原根情况φ 11 40,现在只要考察x8, x20 从2开始,因为 28?10, 220?1 mod 41 ; 38?1, 320?-1 mod 41 ; 48?20, 420?1 mod 41 ; 58?18, 520?1 mod 41 ; 68?10, 620?-1 mod 41 ; 所以6是模41的原根练习求模41的原根情况因为:62?36, 63?-30?11, 64?25, 65?-55?27 mod 41 ; 66?39, 67?29, 68?10, 69?19,610?32, 611?28 mod 41 ; 612?4, 613?24, 614?21, 615?3, 616?18, 617?26 mod 41 ; 618?33, 619?34, 620?40,621?35,622?5, 623?30 mod 41 ; 624?16, 625?14,626?2,627?12, 628?31, 629?22 mod 41 ; 630?9, 631?13, 632?37,633?17,634?20, 635?38 mod 41 ; 636?23, 637?15, 638?8,639?7,640?1 mod 41 ; 练习求模41的原根情况所以:指数为1的元素有φ 1 1个,是1; 指数为2的元素有φ 2 1个,是620?40 mod 41 ; 指数为4的元素有φ 4 2个,是610?32, 630?9mod 41 ; 指数为5的元素有φ 5 4个,是10，18，16，37 指数为8的元素有φ 8 4个,是27，3，14，38 指数为10的元素有φ 10 4个,是25，4，31，23 指数为20的元素有φ 20 8个,是36，39，21，33，5，2，20，8 指数为40的元素有φ 40 16个,是6，11，29，19，28，24，26，34，35，30，12，22，13，17，15，7 总结指数的价值：幂化简原根的价值生成元：生成缩系所有元素 , gd d遍历φ p 的缩系φφ p 个，gd遍历模p的原根 g是原根的时候幂与计算幂后的值形成置换 a a2 a3 a4 a5 a6 3 2 6 4 5 1 总结原根的价值之二可以推出其余所有缩系元素的指数 ordm ai ordm a / ordm a ,i 可以根据幂对缩系元素按指数分类 a7 a8 a9 a10 7 3 6 1 a a2 a3 a4 a5 a6 2 4 8 5 10 9 练习计算同余方程xk ?1 mod 11 的解的个数首先计算φ 11 10，所以指数可能为1,2,5,10 k 1时，有φ 1 1个； k 2时，有φ2 1个 k 5时，有φ 5 4个； k 10时，有φ 10 4个考虑不周，k 3,4等其他数时呢 x ? 1 mod 11 是k等于任何值的解练习计算同余方程xk ?1 mod 11 的解的个数关键在于指数可能可以化简指数可取1,2,5,10, 指数为1时，有1个解，此时k可取1的倍数，即1-10任意数指数为2时，有1个解，此时k取2的倍数，即2,4,6,8,10 指数为5时，有4个解，此时k取5的倍数，即5,10 指数为10时，有4个解，此时k取10 综合：k 1,3,7,9有1个解，k 2,4,6,8有两个解，k 5有5个解，k 10有10个解练习进一步：xk ? 1 mod 11 各有哪些解？先找出每个指数对应的解，要计算指数先找出原根原根都是试找的，先看2 22?4, 25?-1, 210?1 mod 11 ,所以2是模11的原根所以生成缩系中的其它元素 22?4, 23?8, 24?5,25?10, 26?9 mod 11 27?7, 28?3, 29?6, 210?1 mod 11 所以原根有：2、8、7、6（幂与10互质）指数为5的有：4、5、9、3（幂与10最大公约2）指数为2的有：10 指数为1的有1 练习进一步：xk ? 1 mod 11 各有哪些解？所以原根有：2、8、7、6（幂与10互质）指数为5的有：4、5、9、3（幂与10最大公约2）指数为2的有：10 指数为1的有1 所以k 1、3、7、9时有解x?1 mod 11 k2、4、6、8时有解x?1 mod 11 和x?10 mod 11 k 5时有解x?1,3,4,5,9mod 11 K 10时有解x?1,2,3,4,5,6,7,8,9,10 mod 11 2.6.6 初等数论在计算机科学技术中的几个应用费马小定理的应用费马小定理设p是素数, a与p互素, 则 ap-1≡1 mod p . 另一种形式是, 设p是素数, 则对任意的整数a, ap≡a mod p . 费马小定理提供了一种不用因子分解就能断定一个数是合数的新途径. 例如, 29?1≡4 mod 9 , 可以断定9是合数.2.6.6 初等数论在计算机科学技术中的几个应用产生均匀伪随机数的方法随机数与伪随机数线性同余法与乘同余法随机数：随机变量的观察值伪随机数：用计算机随机函数所产生的“随机数”并不随机，是伪随机数。
同余的基本概念和性质
证明 留作习题。
第一节 同余的基本性质
定理3 设a，b，c，d是整数，并且
a b (mod m)，c d (mod m)，
(1)
则
(ⅰ) a c b d (mod m)；
(ⅱ) ac bd (mod m)。
证明 (ⅰ) 由式(1)及定义1可知 ma b，mc d，
第一节 同余的基本性质
(ⅰ) 3|N
n
3 | ai;
i0
(ⅱ) 9|N
n
9| ai;
i0
(ⅲ) 11|N (ⅳ) 13|N
n
11|(1)i ai; i0
1|3 a2a1a0a5a4a3 .
第一节 同余的基本性质
证明 由 100 1，101 1，102 1， (mod 3)
及式(2)可知 N =(mod 3)，
b = q2m r，0 r < m。 证明 留作习题。
第一节 同余的基本性质
定理2 同余具有下面的性质： (ⅰ) (自反性) a a (mod m)； (ⅱ) (对称性) a b (mod m) b a (mod m);
(ⅲ) (传递性) a b，b c (mod m) a c (mod m)。
其中qZ，所以
a
2
k
1
=(1
q2k
+
2)2=1
q
2k
+
31(mod
2k
+
3)，
其中q 是某个整数。这说明式(4)当n = k 1也
成立。
由归纳法知式(4)对所有正整数n成立。
第一节 同余的基本性质
例8 设p是素数，a是整数，则由a2 1(mod p) 可以推出 a 1或a 1 (mod p)。
第一节 同余的基本性质
定理3 设a，b，c，d是整数，并且
a b (mod m)，c d (mod m)，
(1)
则
(ⅰ) a c b d (mod m)；
(ⅱ) ac bd (mod m)。
证明 (ⅰ) 由式(1)及定义1可知 ma b，mc d，
第一节 同余的基本性质
(ⅰ) 3|N
n
3 | ai;
i0
(ⅱ) 9|N
n
9| ai;
i0
(ⅲ) 11|N (ⅳ) 13|N
n
11|(1)i ai; i0
1|3 a2a1a0a5a4a3 .
第一节 同余的基本性质
证明 由 100 1，101 1，102 1， (mod 3)
及式(2)可知 N =(mod 3)，
b = q2m r，0 r < m。 证明 留作习题。
第一节 同余的基本性质
定理2 同余具有下面的性质： (ⅰ) (自反性) a a (mod m)； (ⅱ) (对称性) a b (mod m) b a (mod m);
(ⅲ) (传递性) a b，b c (mod m) a c (mod m)。
其中qZ，所以
a
2
k
1
=(1
q2k
+
2)2=1
q
2k
+
31(mod
2k
+
3)，
其中q 是某个整数。这说明式(4)当n = k 1也
成立。
由归纳法知式(4)对所有正整数n成立。
第一节 同余的基本性质
例8 设p是素数，a是整数，则由a2 1(mod p) 可以推出 a 1或a 1 (mod p)。
第2讲 同余RSA
加密： E(m) ≡ 3m + 8 (mod 26)
m = 'affine '
= (0,5,5,8,13, 4) ⎯E⎯(.)⎯→(8, 23, 23, 6, 21, 20)
= 'IXXGVU ' = c
解密： D(c) ≡ 3−1(c − 8) ≡ 9(c − 8) (mod 26)
c = 'IXXGVU' = (8, 23, 23, 6, 21, 20) ⎯D⎯(.)⎯→(0, 5, 5,8,13, 4) = 'affine ' = m
由同余得定义可知,下列两个条件都是同余的充要条件 ①若 a=b+km ②若用m去除两个整数a和b所得余数相同 由同余的定义, 可得下列简单性质:
①自反性: a≡a (mod m). ②对称性: 若a≡b(mod m), 则 b≡a(mod m). ③传递性: 若a≡b(mod m), b≡c(mod m), 则: a≡c(mod m). 可见, 同余关系是等价关系.
第二章同余
同余是数论中一个基本概念, 在密码学中有着 重要的应用.本章着重讨论同余的基本性质 和应用
东北大学数学系
朱和贵
2.1同余的概念及一次同余式
定义1 给定一正整数m, 若a-b被m整除则称a为对模m同余, 记作 a≡b(mod m); 若余数不同, 则称 a为对模m不同余, 记作 a≠b(mod m).
东北大学数学系
朱和贵
凯撒密码
例：
Alice要将明文“gaul is divided into three part”加密成密文，传给Bob。
东北大学数学系
朱和贵
恺撒挪移码加密示例
同余的运算法则
同余的运算法则全文共四篇示例，供读者参考第一篇示例：同余的概念最早出现在数论领域，是一种描述整数间的模运算关系的数学概念。
同余的运算法则涉及到模运算的一系列性质和规律，对于解决一些数论问题和密码学中的加密算法起着至关重要的作用。
本文将介绍同余的概念及其运算法则，并讨论其在数学和应用方面的重要性。
1. 同余的定义在数论中，我们通常使用符号“≡”表示同余关系。
如果两个整数a和b除以一个正整数m的余数相等，即a除以m和b除以m的余数相等，我们就说a与b关于模m同余，记为a≡b(mod m)。
简单来说，同余就是指两个数除以同一个数的余数相等。
12和22关于模5同余，因为12除以5的余数为2，22除以5的余数也为2，即12≡22(mod 5)。
2. 同余的运算法则在模运算中，同余有着一系列的运算法则。
我们可以根据这些法则来简化模运算的计算，并处理一些复杂的数论问题。
（1）同余的传递性如果a≡b(mod m)且b≡c(mod m)，那么可以推出a≡c(mod m)。
这就是同余关系的传递性，即如果两个数与同一个模同余，那么它们之间也是同余的。
举例来说，如果5≡15(mod 10)且15≡25(mod 10)，那么可以推出5≡25(mod 10)。
（2）同余的对称性和反对称性（3）同余的加法和乘法性质对于同余关系来说，加法和乘法都具有良好的性质。
（4）同余的幂运算性质如果a≡b(mod m)，那么对于任意正整数n，有a^n≡b^n(mod m)。
即同余数的幂运算后依然同余。
（5）同余的逆元如果a在模m下存在逆元，即存在整数b使得ab≡1(mod m)，那么我们称b是a的逆元。
对于素数模m来说，任意整数a在模m下都有逆元。
同余的概念在数论和密码学领域有着广泛的应用。
（1）同余在数论中的应用在数论中，同余可以用来证明一些整数性质和解决一些数论问题。
在证明费马小定理和欧拉定理等定理时就会用到同余的性质。
在密码学中，同余的概念有着重要的应用。
第二讲-同余(数论复赛辅导)
第二讲 同余一.基础知识1.定义1. 设m 是正整数，若用m 去除整数b a ,，所得的余数相同，则称a 与b 关于模m 同余，记作)(mod m b a ≡，否则称a 与b 关于模m 不同余，记作a)(mod m b .例如：)15(mod 434≡，)7(mod 11000-≡，98(mod 2) 等等。
当m b <≤0时，)(mod m b a ≡，则称b 是a 对模m 的最小非负剩余。
对于固定的模m ，通常有下面的性质：性质1. )(mod m b a ≡的充要条件是,a mt b t Z =+∈也即)(|b a m -。
性质2.同余关系满足以下规律：（1）（反身性）)(mod m a a ≡；（2）（对称性）若)(mod m b a ≡，则)(mod m a b ≡；（3）（传递性）若)(mod m b a ≡，)(mod m c b ≡，则)(mod m c a ≡；（4）（同余式相加）若)(mod m b a ≡，)(mod m d c ≡，则)(mod m d b c a ±≡±；（5）（同余式相乘）若)(mod m b a ≡，)(mod m d c ≡，则)(mod m bd ac ≡；注意：① 反复利用（4）（5），可以对多于两个的（模相同的）同余式建立加、减和乘法的运算公式 ；② 特别地，由（5）易推出：若)(mod m b a ≡，c k ,为整数且0>k ，则)(mod m c b c a kk ≡； ③ 同余式的消去律一般并不成立，即从)(mod m bc ac ≡未必能推出)(mod m b a ≡，可是我们却有以下结果：若)(mod m bc ac ≡，则⎪⎪⎭⎫ ⎝⎛≡),(mod c m m b a . 由此可以推出：（6）若,1),(=m c )(mod m bc ac ≡，则有)(mod m b a ≡，即在c 与m 互素时，可以在原同余式两边约去c 而不改变模.（7）若)(mod m b a ≡，d ｜m ，则)(mod d b a ≡；（8）若)(mod m b a ≡，0≠d ，则)(mod dm db da ≡；（9）若(mod )(1,2,,)i a b m i k ≡=L ，则12(mod [,,,])k a b m m m ≡L ，特别地，若12,,,k m m m L 两两互素时，则有12(mod )k a b m m m ≡⋅⋅⋅L ；性质3.若k i m b a i i ,,2,1),(m od Λ=≡，则)(mod 11m b a k i k i i i ∑∑==≡；11(mod )k ki i i i a b m ==≡∏∏； 性质4.设)(x f 是系数全为整数的多项式，若)(mod m b a ≡，则))(mod ()(m b f a f ≡。
同余定理的定义与应用
同余定理的定义与应用同余定理（Congruence theorem）是数论中一种重要的工具，用于描述整数之间“除以某个数的余数相同”的关系。
它在密码学、代数、组合数学等领域都有广泛的应用。
本文将从同余定理的定义和基本性质入手，介绍其在数论和应用领域的具体应用。
一、同余定理的定义在数论中，同余定理指的是：对于任意整数a、b和正整数n，如果a与b除以n的余数相同，即a ≡ b (mod n)，则称a与b在模n下是同余的。
同余关系具有以下几个性质：1. 自反性：a ≡ a (mod n)；2. 对称性：若a ≡ b (mod n)，则b ≡ a (mod n)；3. 传递性：若a ≡ b (mod n)，b ≡ c (mod n)，则a ≡ c (mod n)。
二、同余定理的基本性质1. 同余的运算性质（1）同余的和与差性质：若a ≡ b (mod n)，c ≡ d (mod n)，则a+c ≡ b+d (mod n)，a-c ≡ b-d (mod n)；（2）同余的积性质：若a ≡ b (mod n)，c ≡ d (mod n)，则a·c ≡ b·d (mod n)。
2. 模运算的唯一性对于每一个正整数n，模n同余关系分割整数集合Z成了n个完全的互不相交的子集，即[Z] ≡ [0],[1],[2],...,[n-1]。
任何整数都可以唯一地属于其所对应的整数集合。
三、同余定理在数论中的应用1. 同余方程的求解对于形如ax ≡ b (mod n)的同余方程，可以利用同余定理来求解。
设d是a与n的最大公约数，若b能被d整除，方程有解；否则方程无解。
若方程有解，则可以使用扩展欧几里得算法求出方程的一组特解，并通过枚举生成其他所有解。
2. 质数测试同余定理在质数测试中有着重要的应用。
费马小定理和欧拉定理就是同余定理在质数测试中的两个重要应用。
根据费马小定理，若p为质数且a是整数，则a^(p-1) ≡ 1 (mod p)。
数论算法讲义 3章(同余方程)
第 3 章 同余方程（一） 内容：● 同余方程概念● 解同余方程● 解同余方程组（二） 重点● 解同余方程（三） 应用● 密码学，公钥密码学3.1 基本概念及一次同余方程(一) 同余方程（1） 同余方程【定义3.1.1】（定义1）设m 是一个正整数，f(x)为n 次多项式()0111a x a x a x a x f n n n n ++++=--Λ其中i a 是正整数（n a ≠0（mod m ）），则f (x)≡0（mod m ） （1） 叫做模m 的（n 次）同余式（或模m 的（n 次）同余方程），n 叫做f(x)的次数，记为deg f 。
（2） 同余方程的解若整数a 使得 f (a)≡0（mod m ）成立，则a 叫做该同余方程的解。
（3） 同余方程的解数若a 是同余方程（1）的解，则满足x ≡a （mod m ）的所有整数都是方程（1）的解。
即剩余类a C ＝{x ｜x ∈Z ，x ≡a （mod m ）}中的每个剩余都是解。
故把这些解都看做是相同的，并说剩余类a C 是同余方程(1)的一个解，这个解通常记为x ≡a （mod m ）当21,c c 均为同余方程(1)的解，且对模m 不同余时，就称它们是同余方程(2)的不同的解，所有对模m 的两两不同余的解的个数，称为是同余方程（1）的解数，记作()m f T ;。
显然()m f T ;≤m（4） 同余方程的解法一：穷举法任意选定模m 的一组完全剩余系，并以其中的每个剩余代入方程（1），在这完全剩余系中解的个数就是解数()m f T ;。
【例1】（例1）可以验证，x ≡2，4（mod 7）是同余方程15++x x ≡0（mod 7）的不同的解，故该方程的解数为2。
50＋0＋1＝1≡3 mod 751＋1＋1＝3≡3 mod 752＋2＋1＝35≡0 mod 753＋3＋1＝247≡2 mod 754＋4＋1＝1029≡0 mod 755＋5＋1＝3131≡2 mod 756＋6＋1＝7783≡6 mod 7【例2】求同余方程122742-+x x ≡0（mod 15）的解。
精品课件-信息安全数学基础(张金全)-第2章 同余-1
完全剩余系-举例
《信息安全数学基础》 第2章
完全剩余系-举例
《信息安全数学基础》 第2章
2.3简化剩余系
《信息安全数学基础》 第2章
简化剩余类-性质
《信息安全数学基础》 第2章
简化剩余系
《信息安全数学基础》 第2章
简化剩余系-性质
《信息安全数学基础》 第2章
简化剩余系-例题 【例2.3.4】 模6的一个简化剩余系为1, 5. 模20的一个简化剩余系为1, 3, 7, 9, 11, 13, 17, 19.
每一种知识都需要努力， 都需要付出，感谢支持！
知识就是力量，感谢支持！
《信息安全数学基础》 第2章
一一一一谢谢大家！！
《信息安全数学基础》 第2章
《信息安全数学基础》 第2章
简化剩余系-例题
5×1=5
3×1=3
《信息安全数学基础》 第2章
简化剩余系-性质
《信息安全数学基础》 第2章
简化剩余系-例题
《信息安全数学基础》 第2章
简化剩余系-性质
《信息安全数学基础》 第2章
《信息安全数学基础》 第2章
简化剩余系-例题
《信息安全数学基础》 第2章
第2章 同余
2.1ቤተ መጻሕፍቲ ባይዱ余的基本性质
《信息安全数学基础》 第2章
同余
《信息安全数学基础》 第2章
同余的性质
《信息安全数学基础》 第2章
同余的性质
《信息安全数学基础》 第2章
同余的性质
《信息安全数学基础》 第2章
《信息安全数学基础》 第2章
推论
《信息安全数学基础》 第2章
同余的性质
《信息安全数学基础》 第2章
《信息安全数学基础》 第2章
数论算法讲义2章(同余运算)
第 2 章 同余运算（一） 内容●同余概念 ●性质 ●剩余类→整数分类 ●模幂运算（二） 重点● 同余及其计算（三） 应用：● 密码学● 公钥密码学【例】 RSA 公钥算法：准备：选大素数p 、q ，记n ＝pq ，φ(n)＝(p －1)(q －1)，再选正整数e ，满足（e ，φ(n)）≡1（mod n ）并求d ，满足 ed ＝1（mod φ(n)）加密：明文串P 编码为数字M ，则密文C ≡e M （mod n ） 解密： M ≡d C （mod n ），再将数字M 解码得明文串P2.1 同余的概念及基本性质(一) 同余概念【定义2.1.1】给定一个正整数m ，两个整数a 、b 叫做模m 同余，如果a －b 被m 整除，或b a m -|，记作b a ≡ ()m mod ；否则叫做模m 不同余，记作a ≠b （（mod m ））【注】由于b a m -|等价于b a m --|，所以同余式b a ≡ ()m mod等价于 b a ≡()()m -mod ，故以后总假定模1≥m 。
判断同余的方法一：利用定义【例1】 7│28＝29－1，故29≡1（mod 7）；7│21＝27－6，故27≡6（mod 7）；7│28＝23－（－5），故23≡－5（mod 7）；(二) 性质【性质1】（定理1）设m 是一个正整数，a 、b 是两个整数，则a≡b （mod m ）⇔存在整数k ，使得a ＝b ＋km 。
（证）a≡b （mod m ） ⇔ b a m -|⇔ 存在k ，使得 a －b ＝km ，即a ＝b ＋km【性质2】（定理2）同余是一种等价关系。
即（i ） 自反性：a≡a m（ii ） 对称性：a≡b （mod m ） ⇒ b≡a （mod m ） （iii ） 传递性：a≡b mod m 且b≡c （mod m ）⇒ a≡c （mod m ）（证）（i ）m │0＝a －a ⇒ a≡a m（ii ）a≡b （mod m ） ⇒ m │a －b ⇒ m │b －a ＝－(a －b) ⇒ b≡a （mod m ）（iii ）a≡b （mod m ），b≡c （mod m ） ⇒ m │a －b ，m │b －c⇒m│(a－b)＋(b－c)＝a－c ⇒a≡c （mod m）【例3】【性质3】（等价定义）（定理3）整数a、b模m同余⇔a、b被m除的余数相同。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
x b1 (mod n1 ) x b2 (mod n2 )
有解的充分必要条件是（n1,n2）|(b1-b2)，如果这个条件 成立，则方程组有且仅有一个小于n的非负整数解。
定理 (中国剩余定理) 设 m m1 m2 mk 是k个两两互素的正 整数，则对任意的整数 b1 , b2 , , bk ，同余式组
n n (6) 若 a b(mod m) ，则a b (mod m)，进一步，若
n
P ( x) c k x k是一个整系数多项式(即系数是整数 ck ，其
k 0
中 c n 0 )，则 P ( a ) P (b)(mod m) ； (7) 同余式组 a b(mod m j ), j 1,2, , k同时成立的充要条件 是 a b(mod[m1 , m2 , , mk ]) ； (8) ( a b) mod m ( a mod m b mod m) mod m
定义1 给定一个正整数 m ，如果m | (a b)，则称整数 a, b | (a b)，则称整数 对模 m 同余，记作 a b(mod m) ；如果m a, b 对模 m 不同余，记作a b(mod m)。
。
性质1 (1)自反性：a a (mod m)；
a b (mod m) b a (mod m) (2) 对称性：
d |m , d 0
(d ) m
应用：计算大整数的方幂ak(mod n)。
自然方式的算法： Input: k,a,n Set x=1 For i=1,2,,k repeat Set x=xa(mod n) Output: x 上述计算模幂方法所需的bit计算量为： kO((log2n)2)=O(2log2k(log2n)2)
根据同余的概念，可以将集合Z分成m个两两互不相交的集合，且同 一个集合中的任意两个整数对模m一定同余，而属于不同集合中的两个 整数对模m一定不同余。对任意一个整数a，令
Ca {a km : k } [a]
定义1 每一个这样的集合 Ca 称为模m的同余类或剩余类，一个剩余类 中的任意一个元素叫做该类中的代表元或剩余。一组数 a1 , a2 , , am称为 是模m的完全剩余系，记为Zm。如果对于任意的整数a有且仅有一个整数 与a在同一个剩余类中。 对于模m的一个完全剩余系 a1 , a2 , , am ，C a1 , C a2 , , C am 就是模m 的m个两两不同的剩余类，且有
C ai
i 1
m
Zm中的元素对于“+、－、×”满足结合律、交换律和分配 率，所以称Zm为整数模m的剩余类环。 定义2 剩余系； 1,2,…，m为模m的最小正完全剩余系； -(m-1),-(m-2),…-1,0为模m的最大非正完全剩余系； -m,-(m-1),…-2,-1为模m的最大负完全剩余系； 当m为奇数时 ,-(m-1)/2,…,-1,0,1… ,(m-1)/2为模m的绝对值 最小完全剩余系； 当m为偶数时 ,-m/2,…,-1,0,1… ,(m-2)/2或 ,(-m-2)/2,…,-1, 0,1… ,m/2为模的绝对值最小完全剩余系。 一般地，0,1,2,…，m-1称为模m的最小非负完全
22
Input: t,k0,k1,,kt-1,a,n Set x=1,y=a For i=0,1,,t-1 repeat If ki=1 then set x=xy(mod n) Set y=y2(mod n) Set x=xy(mod n) Output: x 上述模幂算法所需的bit计算量为： t2O((log2n)2)+ O((log2n)2 )= O((log2k)(log2n)2)
1 M2 M2 mod 5 (3 2 1) 1 mod 5 1
M 31 mod 7 (3 5 4) 1 mod 7 41 mod 7 2 M3
1 M4 M4 mod11 (3 5 7) 1 mod11 61 mod11 2
定义3 模m的最小非负完全剩余系中所有与m互素的数组 成的集合叫做模m的最小非负简化剩余系。这个集合中元素的 个数为欧拉函数，记作 ( m) 。 例 模9的最小非负简化剩余系为 {1, 2, 4, 5, 7, 8}
( m) 的计算： ( p ) p 1, p为素数
1、若正整数m，n满足(m，n)=1，则有 ( mn) ( m) ( n) 2、设p为素数，a为正整数，则有 ( p ) p p
a b m (mod )； (3) 若 a b(mod m)，d|(a,b) ，则 d d d
a b(mod m) ， d |m ， (4) 若 d 0 ，则 a b(mod d ) ；
m (5) 若ac bc(modm) ，d=(c,m)，则 a b(mod )，进一步， d 若d (c, m) 1，则有 a b(mod m) ；
；
a b(mod m), b c (mod m) a c(mod m) (3) 传递性：
性质2 c d (mod m) ，则 a c b d (mod m)， (1) 若 a b(mod m)， ac bd (mod m) ，特别地，对于任意一个整数e，都有 a e b e(mod m), ae be(mod m) ； (2) 若 a b(mod m)， k 0 ，则 ak bk (mod mk ) ；
二、中国剩余定理
一次同余方程 ax b(mod n) a=1的情况
x b(mod n) 的所有解可以表示为其本身或 x b kn
x b1 (mod n1 ) 下面考虑同余方程组的解 x b2 (mod n2 )
定理2.2 设n1,n2为正整数，n是n1，n2的最小公倍数， 则同余方程组
②连续乘
a k ti1 ti2 tis
1 s
其中 0 i1 i2 is r , (ki , , ki ) 是 ( k0 , k1 , k2 ,, kr ) 中所有等 于1的项。
多项式时间算法（设k=(1kt-1k1k0)2）——从左向右计算方法：
a k ( (( a 2 a kt 1 ) 2 a k t 2 ) 2 a k1 ) 2 a k 0
x (5 7 11) 1 2 (3 7 11) 1 4 (3 5 11) 2 5 (3 5 7 ) 2 6(mod 1155) x 770 924 1650 1260 1139(mod 1155)
三、剩余系
例 设正整数m=9 ， 0,1,2,3,4,5,6,7,8为模9的最小非负完全剩余系； 1,2,3,4,5,6,7,8,9为模9的最小正完全剩余系； -8,-7,-6,-5,-4,-3,-2,-1,0为模9的最大非正完全剩余系； -9,-8,-7,-6,-5,-4,-3,-2,-1为模9的最大负完全剩余系； -4,-3,-2,-1,0,1,2,3,4为模9的绝对值最小完全剩余系。
Input: t,k0,k1,,kt-1,a,n Set x=a For i=t-1,t-2,,1,0 repeat Set x=x2(mod n) If ki=1 then set x=xa(mod n) Output: x 上述模幂算法所需的bit计算量为： t2O((log2n)2) = O((log2k)(log费马小定理) 对任意的整数a和任意的素数p，有
a a (mod p ),
进一步，若(a，p)=1，则
p
a
几？
p 1
1(mod p).
例 2003年5月8日是星期四，问此天后第33025天是星期
定理2.6 设(m1, m2)=1，如果x遍历m1的一个完全剩余 系，y遍历m2的一个完全剩余系，则m1y+m2x遍历m1m2的一 个完全剩余系。 定理2.7 设(m1, m2)=1，如果x遍历m1的一个缩系，y遍历 m2的一个缩系，则m1y+m2x遍历m1m2的一个缩系。 由定理2.7可以得到 (mn) (m) (n) 定理 对于任意正整数m有
i 1
例：解同余式组
x 2(mod 3) x 4(mod 5) x 5(mod 7) x 6(mod11)
m1 3, m2 5, m3 7, m4 11 M 1 5 7 11, M 2 3 7 11, M 3 3 5 11, M 4 3 5 7 M 1 M 11 mod 3 (2 1 2) 1 mod 3 1
第二讲 同余式（1）
教师：李艳俊 联系方式：13810350384
本讲内容
一 同余的定义 二 中国剩余定理 三 剩余类环
一、同余的定义
“物不知其数”问题
——孙子算经
今有物，不知其数，三三数之剩二，五五数之剩三， 七七数之剩二，问物几何？ 等价于求解
x 2(mod 3) x 3(mod 5) x 2(mod 7)
平方-乘 k的二进制表示为 ①连续平方
k k0 k1 2 kr 2r
t0 a mod n t1 a 2 mod n t2 t12 a 2 mod n
2 t3 t 2 a 2 mod n
3 2
ki 0or1
tr tr21 a 2 mod n
r
例 计算3523mod59。
i 3 2 1 0
ki 0 1 1 1
所以3523≡57mod59
x 45 16 51 57
——从右向左计算方法：
a a (( a
k
2t
2 t 1 k t 1
)
(( a ) k 2 (( a 2 ) k1 (1 a k 0 ))) )