Finding C3-strong pseudoprimes
Finding C3-strong pseudoprimes
复制标题
DOI：
10.1090/s0025-5718-04-01693-x
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Zhenxiang Zhang
中科院分区：
文献类型：
--
作者：
Zhenxiang Zhang
设q1 < q2 < q3是奇素数，N = q1 q2 q3。设d = gcd（q1 − 1，q2 − 1，q3 − 1）和hi = qi−1 d，i = 1，2，3。然后我们称d为核，三元组（h1，h2，h3）为签名，H = h1 h2 h3分别为N的高度。我们称N为C3-数，如果它是一个卡迈克尔数，每个素因子qi_3 mod 4。若N是一个C3-数，且是t个基bi的强伪素数，其中1 ≤ i ≤ t，则称N为C3-spsp（b1，b2，. . .，bt）。由于C3-数的错误概率为1/4（Rabin-Miller检验的上界），因此它们通常用作C3-数的精确值或上界（所有前m个素数基的最小强伪素数）。如果我们知道n <m的确切值，我们将有一个确定的有效的素性测试算法，它很容易实现。在本文中，我们首先描述了一个算法，寻找C3-spsp（2）的，到一个给定的限制，高度有界。总共有21978个C3-spsp（2）< 1024且高度< 109。然后我们给出了21978个C3 spsp（2）的概述，并列出了其中的54个，这是C3-spsp的前8个素数基到19;三个数字是spsp的前11个素数基到31。对于高度< 109的前12个素数基，没有发现C3-spsp < 1024的情况，我们推测高度≥ 109的前12个素数基，不存在C3-spsp < 1024的情况，因此，C3-spsp = 3186 65857 83403 11511 67461（24位数）= 399165290221 · 798330580441，这是作者在早期论文中发现的。我们给出了支持这一猜想的理由。我们寻找这21978个C3-spsp（2）的方法的主要思想是，我们循环高度有界的签名和核的候选者，使C3-spsp（2）的这些候选者N = q1 q2 q3及其素因子q1，q2，q3经受米勒检验，并获得所需的数字。最后，我们加快我们的算法找到更大的C3-spsp的，说高达1050，与一个给定的签名更多的总理基地。与Arnault的和我们以前的方法寻找C3-强伪素数的前几个素基的有效性的比较。
Let q1 < q2 < q3 be odd primes and N = q1q2q3. Put d = gcd(q1 − 1, q2 − 1, q3 − 1) and hi = qi−1 d , i = 1, 2, 3. Then we call d the kernel, the triple (h1, h2, h3) the signature, and H = h1h2h3 the height of N , respectively. We call N a C3-number if it is a Carmichael number with each prime factor qi ≡ 3 mod 4. If N is a C3-number and a strong pseudoprime to the t bases bi for 1 ≤ i ≤ t, we call N a C3-spsp(b1, b2, . . . , bt). Since C3-numbers have probability of error 1/4 (the upper bound of that for the Rabin-Miller test), they often serve as the exact values or upper bounds of ψm (the smallest strong pseudoprime to all the first m prime bases). If we know the exact value of ψm, we will have, for integers n < ψm, a deterministic efficient primality testing algorithm which is easy to implement. In this paper, we first describe an algorithm for finding C3-spsp(2)’s, to a given limit, with heights bounded. There are in total 21978 C3-spsp(2)’s < 1024 with heights < 109. We then give an overview of the 21978 C3spsp(2)’s and tabulate 54 of them, which are C3-spsp’s to the first 8 prime bases up to 19; three numbers are spsp’s to the first 11 prime bases up to 31. No C3-spsp’s < 1024 to the first 12 prime bases with heights < 109 were found. We conjecture that there exist no C3-spsp’s < 1024 to the first 12 prime bases with heights ≥ 109 and so that ψ12 = 3186 65857 83403 11511 67461 (24 digits) = 399165290221 · 798330580441, which was found by the author in an earlier paper. We give reasons to support the conjecture. The main idea of our method for finding those 21978 C3spsp(2)’s is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates N = q1q2q3 of C3-spsp(2)’s and their prime factors q1, q2, q3 to Miller’s tests, and obtain the desired numbers. At last we speed our algorithm for finding larger C3-spsp’s, say up to 1050, with a given signature to more prime bases. Comparisons of effectiveness with Arnault’s and our previous methods for finding C3-strong pseudoprimes to the first several prime bases are given.