Finding strong pseudoprimes to several bases II
Finding strong pseudoprimes to several bases II
复制标题
DOI：
10.1090/s0025-5718-03-01545-x
复制
发表时间：
2003-10
期刊：
影响因子：
--
通讯作者：
Zhenxiang Zhang;M. Tang
中科院分区：
文献类型：
--
作者：
Zhenxiang Zhang;M. Tang
定义ψm为所有前m个素基的最小强伪素。如果我们知道ψm的精确值，对于整数n>；ψm，我们将有一个确定的、高效的、易于实现的素性测试算法。多亏了波美兰斯等人。和Jeschke，ψm表示1≤m≤8。ψg，ψ10和ψ11的上界最先由Jeschke给出，ψ10和ψ11的上界随后由第一作者在他的前一篇论文(Math.公司。70(2001)，863-872)。本文首先以双二次剩余特征标和三次剩余特征标为主要工具，列出了所有强伪素数(SPSP‘s)n>；1024到前五个或六个素数基，它们的形式为n=pq，p，q奇素数，q-1=k(p-1)，k=4/3，5/2，3/2，6；总共有36个这样的卡迈克尔数，其中12个数也是从≡到基17；有5个数是从17和19开始的；一个数是从前11个素数到31个素基的。因此，ψ9、ψ10和ψ11的上限从20位和22位十进制数字降低为19位十进制数字：ψ9≤ψ10≤ψ11≤Q11=3825 12305 65464 13051(19位数)=149491ċ747451ċ34233211。我们猜想ψ9=ψ10=ψ11=3825 12305 65464 13051，并给出了支持这一猜想的理由。寻找这些Carmichael数的主要思想是，我们在最大素因数Q3上循环，并提出关于n是前5个素基的强伪素的必要条件。给出了与Arnault、Bleichenbacher、Jeschke和Pinch的方法求具有三个素数因子的(Carmichael)数的有效性的比较，这三个素因数对前几个素基是强伪素。
Define ψm to be 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. Thanks to Pomerance et al. and Jaeschke, the ψm are known for 1 ≤ m ≤ 8. Upper bounds for ψg, ψ10 and ψ11 were first given by Jaeschke, and those for ψ10 and ψ11 were then sharpened by the first author in his previous paper (Math. Comp. 70 (2001), 863-872).In this paper, we first follow the first author's previous work to use biquadratic residue characters and cubic residue characters as main tools to tabulate all strong pseudoprimes (spsp's) n > 1024 to the first five or six prime bases, which have the form n = pq with p,q odd primes and q - 1 = k(p-1), k = 4/3, 5/2, 3/2, 6; then we tabulate all Carmichael numbers > 1020, to the first six prime bases up to 13, which have the form n = q1q2q3 with each prime factor qi ≡ 3 mod 4. There are in total 36 such Carmichael numbers, 12 numbers of which are also spsp's to base 17; 5 numbers are spsp's to bases 17 and 19; one number is an spsp to the first 11 prime bases up to 31. As a result the upper bounds for ψ9, ψ10 and ψ11 are lowered from 20- and 22-decimal-digit numbers to a 19-decimal-digit number: ψ9 ≤ ψ10 ≤ ψ11 ≤ Q11 = 3825 12305 65464 13051 (19 digits) = 149491 ċ 747451 ċ 34233211. We conjecture that ψ9 = ψ10 = ψ11 = 3825 12305 65464 13051, and give reasons to support this conjecture. The main idea for finding these Carmichael numbers is that we loop on the largest prime factor q3 and propose necessary conditions on n to be a strong pseudoprime to the first 5 prime bases. Comparisons of effectiveness with Arnault's, Bleichenbacher's, Jaeschke's, and Pinch's methods for finding (Carmichael) numbers with three prime factors, which are strong pseudoprimes to the first several prime bases, are given.