一种大素数生成方法及其快速求余方法

摘要

本发明提供一种大素数生成方法，通过简单的素数预判断方法，先排除大部分合数，之后再进行素性判断，可减少素性判断的次数，因此提高了速度。同时，在素数预判断中若使用了对30求余的特殊计算方法，以少数次加法代替求余操作，进一步提高了计算速度。

主权项

一种大素数生成方法，其特征在于：包括步骤10、生成随机数：若生成的随机数为偶数，则生成的随机数加1，随机数记为Rn；步骤20、求余计算：设N=P1×P2×P3……Pn，且N＞2，{P1、P2、P3……Pn}为素数序列；任取正整数n，得到对应的N，将Rn对N求余：若N≠30，Rn对N求余，余数记为Re，进入步骤30；若N=30，则按下列方法计算：（1）将随机数Rn的按十六进制表示时的所有半字节数据相加，得到的结果若大于16，则继续将上一次相加得到的结果中所有半字节相加，直到当前相加的结果小于16，记为有效结果；（2）若（1）所得的有效结果为偶数，则将有效结果加上15后作为最终结果，否则保留原值作为最终结果，此最终结果即为随机数Rn对30求余的结果，余数记为Re，进入步骤30；步骤30、素数预判断：设数据序列为小于N的所有素数中删除P1、P2……Pn，并与1一起构成的从小到大排列的序列；数据序列的数据个数记为Ln；判断Re是否在所述数据序列中，若Re不在数据序列中，则判断为合数，认为未通过素数预判断，进入步骤40；否则认为已通过素数预判断，记录余数Re在所述数据序列中的位置，并记为Idx，进入步骤50；步骤40、取所述数据序列中第一个比余数Re大的数D，取Rm=Rn‑Re+D。记录余数Re在上述序列中的位置，记为Idx，进入步骤50；步骤50、进行米勒‑拉宾素性检测算法判断，若结果为素数，则输出素数后结束；若结果为合数，则进入步骤60；步骤60、根据Idx的数值作为索引，取步长序列对应的值进行加到原随机数，结果作为新随机数，同时Idx小于Ln时，Idx加1，若Idx=Ln，则记 Idx=1，然后返回到步骤50，所述步长序列为数据序列的后项减去前项的差，其中最后一个步长等于第一项减去最后一项再加上N。