Constructing Carmichael numbers which are strong pseudoprimes to several bases (Q1911938): Difference between revisions

Let \(b\) be an integer, \(n\) a prime number such that \(\text{gcd} (n,2b)=1\) and define \(k,q\) by \(n-1=2^kq\), \(q\) odd. By Fermat's little theorem one of the following conditions is satisfied: (1) \(b^q\equiv 1\bmod n\); (2) there exists an integer \(i\), \(0\leq i\leq k\), such that \(b^{2^iq}\equiv -1\bmod n\). A composite number satisfying this property is called a strong pseudoprime to the base \(b\) \((\text{spsp}(b))\). It is well known that the Rabin-Miller primality test checks the conditions (1) and (2) for several bases \(b\). The author describes a method of constructing spsp's being the product of three or more primes which pass the Rabin-Miller test in packages like Axiom 1.1 or Maple V.2. He uses a similar method to construct composite numbers which are found to be prime by the strong Lucas test. Further, he derives sufficient conditions for a Carmichael number to be an \(\text{spsp}(b)\) for several bases \(b\). Numerous examples are given.