Notes on some new kinds of pseudoprimes

J. Browkin defined in his recent paper (Math. Comp. 73 (2004), pp. 1031-1037) some new kinds of pseudoprimes, called Sylow -pseudoprimes and elementary Abelian -pseudoprimes. He gave examples of strong pseudoprimes to many bases which are not Sylow -pseudoprime to two bases only, where or .

In this paper, in contrast to Browkin's examples, we give facts and examples which are unfavorable for Browkin's observation to detect compositeness of odd composite numbers. In Section 2, we tabulate and compare counts of numbers in several sets of pseudoprimes and find that most strong pseudoprimes are also Sylow -pseudoprimes to the same bases. In Section 3, we give examples of Sylow -pseudoprimes to the first several prime bases for the first several primes . We especially give an example of a strong pseudoprime to the first six prime bases, which is a Sylow -pseudoprime to the same bases for all . In Section 4, we define to be a -fold Carmichael Sylow pseudoprime, if it is a Sylow -pseudoprime to all bases prime to for all the first smallest odd prime factors of . We find and tabulate all three -fold Carmichael Sylow pseudoprimes . In Section 5, we define a positive odd composite to be a Sylow uniform pseudoprime to bases , or a Syl-upsp for short, if it is a Syl-psp for all the first small prime factors of , where is the number of distinct prime factors of . We find and tabulate all the 17 Syl-upsp's and some Syl-upsp 's . Comparisons of effectiveness of Browkin's observation with Miller tests to detect compositeness of odd composite numbers are given in Section 6.

     

The Rabin-Monier theorem for Lucas pseudoprimes

We give bounds on the number of pairs with such that a composite number is a strong Lucas pseudoprime with respect to the parameters .

     

Finding strong pseudoprimes to several bases

Define to be the smallest strong pseudoprime to all the first prime bases. If we know the exact value of , we will have, for integers , 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, are known for . Upper bounds for were given by Jaeschke.

In this paper we tabulate all strong pseudoprimes (spsp's) to the first ten prime bases which have the form 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 and are lowered from 28- and 29-decimal-digit numbers to 22-decimal-digit numbers, and a 24-decimal-digit upper bound for 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.

     

Finding strong pseudoprimes to several bases. II

Define to be the smallest strong pseudoprime to all the first prime bases. If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the are known for . Upper bounds for were first given by Jaeschke, and those for 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) to the first five or six prime bases, which have the form with odd primes and ; then we tabulate all Carmichael numbers , to the first six prime bases up to 13, which have the form with each prime factor . 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 and are lowered from 20- and 22-decimal-digit numbers to a 19-decimal-digit number:

We conjecture that

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.

     

Two kinds of strong pseudoprimes up to

Let be an odd composite integer. Write with odd. If either mod or mod for some , then we say that is a strong pseudoprime to base , or spsp() for short. Define to be the smallest strong pseudoprime to all the first prime bases. If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the are known for . Conjectured values of were given by us in our previous papers (Math. Comp. 72 (2003), 2085-2097; 74 (2005), 1009-1024).

The main purpose of this paper is to give exact values of for ; to give a lower bound of : ; and to give reasons and numerical evidence of K2- and -spsp's to support the following conjecture: for any , where (resp. ) is the smallest K2- (resp. -) strong pseudoprime to all the first prime bases. For this purpose we describe procedures for computing and enumerating the two kinds of spsp's 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: with primes and ; and that a -spsp is an spsp and a Carmichael number of the form: with each prime factor mod .)

     

Density of Carmichael numbers with three prime factors

We get an upper bound of on the number of Carmichael numbers with exactly three prime factors.

     

形如2kp+1的数的素性检验

本文初步探讨了如何快速检验一个大数n是素数(这里n-1含有大的素因子)的算法问题以及如何生成一个大素数p使得p-1有大的素因子q的算法问题.我们给出了形如n=2kp+1的数的素性检验的多项式时间算法,这里p是一个给定的大素数,k是正整数满足22k＜2kp.该算法的计算量为O(log32n).然后我们给出了生成一个大素数p使得p-1有大的素因子q的算法,其中q满足q＞(p-1)/log2(p-1).特别地,我们给出了判定并生成一个安全素数p的算法.     

Finding -strong pseudoprimes

Let be odd primes and . Put

Then we call the kernel, the triple the signature, and the height of , respectively. We call a -number if it is a Carmichael number with each prime factor . If is a -number and a strong pseudoprime to the bases for , we call a -spsp . Since -numbers have probability of error (the upper bound of that for the Rabin-Miller test), they often serve as the exact values or upper bounds of (the smallest strong pseudoprime to all the first prime bases). If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement.

In this paper, we first describe an algorithm for finding -spsp(2)'s, to a given limit, with heights bounded. There are in total -spsp's with heights . We then give an overview of the 21978 - spsp(2)'s and tabulate of them, which are -spsp's to the first prime bases up to ; three numbers are spsp's to the first 11 prime bases up to 31. No -spsp's to the first prime bases with heights were found. We conjecture that there exist no -spsp's to the first prime bases with heights and so that

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 -spsp's is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates of -spsp's and their prime factors to Miller's tests, and obtain the desired numbers. At last we speed our algorithm for finding larger -spsp's, say up to , with a given signature to more prime bases. Comparisons of effectiveness with Arnault's and our previous methods for finding -strong pseudoprimes to the first several prime bases are given.

     

On the effectiveness of a generalization of Miller’s primality theorem

Berrizbeitia and Olivieri showed in a recent paper that, for any integer r$r$, the notion of ω$\omega$-prime to base a$a$ leads to a primality test for numbers n≡1$n\equiv 1$ mod r$r$, that under the Extended Riemann Hypothesis (ERH) runs in polynomial time. They showed that the complexity of their test is at most the complexity of the Miller primality test (MPT), which is O((logn)^4+o(1))$O\left({(logn)}^{4+o\left(1\right)}\right)$. They conjectured that their test is more effective than the MPT if r$r$ is large.     

On the Applications of the Linear Recurrence Relationships to Pseudoprimes

We present here some results on the applications of linear recursive sequences of order $2$ to the Fermat pseudoprimes, Fibonacci pseudoprimes, and Dickson pseudoprimes.     

New frameworks for Montgomery's modular multiplication method

We present frameworks for fast modular multiplication based on a modification of Montgomery's original method. For (fixed) large integers, our algorithms may be significantly faster than conventional methods. Our techniques may also be extended to modular polynomial arithmetic.

     

On Assessing the Performance of Randomized Algorithms

In this paper we study randomized algorithms with random input. We adapt to such algorithms the notion of probability of a false positive which is common in epidemiological studies. The probability of a false positive takes into account both the (controlled) error of the randomization and the randomness of the input, which needs to be modeled. We illustrate our idea on two classes of problems: primality testing and fingerprinting in strings transmission. Although in both cases the randomization has low error, in the first one the probability of a false positive is very low, while in the second one it is not. We end the paper with a discussion of randomness illustrated in a textbook example.     

Some characterizations of perturbational dual problems

Continuing our papers [4] - [7], where we have given an axiomatic approach to unperturbational dual problems, we study here perturbational dual problems. we give some characterizations of various classes of perturbations and the associated marginal functions and of various classes of perturbational dual objective functions and the associated Lagrangians, regarded as functions of their natural variables and of the primal parameters     

Banach空间的某类分解

该文从Schauder分解出发，考虑了由一类具有特殊基的Banach空间Y所生成的Banach空间Y（Xi，i∈N）（特别是当每个Xi均为Y的标量域）的一些性质，以及它们之间的联系．     

Some Notes about Tanaka''''s Equation

ＳｏｍｅＮｏｔｅｓａｂｏｕｔＴａｎａｋａ＇ｓＥｑｕａｔｉｏｎＹａｎＺｈｉｂｉｎ（严质彬）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＨａｒｂｉｎＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ，１５０００１）ＡｂｓｔｒａｃｔＬｅｔ｛Ｗｔ...     

N值随机变量序列的AEP型极限及若干强偏差定理

设{X_n,n≥1}是在S={1,2,…,N}中取值的随机变量序列,其分布为p(x_1,…,x_n),liminf[P(X_1,…,X_n)]~(1/n)与limsup[p(X_1,…,X_n)]~(1/n)称为AEP型极限。利用这些极限该文得到{X_n,n≥1}的若干强偏差定理,即一类用不等式表示的强极限定理。     

强正则图的一些性质

文[3]给出了强正则图的概念及有关性质,本文在此基地上利用图的谱性质,得到了强正则图的又一些性质。     

New Fibonacci and Lucas primes

Extending previous searches for prime Fibonacci and Lucas numbers, all probable prime Fibonacci numbers have been determined for and all probable prime Lucas numbers have been determined for . A rigorous proof of primality is given for and for numbers with , , , , , , , , the prime having 3020 digits. Primitive parts and of composite numbers and have also been tested for probable primality. Actual primality has been established for many of them, including 22 with more than 1000 digits. In a Supplement to the paper, factorizations of numbers and are given for as far as they have been completed, adding information to existing factor tables covering .

     

一类随机适应序列的强收敛性

本文利用对随机变量进行截尾的方法和非负鞅的性质,证明了一类随机变量序列的强收敛性.     

Some necessary and sufficient conditions for Hypercyclicity Criterion

We give necessary and sufficient conditions for an operator on a separable Hilbert space to satisfy the hypercyclicity criterion. This paper is a part of the second author’s Doctoral thesis, written at Shiraz University under the direction of the first author.