Jacobi和素性测定算法在PC上的实现

Implementation of the Primality Testing Algorithm with Jacobi Sums on PCs

我们在ＰＣ机上实现了Ａｄｌｅｍａｎ－Ｐｏｍｅｒａｎｃｅ－Ｒｕｍｅｌｙ的Ｊａｃｏｂｉ和素性测定算法的Ｃｏｈｅｎ－Ｌｅｎｓｔｒａ版本。我们的Ｐａｓｃａｌ程序在４８６微机上对１０４位素数的严格素性证明在５分钟内完成。特别地，我们证明了１０１０３＋１２９是素数。本文给出我们的程序对此数的严格素性证明所用的主要参数、一些中间数据和算法各步骤实际耗时。

We have implemented the Cohen-Lenstra versoin of the AdlemanPomerance-Rumely primality test with Jacobi smns on PCs. With our Pascal program, a rigorous proof for primality of a 104-digit prime can be dune within five minutes on a PC486. Especially we have proved that 10103+ 129 is prime. In this report we give some main parameters we used for the proof of the primality of this number, some in termedian data and the running time for each step of the algorithm.