高中数学选修5-3(密码学算法基础) 选修课密码学5 课件

密码学概论 密码学的数学基础 三 稀贵悲倾桃链淹靖赠椰彼侮庇催辐拂舶购伟末氦亦夫傀狸蘸山瘟固严宾年高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 本讲授课提纲 1 模运算和同余 复习 2 乘法逆元素 3 扩展的欧几里德算法 揭滇供苗陵隐迁潜但呵昨荤眶奔舰绷末睫弯尉怀疡灵委疫绝色仙古宦渤廊高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 3 设n是一正整数 a是整数 如果用n除a 得商为q 余数为r 则a qn r 0 r n 用amodn表示余数r 如果 amodn bmodn 则称两整数a和b模n同余 记为a bmodn 称与a模n同余的数的全体为a的同余类 记为 a 称a为这个同余类的表示元素 复习 模运算和同余 粒编擞士芜冬副淤樟盅原秉闯旦晚藐咽尚厚衬键衍收副芳跺尽旨爪莆孔迄高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 复习 模运算和同余 模运算a modn 的运算给出了a对模数n的余数 这种运算称为模运算 modularreduction 从0到n 1的整数组成的集合构成了模n的完全剩余集 这意味着 对于每一个整数a 它的模n的余项是从0到n 1的某个数 鸵孟往寥均措踩价打擂诗似祸览疗憨稳戴缓励郭倾住绢侈共祥污学葛奴柞高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 模运算和同余 同余设整数a b n n 0 如果a b是n的整数倍 正的或负的 我们就说 a与b模n同余 记做a b modn 有时 b被叫做a模n的余数 另一种描述 如果a与b的差能被n整除 就说a b modn 即存在非零整数k 使得a b nk 耍拜计今挛龄琵阑咆洪乏肌氏车仓垃折包奏尼侥图溅仇树基训宪挞阻极萧高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 模运算和同余 同余和模运算的关系同余的另一种定义 如果a modn b modn 则称a和b模n同余 记做a b modn a modn b modn a b modn 举例 73 mod23 4 27 mod23 4 所以73 27 mod23 尘析稚伙沧领剑寿婪漂煌哄遗狐啼康秋福徊叶人液宵会狡咖戚融饱藏肪戳高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 模运算和同余 性质一 当且仅当n a a 0 modn 模运算和同余的性质 性质二 自反性 对任意整数a 有a a modn 性质三 对称性 如果a b modn 那么b a modn 性质四 传递性 如果a b modn b c modn 那么a c modn 性质五 如果m a b 则a b modm 性质六 设整数a b c d n n 0 假设a b modn 且c d modn 那么a c b d modn a c b d modn ac bd modn 付赶休嫉究蓬恰煮持煽骄戍肛锥祷步揭苍戊毅潮硕措挨潮觅穗棒坪憾师畅高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 模运算和同余 模运算的加法和减法 a modn b modn modn a b modn 举例 已知11 mod8 3 15 mod8 7 11 mod8 15 mod8 mod8 3 7 mod8 2 11 15 mod8 26 mod8 2 11 mod8 15 mod8 mod8 3 7 mod8 4 11 15 mod8 4 mod8 4 旱莽掌导眺巩仁讶蛆耳纤扔谋姿跑玻迟拄践粹泊予乞含琉摄原碱腮畦垒围高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 模运算和同余 模运算的乘法的结合律 a modn b modn modn a b modn 举例 11 mod8 15 mod8 mod8 3 7 mod8 21 mod8 5 11 15 mod8 165 mod8 5 掖并鸣窜烟宰岂踪泽编卓代画幻苛黄令勇懈上廷宜瑰烘主乙醛骋唱搪淑瓜高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 模运算和同余 同余的加法消去律如果 a b a c modn 那么b c modn 举例 5 23 5 7 mod8 那么23 7 mod8 废靛舟修乖拯逻讨以刻苗下兔恒呕妖文哄窃瘟炒户但采刊毛诫灼剃字精贷高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 模运算和同余 同余的乘法消去律设整数a b c n n 0 且gcd a n 1 如果ab ac modn 那么b c modn 举例 5 3 15 7 mod8 5 11 55 7 mod8 5 3 5 11 mod8 3 11 mod8 铁俯傀准违炯洛杠硷侥箱牲筐膘票坐晨境狱迸凡郊楞铸橇灰乡服级逃职钨高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 模运算和同余 模n除法模n除法主要用乘法消去律和乘法逆元素来解决举例 解2x 7 3 mod17 2x 3 7 4 mod17 于是有x 2 15 mod17 举例 解5x 6 13 mod11 5x 7 mod11 此处涉及乘法逆元素 一种可行的方法是试探所有的7 18 29 40 51 直到有能被5整除的为止 材府劲屠销焚苛漆婴沟油咐得舆合馈羚攻庙戎鳃皖曝塞刷慎沼特扼剥掸步高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 本讲授课提纲 1 模运算和同余 复习 2 乘法逆元素 3 扩展的欧几里德算法 挪盾葱法肋洒团显西锥严掺拜盂羡猎尤幻例冶阎暮针殃程勾愁陇椿忍日混高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 乘法逆元素 乘法逆元素的引入仿射密码解密时 需由加密函数y 9x 2 mod26 中反解出x x 1 9 y 2 mod26 1 9就表示在模26的条件下 9的乘法逆元素 换句话说 就是 要求在0 1 2 3 4 25找一个数 这个数和9相乘再取模26运算 结果为1 功笨城甸岔篮诅侄歇爬慷娄指寒科坪烩斌我酸酵倒啦本寄恃柄窿驱攫洱窟高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 乘法逆元素 乘法逆元素的一般提法寻找一个x 使得1 a x modn 写成另一种形式 即a 1 x modn 解决乘法逆元素很困难 有时候有一个方案 有时候没有 例如2模14的乘法逆元素就不存在 5模14的乘法逆元素是3 涵谆唯潞鲤遵炒申给玄亭估亥昏讹牧餐缀风品耘巢忠耘咀啥镀斩愚便香簇高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 乘法逆元素 乘法逆元素的定义假设gcd a n 1 则存在整数 使得as 1 modn 即s是a modn 的乘法逆元素 驾眼噶撬咀沉榨挎吊镭芳粪盆坑恬脸恍揖嘶丁撞易甲伙换启谎溃炉呈枝托高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 本讲授课提纲 1 模运算和同余 2 乘法逆元素 3 扩展的欧几里德算法 掉采阀瘪颓叁临菌抡荷颊澡达矣稿缠侣辽尿蚀光遏郧邱鞋啄辖肛准铰秆省高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 扩展的欧几里德算法 关于ax by d 由欧几里德算法可以得到下面的重要结论设a和b是两个正整数 至少有一个非零 d gcd a b 则存在整数x和y使得ax by d成立 如果a和b都是素数 那么存在整数x和y使得ax by 1成立 此时可以求出ax 1 modb 中的x 距浓恩临豫焚竣裔哈桐娃诞恶鲁沤揍悲欧乙梭誓苗促符螺炊握恒排越赂操高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 扩展的欧几里德算法 关于ax by d 求解ax by 1可使用扩展的欧几里德算法 扩展的欧几里德算法不仅能确定两个正整数的最大公约数 如果这两个数互素 还能确定他们各自的乘法逆元素 蔡品泌秀获滥杜痹氏王烽治语送绕郎剪宿柄灭星征刁暖灸牲谋阑魔捷粤歹高中数学选修5 3 密码学算法基础 选修课密码学5课件高中数学选修5 3 密码学算法基础 选修课密码学5课件 扩展的欧几里德算法 扩展的欧几里德算法 1 A1 A2 A3 1 0 m B1 B2 B3 0 1 b 2 ifB3 0 returnA3 gcd m b noinverse ifB3 1 returnB3 gcd m b B2 b 1modm 3 Q A3 B3 4 T1 T2 T3 A1 QB1 A2 QB2 A3 QB3 A1 A2 A3 B1 B2 B3 B1 B2 B3 T1 T2 T3 5 GOTO2 笼补伺