| 2.3素数的预筛选
素数的测试比较费时，所以在测试前将合数滤掉可以提高效率。通常使用试除法进行过滤，即用小素数如3，5，7，11……等去试除待测数，如果能除尽，则为合数。通过这种方法，可以先行排除掉一些比较明显的合数，提高待测数的素性检测速度。
2.4素数的素性验证
对于一个数是否是素数，必须经过详细的判断，因为，越是位数大的素数，越难于判断其素性。素数验证方法有多种，本文选用Rabin-Miller方法。
首先选一个待测的随机p，计算b，b是2整除p-1的次数。然后计算m，使得n=1+(2^b)m。
(1)选择一个小于p的随机数a；
(2)设j=0且z=a^mmodp；
(3)如果z=1或z=p-1，那么p通过测试，可能是素数；
(4)如果j>0且z=1,那么p不是素数；
(5)设j=j+1。如果j且zp-1,设z=z^2modp，然后回到(4)。如果z=p-1，那么p通过测试，可能为素数；
(6)如果j=b且zp-1，不是素数。
这个测试速度较快。数a被当成证据的概率为75%。这意味着当迭代次数为t时，它产生一个假的素数所花费的时间不超过1/4^t。实际上，对大多数随机数，几乎99.99%肯定a是证据。
2.5算法设计
参考以上关于素数的生成过程，对于本文的素数生成算法设计如下：
·通过伪随机发生器生成一个n位的随机数p，n>100；
·判断随机数p的奇偶性，如果随机数是偶数，则加1；
·用小于2000的素数对p进行整除，先行筛去比较容易辨认的合数。如果能够整除则重新生成一个新的随机数，如果都不能整除，则进行下一步的拣选；
·对某随机数a运行Rabin-Miller检测，如果p通过，则另外产生一个随机数a，再测试。选取较小的a值，以保证速度。做5次Rabin-Miller测试，如果p在其中失败，重新产生p，再测试。
3结束语
本文对数字签名技术的原理和加密算法做了详尽地介绍，设计了一种非常有效的算法，并在实际应用中得到了验证，运用此算法可以提高加密效率。
参考文献
1 王东临.电子印章让电子签名走向百姓.信息化建设.2005.5 ( 22-23)
2 李希.从《中华人民共和国电子签名法》的实施谈银行中的数字签名应用.金融实务.2005.5 (57-59)
3 黄磊,陈海,李建民,袁唯才.数字签名技术在政府公文处理系统中的应用.计算基与现代化.2003.7 (52-54)
4 耿海飞,苏锦海.大素数的快速生成研究与实现.电脑与信息技术.2005.(13).2 (9-11) 2/2 首页 上一页 1 2 |
