一种改进的快速生成大素数的方法

摘要

本发明公开了一种改进的快速生成大素数的方法，该方法能够快速生成大素数，是基于Miller-Rabin素数检测算法，通过加入预处理过程，并且采用Montgomery模乘算法对原Miller-Rabin算法检测素数进行了优化。Montgomery模乘算法采用的是模加右移的方法，有效地避免了求模运算中比较耗时的除法运算，减少了原算法中模幂运算的次数,从而大大提高了对于素数的检测速度。

主权项

一种改进的快速生成大素数的方法，其特征在于，所述方法包括如下步骤：步骤1：首先随机生成指定位数的大整数；步骤1‑1：定义一个数组，其中数组中的每一个元素的范围是0～0xFFFFFFFF；步骤1‑2：以时间为随机种子；步骤1‑3：循环随机的产生数组中的每一个元素上的数；步骤1‑4：循环结束后，使最高位的元素与0x80000000进行按位或运算，使得产生的大整数的最高位是1，即保证大数的位数；步骤2：对产生的随机大整数进行预处理：步骤3：对步骤2中经过预处理后的大整数进行5次的Miller‑Rabin算法检测；步骤4：如果5次都通过检测，则该大整数就是素数，转到步骤6；步骤5：如果没有通过检测，则在该大整数数的基础上加上预先定义的素数表PrimeTableB[N]中的数，转到步骤2；步骤6：保存并输出该大素数。