Finding strong pseudoprimes to several bases. II期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Finding strong pseudoprimes to several bases. II

Authors:	Zhenxiang Zhang Min Tang

Institution:	Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, Peoples Republic of China ; Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, Peoples Republic of China

Abstract:	Define $\psi_m$ to be the smallest strong pseudoprime to all the first prime bases. If we know the exact value of $\psi_m$ , we will have, for integers $n<\psi_m$ , a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the $\psi_m$ are known for $1 \leq m \leq 8$ . Upper bounds for $\psi_9,\psi_{10} \text{ and } \psi_{11}$ were first given by Jaeschke, and those for $\psi_{10} \text{ and } \psi_{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<10^{24}$ to the first five or six prime bases, which have the form $n=p\,q$ with odd primes and $q-1=k(p-1), k=4/3,\,5/2,\,3/2,\,6$ ; then we tabulate all Carmichael numbers $<10^{20}$ , to the first six prime bases up to 13, which have the form with each prime factor $q_i\equiv 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 $\psi_{9}, \psi_{10}$ and $\psi_{11}$ are lowered from 20- and 22-decimal-digit numbers to a 19-decimal-digit number: $\begin{displaymath}\begin{split} \psi_{9}\leq \psi_{10}\leq \psi_{11}\leq Q_{11}... ...(19 digits)} &= 149491\cdot 747451\cdot 34233211. \end{split}\end{displaymath}$ We conjecture that $\begin{displaymath}\psi_{9}= \psi_{10}= \psi_{11}=3825123056546413051,\end{displaymath}$ and give reasons to support this conjecture. The main idea for finding these Carmichael numbers is that we loop on the largest prime factor and propose necessary conditions on to be a strong pseudoprime to the first 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.

Keywords:	Strong pseudoprimes Carmichael numbers Rabin-Miller test biquadratic residue characters cubic residue characters Chinese remainder theorem

	点击此处可从《Mathematics of Computation》浏览原始摘要信息
	点击此处可从《Mathematics of Computation》下载免费的PDF全文

设为首页 | 免责声明 | 关于勤云 | 加入收藏