《素性检测运算快速算法》由会员分享，可在线阅读，更多相关《素性检测运算快速算法（2页珍藏版）》请在装配图网上搜索。
1、素性检测快速算法优化的Miller-Rabin算法待测数生成当某一待测数被测试为合数后，采用对原数加2而非重新产生随机数的方法产生新的待测数。小素数集测试在素性测试时，针对每种位长的待测数分别选定小素数集合，最大选择24元素集合，即不包含2的小于100的素数构成的集合。将最小的6个素数组合进行测试，即3*17、5*13、7*11分别作为一个除数进行试除，再根据余数是否含有这几个小素数因子来确定待测数是否能被小素数整除，这样可以约减少3次试除。(1) Miller-Rabin测试素性检测的主体是进行Miller-Rabin测试：令n=2sd+1，其中s为非负整数，d为正奇数。设2an-1，若ad
2、三1(modn)或存在r使得ad=-1(modn)成立，0rs-1，贝y称n通过以a为基的Miller-Rabin测试。测试流程如下图所示。图优化的Miller-Rabin素性测试按照完整的Miller-Rabin测试过程，当图中V丰1时，应进一步判断被测数是否满足第二种情况，即是否存在丫使a2rd=1(modn)成立。通过软件测试发现，当V丰1时，被测数通过Miller-Rabin测试的可能性很小。因此，在软件实现时对被测数是否满足第二种情况的判断略去，这样虽可能使一些真正的素数被当作合数过滤掉，但总体来说使生成素数的速度更快。Miller-Rabin测试给出了被测数是素数的必要条件，而非充分条件。该测试有这样一个性质：若n是奇合数，则n通过Miller-Rabin测试的基a的个数最多为(n-D；4，2an-1。例如选择基的个数为5时，产生伪素数的可能性为145，加之小素数集测试，n为素数的概率已经超过了99.9%。在生成密钥对之后，选择一个较小的数进行一次加密解密/签名验证的正确性检验，从而保证通过测试的数确为素数。
素性检测运算快速算法
