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
1 March 2005
0 references
Carmichael numbers
0 references
\(C_3\)-numbers
0 references
strong pseudoprimes
0 references
Rabin-Miller test
0 references
0.81551397
0 references
0.7587035
0 references
0.7586392
0 references
0.74124163
0 references
0.71714073
0 references
0.71681833
0 references
0 references
0.68587255
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