信息安全数学基础知识点

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则12d能整除12n定理 1：存在无穷多个对于基2的拟素数。定理 2：设 n

2、是一个奇合数，则(i)n 是对于基 b,(b,n)=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.随即选取整

3、数b,22nb；2.计算nbrnmod1; 3.如果1r，则 n 是合数；4.上述过程重复t次；定义 2：合数 n称为 carmichael数，如果对所有的正整数b，(b,n)=1, 都有同余式nbnmod11成立定理 3：设 n是一个奇合数。(i)如果 n被一个大于 1平方数整除，则n不是 carmichael数。(ii)如果kppn1是一个无平方数，则n 是 carmichael数的充要条件是11npi，ki1定理 4：每个 carmichael数是至少三个不同素数的乘积注：1.存在无穷多个 carmichael数2.当 n充分大时，区间n,2内的 carmichael数的个数大于等于72

4、n6.2 euler拟素数引例：设 n 是奇素数，根据定理，我们有同余式)(mod21nnbbn精品好资料 -如有侵权请联系网站删除精品好资料 -如有侵权请联系网站删除对任意整数 b 成立因此，如果存在整数b，(b,n)=1,使得)(mod21nnbbn则 n 不是一个素数。定义 1:设 n是一个正奇合数，设整数b与 n互素，如果整数 n 和 b满足条件：)(mod21nnbbn则 n 叫做对于基 b 的euler 拟素数。定理 1：如果 n是对于基 b的 euler 拟素数，则 n是对于基 b的拟素数。/ solovay-stassen素性检验给定奇整数3n和安全参数t. 1.随即选取整数b

5、，22nb；2.计算);(mod21nbrn3.如果1r以及1nr，则 n 是合数；4.计算 jacobi符号;nbs5.如果sr，则你是合数；6.上述过程重复t次。6.3 强拟素数精品好资料 -如有侵权请联系网站删除精品好资料 -如有侵权请联系网站删除引例：设 n 是正奇整数，并且有tnn21，则我们有如下因数分解式：) 1)(1() 1)(1(121221ttttnbbbbbnn因此，如果有同余式)(mod11nbn则如下同余式至少有一个成立：)(mod1)(mod1)(mod1)(mod1122nbnbnbnbttttn定义 1：设 n是一个奇合数，且有表达式tnn21，其中 t为奇数，

6、设整数b 与 n 互素，如果整数 n 和 b 满足条件：)(mod1nbt或者存在一个整数，sr0使得)(mod12nbtr则 n 叫做对于基 b 的强拟素数。定理 1：存在无穷多个对于基2的强拟素数。定理 2:如果 n是对于基 b 的强拟素数， n 是对于基 b 的 euler拟素数。定理 3：设 n是一个奇合数，则n是对于基 b，11nb，的强拟素数的可能性至多为25%。/ 精品好资料 -如有侵权请联系网站删除精品好资料 -如有侵权请联系网站删除miller-rabin 素性检验给定奇整数3n和安全参数 k。写tns21，其中 t 为奇整数。1.随机选取整数22,nbb。2.计算)(mod0nbrt；3.(i)如果10r或10nr，则通过检验，可能为素数。回到1，继续选取另一个随机整数22,nbb; (ii)否则，有10r以及10nr，我们计算)(mod201nrr；4.(i)如果11nr，则通过检验，可能为素数。回到1，继续选取另一个随机整数22,nbb； (ii)否