信息安全数学基础知识点

第六章 素性检验 6.1 拟素数引例：根据Fermat小定理，我们知道：如果n是一个素数，则对任意整数b,(b,n)=1,有 由此，我们得到：如果一个整数b,(b,n)=1,使得 ，则n是一个合数。定义1：设n是一个奇合数，如果整数b,(b,n)=1使得同余式 成立，则n叫做对于基b的拟素数。引理：设d,n都是正整数，如果d能整除n则能整除定理1：存在无穷多个对于基2的拟素数。定理2：设n是一个奇合数，则(i)n是对于基b,(b,n)=1),的拟素数当且仅当b模n的指数整除n-1。(ii)如果n是对于基(,n)=1),和基，(,n)=1),的拟素数，则n是对于基的拟素数。(iii)如果n是对于基b,(b,n)=1),的拟素数，则n是对于基的拟素数。(iv)如果有一个整数b，(b,n)=1),使得同余式不成立，则模n的简化剩余系中至少有一半的数使得该同余式不成立。/Fermat 素性检验给定奇整数和安全参数。1. 随即选取整数,；2. 计算;3. 如果，则n是合数；4. 上述过程重复次；定义2：合数n称为Carmichael数，如果对所有的正整数b，(b,n)=1, 都有同余式成立定理3：设n是一个奇合数。(i)如果n被一个大于1平方数整除，则n不是Carmichael数。(ii)如果是一个无平方数，则n是Carmichael数的充要条件是 ，定理4：每个Carmichael数是至少三个不同素数的乘积注：1.存在无穷多个Carmichael数2.当n充分大时，区间内的Carmichael数的个数大于等于 6.2 Euler拟素数引例：设n是奇素数，根据定理，我们有同余式 对任意整数b成立 因此，如果存在整数b，(b,n)=1,使得 则n不是一个素数。定义1:设n是一个正奇合数，设整数b与n互素，如果整数n和b满足条件： 则n叫做对于基b的Euler拟素数。定理1：如果n是对于基b的Euler 拟素数，则n是对于基b的拟素 数。 /Solovay-Stassen素性检验给定奇整数和安全参数.1. 随即选取整数，；2. 计算3. 如果以及，则n是合数；4. 计算Jacobi符号5. 如果，则你是合数；6. 上述过程重复次。 6.3 强拟素数引例：设n是正奇整数，并且有，则我们有如下因数分解式： 因此，如果有同余式 则如下同余式至少有一个成立： 定义1：设n是一个奇合数，且有表达式，其中t为奇数，设整数b与n互素，如果整数n和b满足条件： 或者存在一个整数，使得 则n叫做对于基b的强拟素数。定理1：存在无穷多个对于基2的强拟素数。定理2:如果n是对于基b的强拟素数，n是对于基b的Euler拟素数。定理3：设n是一个奇合数，则n是对于基b，的强拟素数的可能性至多为25%。/Miller-Rabin素性检验给定奇整数和安全参数k。写，其中t为奇整数。1. 随机选取整数。2. 计算；3. (i)如果或，则通过检验，可能为素数。回到1，继续选取另一个随机整数; (ii)否则，有以及，我们计算；4. (i)如果，则通过检验，可能为素数。回到1，继续选取另一个随机整数； (ii)否则，有