| Primality testing is one of two closely related classical problems in computational number theory, the other being that of factoring integers. Jacobi-Sum primality testing algorithm and Elliptic Curve Primality Proving (ECPP) algorithm are almost polynomial time deterministic primality proving algorithms. In August 2002, M. Agrawal, N. Kayal and N. Saxena presented a deterministic primality proof algorithm in polynomial time, this was a theoretical breakthrough, but as pointed out by Gunter M. Ziegler that, "it is not yet suitable for use in practice". Rabin-Miller test and the Baillie-PSW probable prime test are primality tests the most used in practice. But no precise result is known about the probability of error of the Baillie-PSW probable prime test. Zhang [Mathematics of Computation, 71 (2002), 1699-1734. MR 2003f:11191] first gave definitions of one-parameter quadratic-base pseudoprimes and strong pseudoprimes. Let u be an integer greater than 2. Put Tu = T (mod T2 — uT + 1). Then for any prime n with gcd(u2 — 4, n) = 1, Tun-ε = 1 (mod n), where e is the Jacobi symbol of u2 — 4 to n. If n is composite such that the above congruence holds, then we call n a pseudoprime to the base Tu, or psp(Tu) for short. Then Zhang proposed a one-parameter quadratic-base version of the Baillie-PSW probable prime test, or One-Parameter Quadratic-Base Test (OPQBT) for short and gave formulas for computing its probability of error.In this paper, we discuss some properties of one parameter quadratic-base pseudo-primes not mentioned in Zhang's paper. At first, we show that there are infinitely many psp(Tu)'s for any given u > 2. Then, we discuss the order and structure of the group of units of the semigroup (Z[Tu]/(n), ·, 1), and give a necessary and sufficient condition for that the product of two bases Ta · Tb, is congruent to a third base Tc modulo n. At last, we describe a procedure for finding all psp(T3) 's up to 108. There are in total 1460 such numbers. We give an overview of them.
|
PDF Full Text Request