信息安全数学基础知识点中学教育中考_中学教育-中学课件.pdf

《信息安全数学基础知识点中学教育中考_中学教育-中学课件.pdf》由会员分享，可在线阅读，更多相关《信息安全数学基础知识点中学教育中考_中学教育-中学课件.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习必备 欢迎下载 第六章 素性检验 6.1 拟素数 引例：根据 Fermat 小定理，我们知道：如果 n 是一个素数，则对任意整数 b,(b,n)=1,有 )(mod11nbn 由此，我们得到：如果一个整数 b,(b,n)=1,使得 )(mod11nbn，则 n 是一个合数。定义 1：设 n 是一个奇合数，如果整数 b,(b,n)=1使得同余式 )(mod11nbn成立，则 n 叫做对于基 b 的拟素数。引理：设 d,n 都是正整数，如果 d 能整除 n 则12 d能整除12 n 定理 1：存在无穷多个对于基 2 的拟素数。定理 2：设 n 是一个奇合数，则(i)n 是对于基 b,(b,n)

2、=1),的拟素数当且仅当 b 模 n 的指数整除 n-1。(ii)如果 n 是对于基1b(1b,n)=1),和基2b，(2b,n)=1),的拟素数，则n 是对于基21bb的拟素数。(iii)如果 n 是对于基 b,(b,n)=1),的拟素数，则 n 是对于基1b的拟素数。(iv)如果有一个整数 b，(b,n)=1),使得同余式)(mod11nbn不成立，则模 n 的简化剩余系中至少有一半的数使得该同余式不成立。/学习必备 欢迎下载 Fermat 素性检验 给定奇整数3n和安全参数t。1.随即选取整数b,22nb；2.计算nbrnmod1;3.如果1r，则 n 是合数；4.上述过程重复t次；定义

3、 2：合数 n 称为 Carmichael 数，如果对所有的正整数 b，(b,n)=1,都有同余式nbnmod11成立 定理 3：设 n 是一个奇合数。(i)如果 n 被一个大于 1 平方数整除，则 n 不是 Carmichael 数。(ii)如果kppn1是一个无平方数，则 n 是 Carmichael 数的充要条件是 11 npi，ki 1 定理 4：每个 Carmichael 数是至少三个不同素数的乘积 注：1.存在无穷多个 Carmichael 数 2.当 n 充分大时，区间 n,2内的 Carmichael 数的个数大于等于72n 6.2 Euler 拟素数 引例：设 n 是奇素数，

4、根据定理，我们有同余式 )(mod21nnbbn 对任意整数 b 成立 因此，如果存在整数 b，(b,n)=1,使得 如果一个整数使得则是一个合数定义设是一个奇合数如果整数使得同余式成立则叫做对于基的拟素数引理设都是正整数如果能整除则定理存在无穷多个对于基的拟素数定理设是一个奇合数则能整除是对于基的拟素数当且仅当模的指数使得同余式不成立则模的简化剩余系中至少有一半的数使得该同余式不成立学习必备欢迎下载素性检验给定奇整数和安全参数随即选取整数计算如果则是合数上述过程重复次定义合数称为数如果对所有的正整数都有同余式成立定少三个不同素数的乘积注存在无穷多个数内的数的个数大于等于当充分大时区间拟素数引

5、例设是奇素数根据定理我们有同余式对任意整数成立因此如果存在整数使得学习必备欢迎下载则不是一个素数定义设是一个正奇合数设整数与学习必备 欢迎下载 )(mod21nnbbn 则 n 不是一个素数。定义 1:设 n 是一个正奇合数，设整数 b 与 n 互素，如果整数 n 和 b 满足条件：)(m o d21nnbbn 则 n 叫做对于基 b 的Euler 拟素数。定理 1：如果 n 是对于基 b 的 Euler 拟素数，则 n 是对于基 b 的拟素 数。/Solovay-Stassen 素性检验 给定奇整数3n和安全参数t.1.随即选取整数b，22nb；2.计算);(mod21nbrn 3.如果1r

6、以及1 nr，则 n 是合数；4.计算 Jacobi 符号;nbs 5.如果sr，则你是合数；6.上述过程重复t次。6.3 强拟素数 引例：设 n 是正奇整数，并且有tnn21，则我们有如下因数分解式：)1)(1()1)(1(121221ttttnbbbbbnn 如果一个整数使得则是一个合数定义设是一个奇合数如果整数使得同余式成立则叫做对于基的拟素数引理设都是正整数如果能整除则定理存在无穷多个对于基的拟素数定理设是一个奇合数则能整除是对于基的拟素数当且仅当模的指数使得同余式不成立则模的简化剩余系中至少有一半的数使得该同余式不成立学习必备欢迎下载素性检验给定奇整数和安全参数随即选取整数计算如果则

7、是合数上述过程重复次定义合数称为数如果对所有的正整数都有同余式成立定少三个不同素数的乘积注存在无穷多个数内的数的个数大于等于当充分大时区间拟素数引例设是奇素数根据定理我们有同余式对任意整数成立因此如果存在整数使得学习必备欢迎下载则不是一个素数定义设是一个正奇合数设整数与学习必备 欢迎下载 因此，如果有同余式 )(m o d11nbn 则如下同余式至少有一个成立：)(mod1)(mod1)(mod1)(mod1122nbnbnbnbttttn 定义 1：设 n 是一个奇合数，且有表达式tnn21，其中 t 为奇数，设整数 b 与 n 互素，如果整数 n 和 b 满足条件：)(mod1nbt 或者

8、存在一个整数，sr 0使得 )(mod12nbtr 则 n 叫做对于基 b 的强拟素数。定理 1：存在无穷多个对于基 2 的强拟素数。定理 2:如果 n 是对于基 b 的强拟素数，n 是对于基 b 的 Euler 拟素数。定理 3：设 n 是一个奇合数，则 n 是对于基 b，11nb，的强拟素数的可能性至多为 25%。/Miller-Rabin素性检验 给定奇整数3n和安全参数 k。写tns21，其中 t 为奇整数。如果一个整数使得则是一个合数定义设是一个奇合数如果整数使得同余式成立则叫做对于基的拟素数引理设都是正整数如果能整除则定理存在无穷多个对于基的拟素数定理设是一个奇合数则能整除是对于基

9、的拟素数当且仅当模的指数使得同余式不成立则模的简化剩余系中至少有一半的数使得该同余式不成立学习必备欢迎下载素性检验给定奇整数和安全参数随即选取整数计算如果则是合数上述过程重复次定义合数称为数如果对所有的正整数都有同余式成立定少三个不同素数的乘积注存在无穷多个数内的数的个数大于等于当充分大时区间拟素数引例设是奇素数根据定理我们有同余式对任意整数成立因此如果存在整数使得学习必备欢迎下载则不是一个素数定义设是一个正奇合数设整数与学习必备 欢迎下载 1.随机选取整数22,nbb。2.计算)(mod0nbrt；3.(i)如果10r或10 nr，则通过检验，可能为素数。回到 1，继续选取另一个随机整数22

10、,nbb;(ii)否则，有10r以及10nr，我们计算)(mod201nrr；4.(i)如果11 nr，则通过检验，可能为素数。回到 1，继续选取另一个随机整数22,nbb；(ii)否则，有11nr，我们计算)(mod212nrr；如此继续下去，S+2.(i)如果11nrs，则通过检验，可能为素数。回到 1，继续选取另一个随机整数22,nbb;(ii)否则，有11nrs，n 为合数。如果一个整数使得则是一个合数定义设是一个奇合数如果整数使得同余式成立则叫做对于基的拟素数引理设都是正整数如果能整除则定理存在无穷多个对于基的拟素数定理设是一个奇合数则能整除是对于基的拟素数当且仅当模的指数使得同余式不成立则模的简化剩余系中至少有一半的数使得该同余式不成立学习必备欢迎下载素性检验给定奇整数和安全参数随即选取整数计算如果则是合数上述过程重复次定义合数称为数如果对所有的正整数都有同余式成立定少三个不同素数的乘积注存在无穷多个数内的数的个数大于等于当充分大时区间拟素数引例设是奇素数根据定理我们有同余式对任意整数成立因此如果存在整数使得学习必备欢迎下载则不是一个素数定义设是一个正奇合数设整数与