1、 返回总目录返回总目录 第 3章基础数论1.2 2006第第 3章章 基础数论基础数论教学目的了解模运算及辗转相除法了解模运算及辗转相除法了解中国余式子定律了解中国余式子定律了解了解 Lagrange定理与费马小定理定理与费马小定理了解原根、二次剩余、了解原根、二次剩余、 Galois域等概念域等概念了解质数理论和连分数了解质数理论和连分数了解密码安全伪随机数字生成器了解密码安全伪随机数字生成器 1.3 2006第第 3章章 基础数论基础数论 模运算与辗转相除法模运算与辗转相除法本章内容 中国余式子定律中国余式子定律 Lagrange定理与费马小定理定理与费马小定理 原根原根 二次剩余二次剩余
2、 Galois域域 连分数连分数 质数理论质数理论 密码安全伪随机数字生成器密码安全伪随机数字生成器 1.4 2006第第 3章章 基础数论基础数论模运算与辗转相除法3.1 模运算与辗转相除法模运算与辗转相除法假设今天是星期五，请问 10000天后是星期几？ （即 5+10000除以 7的余数）即： 10000天后是星期二 1.5 2006第第 3章章 基础数论基础数论同余定义定义 （同余，（同余， Congruence）：令）：令 。令。令 为两整数，称为两整数，称 a同余同余 b模模 n，记为，记为 ，当，当 n整整除除 b-a。而所有与。而所有与 a同余的整数所组成的集合，即同余的整数所
3、组成的集合，即称为称为 a的同余类。所有同余类所形成的集合的同余类。所有同余类所形成的集合 1.6 2006第第 3章章 基础数论基础数论同余类同余类满足的性质：同余类满足的性质：（ 1）（反身性， Reflexivity）（ 2）（对称性， Symmetry） 若若 则则（ 3）（迁移性， Transitivity）若若 则则例：例： 令令 则则1.7 2006第第 3章章 基础数论基础数论模运算加法：加法：（ 1）封闭性：若同余类）封闭性：若同余类 则则 （ 2）交换律：若同余类）交换律：若同余类 则则 （ 3）结合律：若同余类）结合律：若同余类 则则 （ 4）存在加法单位素：存在）存在加
4、法单位素：存在 ，使得，使得 （ 5）存在加法反元素：对任一）存在加法反元素：对任一 存在存在 使得使得 减法：减法：乘法：乘法：1.8 2006第第 3章章 基础数论基础数论交换群定义定义 （交换群）（交换群） 考虑考虑 ，其中，其中 G为集合，而为集合，而*为运算。令公理：为运算。令公理：（ 1）封闭性：）封闭性： 则；则；（ 2）交换律：）交换律： 则；则；（ 3）结合律：）结合律： 则；则；（ 4）存在单位素：）存在单位素： ， ，使得，使得（ 5）存在反元素：）存在反元素： ， ，使得，使得若公理若公理 1、 3、 4、 5成立，称为成立，称为 群群 (Group)；若以上公理若以上
5、公理 1 5都成立，称为都成立，称为 交换群交换群 。1.9 2006第第 3章章 基础数论基础数论交换环此时除了此时除了 为交换群以外，另外针对乘法为交换群以外，另外针对乘法运算也满足封闭性、交换律、结合律以及存在乘法单运算也满足封闭性、交换律、结合律以及存在乘法单位素（即位素（即 ）等性质，但并）等性质，但并非所有非零元素都有乘法反元素，另外乘法对加法有非所有非零元素都有乘法反元素，另外乘法对加法有分配律，即：分配律，即：若若 则则此时，以代数的术语，称此时，以代数的术语，称 为为 交换环交换环 （Commutative Ring）。）。 考虑考虑1.10 2006第第 3章章 基础数论基础数论辗转相除法例：例： 求 7812及 6084的最大公因子被除数被除数 =商商 除数除数 +余数，余数，gcd（被除数，除数）（被除数，除数） =gcd（除数，余数）（除数，余数）辗转相除法辗转相除法 就是利用此性质，反复以就是利用此性质，反复以（除数（除数 /余数）取代（被除数余数）取代（被除数 /除数）除数） k 0 1 2 3 4 5 6 7rk 7812 6048 1728 900 828 72 36 0qk 1 3 1 1 11 2其中：其中：所以 gcd (7812 , 6084) = 36
