Two kinds of strong pseudoprimes up to 1036
Two kinds of strong pseudoprimes up to 1036
复制标题
DOI：
10.1090/s0025-5718-07-01977-1
复制
发表时间：
2007-10
期刊：
影响因子：
--
通讯作者：
Zhenxiang Zhang
中科院分区：
文献类型：
--
作者：
Zhenxiang Zhang
设n > 1是一个奇合数。写n - 1 = 2 s d，d为奇数。如果对于某个r = 0，1，.，B d ∈ 1 mod n或B 2 r d ∈-1 mod n，s - 1，则称n是基B的强伪素数，简称spsp（B）.设t是所有前t个素基的最小强伪素数。如果我们知道的确切值，我们将有，对于整数n 10 36 ;并给出原因和数字证据的K2-和C3-spsp的12，其中' t（resp。k”t）是最小的K2-（resp. C3-）强伪素数对所有前t个素基。为此，我们描述的程序计算和枚举两种spsp的< 10 36到前9个素数基地。整个计算在Pentium IV/1.8GHz的PC上花费了大约4000小时。（回想一下，K2-spsp是如下形式的spsp：n = pq，p，q是素数，q - 1 = 2（p - 1）; C3-spsp是如下形式的spsp和卡迈克尔数：n = q1 q 2 q 3，每个素数因子q i = 3 mod 4。）
Let n > 1 be an odd composite integer. Write n - 1 = 2 s d with d odd. If either b d ≡ 1 mod n or b 2r d ≡ -1 mod n for some r = 0,1,..., s - 1, then we say that n is a strong pseudoprime to base b, or spsp(b) for short. Define ψ t to be the smallest strong pseudoprime to all the first t prime bases. If we know the exact value of ψ t , we will have, for integers n 10 36 ; and to give reasons and numerical evidence of K2- and C 3 -spsp's 12, where ψ' t (resp. ψ" t ) is the smallest K2- (resp. C 3 -) strong pseudoprime to all the first t prime bases. For this purpose we describe procedures for computing and enumerating the two kinds of spsp's < 10 36 to the first 9 prime bases. The entire calculation took about 4000 hours on a PC Pentium IV/1.8GHz. (Recall that a K2-spsp is an spsp of the form: n = pq with p, q primes and q - 1 = 2(p - 1); and that a C 3 -spsp is an spsp and a Carmichael number of the form: n = q 1 q 2 q 3 with each prime factor q i = 3 mod 4.).