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

按检索

Finding strong pseudoprimes to several bases

Authors:	Zhenxiang Zhang

Institution:	Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, P. R. China - State Key Laboratory of Information Security, Graduate School USTC, 100039 Beijing, P. R. 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 primality testing algorithm which is not only easier to implement but also faster than either the Jacobi sum test or the elliptic curve test. Thanks to Pomerance et al. and Jaeschke, $\psi_m$ are known for $1 \leq m \leq 8$ . Upper bounds for $\psi_9,\psi_{10} \text{ and } \psi_{11}$ were given by Jaeschke. In this paper we tabulate all strong pseudoprimes (spsp's) $n<10^{24}$ to the first ten prime bases $2, 3, \cdots, 29,$ which have the form $n=p\,q$ with odd primes and There are in total 44 such numbers, six of which are also spsp(31), and three numbers are spsp's to both bases 31 and 37. As a result the upper bounds for $\psi_{10}$ and $\psi_{11}$ are lowered from 28- and 29-decimal-digit numbers to 22-decimal-digit numbers, and a 24-decimal-digit upper bound for $\psi_{12}$ is obtained. The main tools used in our methods are the biquadratic residue characters and cubic residue characters. We propose necessary conditions for to be a strong pseudoprime to one or to several prime bases. Comparisons of effectiveness with both Jaeschke's and Arnault's methods are given.

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

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

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