信息安全数学基础(第二章)课件

1第二章第二章 同余同余要求：掌握同余、剩余类、完全剩余系和简化剩余系等定义，熟练运用同余运算、欧拉定理、费马小定理以及模重复平方法。1第二章 同余要求：掌握同余、剩余类、完全剩余系和简化剩余22.1 2.1 同余的概念及其基本性质同余的概念及其基本性质一、基本概念一、基本概念22.1 同余的概念及其基本性质一、基本概念3二、基本定理及性质二、基本定理及性质3二、基本定理及性质44556同余式可逐同余式可逐项相相加、减、乘加、减、乘6同余式可逐项相加、减、乘77889910101111121213131414151516161717181819192020212122222323242425三、验算整数计算结果的方法（弃九法）三、验算整数计算结果的方法（弃九法）25三、验算整数计算结果的方法（弃九法）26262727282.2 2.2 剩余类及完全剩余系剩余类及完全剩余系一、基本概念一、基本概念282.2 剩余类及完全剩余系一、基本概念2929303031313232333334二、有关完全剩余系的几个定理二、有关完全剩余系的几个定理34二、有关完全剩余系的几个定理353536363737383839394040414142424343442.3 2.3 简化剩余系与欧拉函数简化剩余系与欧拉函数一、欧拉一、欧拉(Euler)函数函数442.3 简化剩余系与欧拉函数一、欧拉(Euler)函数45二、简化剩余系二、简化剩余系45二、简化剩余系4646474748484949505051三、有关简化剩余系的定理三、有关简化剩余系的定理51三、有关简化剩余系的定理52525353545455 如何找到如何找到a呢？利用广呢？利用广义Euclid除法除法：思考思考题：唯一性？：唯一性？55 如何找到a呢？利用广义Euclid除法：思考题：唯一5656575758由定理由定理2.2.4（根据第一章关于最大公因数的定理）（根据第一章关于最大公因数的定理）58由定理2.2.4（根据第一章关于最大公因数的定理）595960四、欧拉函数的性质及计算方法四、欧拉函数的性质及计算方法60四、欧拉函数的性质及计算方法61616262636364646565666667676868692.4 2.4 欧拉定理欧拉定理 费马小定理费马小定理692.4 欧拉定理 费马小定理7070717172m为素数素数时，有，有Fermat定理定理72m为素数时，有Fermat定理737374由定理由定理2.3.474由定理2.3.475因因p,q=pq=n75因p,q=pq=n76由定理由定理2.3.476由定理2.3.47777787879798080812.5 2.5 模重复平方计算法模重复平方计算法812.5 模重复平方计算法828283838484858586第二章作业交作业时间：第三章结束之前交给学习委员，上课时统一交给我。不需要交作业本，作业可以写在纸上，第一页上方写上姓名、学号、班级。86第二章作业交作业时间：第三章结束之前交给学习委员，上课时