Strong primality tests that are not sufficient
Strong primality tests that are not sufficient
复制标题
强素性测试还不够
DOI：
10.1090/s0025-5718-1982-0658231-9
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
D. Shanks
中科院分区：
文献类型：
--
作者：
W. W. Adams;D. Shanks
。详细研究了三次递归在原数检验中的可能应用。在这个摘要中没有试图涵盖所有在论文中检查的许多主题。用Ain + 3 = H(n + 2) - s/l(n + 1) + Ain定义序列a (n)的双无限集，其中a (-l) = i, a (0) = 3, a (l) = r。如果n是素数，则a (n)是a (l) （mod n）。Perrin问，如果r = 0, s = -1是否有合数满足这个同余。答案是肯定的，我们的第一个例子引导我们通过引入n的“签名”来加强条件：Ai-n - 1),Ai-n),Ai-n+ I), Ain - I), 4（«），。4(/j + 1) mod n。质数有三种类型的签名，这取决于它们如何在x3 - rx2 + sx - 1 = 0生成的三次域中分裂。具有“可接受”签名的复合材料确实存在，但非常罕见。与完全分裂素数对应的5型特征具有非常特殊的作用，甚至有可能/和Q型合数在prcrrin序列中不存在，尽管/和Q质数占所有素数的5/6。A(n) （mod n）很容易在0（log»）次操作中计算出来。本文以p进分析结束。这个强大的工具为我们的[12]奠定了基础，[12]将是本文的第二部分。
. A detailed investigation is given of the possible use of cubic recurrences in primality tests. No attempt is made in this abstract to cover all of the many topics examined in the paper. Define a doubly infinite set of sequences A(n) by Ain + 3) = H(n + 2) - s/l(n + 1) + Ain) with A(-l) = i, A(0) = 3, and A(l) = r. If n is prime, A(n) s A(l) (mod n). Perrin asked if any composite satisfies this congruence if r = 0, s = -1. The answer is yes, and our first example leads us to strengthen the condition by introducing the "signature" of n: Ai-n - l),Ai-n),Ai-n+ I), Ain - I), 4(«), .4(/j + 1) mod n. Primes have three types of signatures depending on how they split in the cubic field generated by x3 — rx2 + sx - 1 = 0. Composites with "acceptable" signatures do exist but are very rare. The 5-type signature, which corresponds to the completely split primes, has a very special role, and it may even be that / and Q type composites do not occur in Pcrrin's sequence even though the / and Q primes comprise 5/6ths of all primes. A(n) (mod n) is easily computable in 0(log») operations. The paper closes with a p-adic analysis. This powerful tool sets the stage for our [12] which will be Part II of the paper.