信息安全数学基础知识点(共5页).doc

精选优质文档-倾情为你奉上第六章 素性检验 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是对于基的拟素数。