信息安全数学基础知识点

上传人：思*** IP属地：江苏上传时间：2022-12-01 格式：DOCX 页数：5 大小：25.23KB 积分：15 举报 版权申诉

免费预览已结束，剩余1页可下载查看

 下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

--------第六章素性检验拟素数引例：根据小定理，我们知道：如果n是一个素数，则对任意整数b,()=1,有

bn1n)由此，我们得到：如果一个整数b,()=1,使得bn1(mod

，则n是一个合数。定义1：设n 是一个奇合数，如果整数b,()=1 使得同余式bn1n成立，则n叫做对于基b拟素数。2d 1 2n 1引理：设都是正整数，如果d能整除n则能整除122：设n是一个奇合数，则(i)n是对于基b,(()=1),的拟素数当且仅当b模n1。b()如果n是对于基

1((

b1)=1),

b2)=1),n是对于基bb

的拟素数。1 2()如果n是对于基b,(()=1),的拟素数，则n是对于基

1的拟素数。()b，(()=1),使得同余式bn1n模n的简化剩余系中至少有一半的数使得该同余式不成立。素性检验给定奇整数n3和安全参数t 。1.随即选取整数b ,22.计算rbn1n;

n2；r1n是合数；t上述过程重复次；定义2：合数n称为数，如果对所有的正整数b，()=1, 都有同余式bn1n成立定理3：设n是一个奇合数。(i)如果n被一个大于1平方数整除，则n不是数。1np1

p 是一个无平方数，则n 是数的充要条件是k，p1n1，i

1ik定理4：每个数是至少三个不同素数的乘积1.2.当n

2727拟素数引例：设n是奇素数，根据定理，我们有同余式bn12

b(modn) n 对任意整数b成立因此，如果存在整数b，()=1,使得bn12

b(modn) 则n不是一个素数。1:设nb与nn和b满bn1

b(modn)足条件：

2 n n则n叫做对于基b的拟素数。定理1：如果n是对于基b的拟素数，则n是对于基b的拟素数。素性检验t给定奇整数n3和安全参数.随即选取整数b

2bn2，；r

bn12(modn);1rn1，则n是合数；nsbn 计算符号 rs，则你是合数；t上述过程重复

次。强拟素数n是正奇整数，并且有n12nt，则我们有如下因数分解式：bn11b2n1因此，如果有同余式

)b2n2t) bt)bt)bn1n)则如下同余式至少有一个成立：bt n)bt n)b2t n)b2n1t (modn)nn12ntt设整数b与n互素，如果整数n和b满足条件：bt (modn)0

rs使得b2rt(modn)则n叫做对于基b的强拟素数。定理1：存在无穷多个对于基2的强拟素数。定理2:如果n是对于基b的强拟素数，n是对于基b的拟素数。3nnb，1bn1，的强25%。素性检验给定奇整数n3和安全参数k。n12st，其中t随机选取整数b,2bn2。计算r0

bt(modn)；r 1 rn13.()如果或，则通过检验，可能为素数。回到1，i 0 0继续选取另一个随机整数b,2bn2;0()0

1以及r0

r2(modn)01i；4.(r1i；1

n1，则通过检验，可能为素数。回到1，继续选取另一个随机整数b,2bn2；()否则，有r1

n1r2

r2(modn)1如此继续下去，

人人文库> 全部分类> 教育资料 > 辅导培训

1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。