适用于密码学应用的素数生成方法

摘要

本发明公开了一种适用于密码学应用的素数生成方法，将随机数和一系列小素数通过求最大公约数的方法进行素数预检测，仅当该随机数与这些小素数都互素时能够通过素数预检测，再将通过素数预检测的随机数进行素性检测。由于通过预检测的方法能够排除掉一部分合数，因而使得预检测之后的素性检测的循环次数能够大大减少。传统的素数生成方法为直接对随机数进行素性检测，因此需要进行大量的素性检测运算；在通常实现情况下，素性检测的时间要远远大于求最大公约数的时间，因此本发明的方法能够大幅改善素数生成的运算速度和时间。