RSA 演算法(3)

〖Encrypt〗
 
上一篇|下一篇|回文章  分类讨论区   全部讨论区   本讨论区  
 
  发信人: Bird_Bird.pbbs@bbs.nju.edu.cn (Bird Bird), 信区: Encrypt
标  题: RSA 演算法(3)
发信站: PowerBBS NJU Station (Wed Dec 24 04:05:48 1997)
转信站: whbbs!ustcnews!nju_pbbs


还有一些事值得探讨的

首先是质数的选取........

上一篇提到为了使因数分解发生困难, 所选择的质数要愈大愈好,
但这也意味著, 质数的选取也同样的困难......
因为就目前而言, 跟本没有一个所谓的质数产生公式可用........

解析数论上有一个定理, 当 p 很大时, 质数的分布密度与 1/log p 成正比,
也就是说一个质数和下一个质数的差平均而言与 log p 成正比.......
还好 log p 的成长并不会很快, 所以就采用一个方法 --- 暴力搜寻法....
一个数接著一个数找...... 直到找到质数为止.........
即使 n 大到 2^512, 所要花的时间也不会大到天文数字,
用 486 的话, 大概在数秒钟至数十秒之内会找到..... (包括判定的时间)

现在有一个问题了..... 如何去判定一个数是否是质数........
咳....... 大哉问, 因为到目前为止, 并没有一个很有效的方法来判定.......
当然有人会问, 为什麽不用试除法........
嗯...... 如果用这个方法, 2^512 这麽大的数, 大概要除个大於 10^30 年......
虽然如此, 但还是得去判断啊........

有一个方法, 是利用费马小定理去做判定的.......
假设一数 p, 如果 p 是质数, a^p == a mod p,
如果 p 不是质数, 那麽 a^p == a mod p 虽然也有可能成立,
但成立的机率非常小, 而且 p 愈大时机率愈小........
用这种方法, 我们就找一些质数来测定, 比如验证
2^p == 2 mod p, 3^p == 3 mod p, 5^p == 5 mod p..... 等式是否成立....
如此一来, p 是质数的机率就变得非常非常高了.........

 小鸟
--
 * Origin: NJU PowerBBS


 
 
 
  
 
上一篇|下一篇|回文章  分类讨论区   全部讨论区   本讨论区  
 
Copyright(c)2000 白云黄鹤BBS站 All Rights Reserved.