超强伪素数及素性检验加速算法

Accelerating Computation Method for the Hypre-strong Pseudoprime and Prime Tests

提出超强伪素数的概念,并构造超强伪素数检测算法HSP(n,h),可将目前应用最广泛的素性检测算法Miller＿Rabin算法的出错率1 4大为改善,可证明对一个子类HSP(n,h)出错率降为1 30;且只需对后者增加O(log2n)次乘法,便可重复作m次检测,从而达到素性加速检验,可用来生成大素数。

The concept of hyper_strong pseudoprime,as well as the corresponding HSP(n,h) prime test algorithm, is proposed.It can decrease the error rate for the most extensively used prime test Miller_Rabin algorithm 1/4 to 1/30 for one sub_class,which can be repeated fom m times test by increasing \$O(log2 n)\$ times multiplication.Thus, accelerating prime test method can be established and used to generate large prime.