公钥密码体制加解密算法基于两个大素数乘积的难分解性。为了提升大素数生成算法的效率和降低算法的报错率,提出了一种基于概率论的方法,通过优化Eratosthenes筛法构建素数库,从而通过分析素数库中素数尾数的分类频数和表达式下素数频率,再通过对素数检验算法进行分析,最后得到一种高效的大素数生成算法。在算法中,任意初始的整数都具有较高的素数概率,从根本上提升了算法的执行效率。