Finding 𝐢₃-strong pseudoprimes (Q4654036)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 2140106
Language Label Description Also known as
default for all languages
No label defined
    English
    Finding 𝐢₃-strong pseudoprimes
    scientific article; zbMATH DE number 2140106

      Statements

      Finding 𝐢₃-strong pseudoprimes (English)
      0 references
      0 references
      1 March 2005
      0 references
      Carmichael numbers
      0 references
      \(C_3\)-numbers
      0 references
      strong pseudoprimes
      0 references
      Rabin-Miller test
      0 references
      The author, continuing previous researches, gives an algorithm to find \(C_3\)-strong pseudoprimes and conjectures the exact value of \(\psi_{12}\). The knowledge of \(\psi_m\)\, (the smallest strong pseudoprime to the first \(m\) prime bases) is interesting since it would provide an easy deterministic primality test for all natural numbers \(n< \psi_m\) (applying Miller-Rabin's test to those \(m\) bases). A \(C_3\)-number \(N\) is a Carmichael number \(N=q_1q_2q_3\), product of three prime numbers \(q_i\), \(q_i\equiv 3 \bmod 4\). Section 2 of the paper describes an algorithm to find \(C_3\)-strong peudoprimes to the base \(2\) and Section 3 discusses the numerical results found in an implementation of the algorithm. In particular the author shows that there are \(21973\) \(C_3\)-strong pseudoprimes \(N\)\, to the base 2, with \(N<10^{24}\)\, and with height \(H(N)<10^9\)\, (the height of \(N=q_1q_2q_3\)\, is defined as \(H=h_1h_2h_3\), where \(h_i=\frac{q_i -1}{d}\) and \(d=gcd(q_1-1, q_2-1, q_3-1)\). None of these \(21973\) \(C_3\)-strong pseudoprimes is strong pseudoprime to the first 12 first prime bases and the author conjectures that \(\psi_{12}= N_{12}\), where \(N_{12}\)\, is a number of 24 digits, product of two primes, which was found to be an upper bound for \(\psi_{12}\) in a previous paper of the author [Math. Comput. 70, 863--872 (2001; Zbl 1007.11003)]. Section 5 of the paper gives reasons and numerical evidence to support the mentioned Conjecture: \(\psi_{12}= N_{12}\).
      0 references

      Identifiers