Bad witnesses for a composite number

DOI10.4064/AA230512-17-2MaRDI QIDQ6606883zbMATH OpenFDO

Authors Johnathan Djella Legnongo, Tony Ezome, Florian Luca

Publication date 17 September 2024

Published in Acta Arithmetica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4064/AA230512-17-2

zbMATH Keywords

bad witnessesGalois testMiller-Rabin testpseudoprime test

Mathematics Subject Classification ID

Factorization; primality (11A51) Primality (11Y11)

Review text

This paper provides lower and upper bounds for the arithmetic and geometric means of the number of bad witnesses for an odd composite integer \(n\)\, with regard to a particular pseudo (or probabilistic) primality test.\N\NLet us reminder that \(x\)\, is a bad witnesses for a composite \(n\)\, if the test declare that \(n\)\, is prime. In this paper the pseudo-primality test is the product of a multiple rounds of the Miller-Rabin test by a Galois test (a pseudo-primality test based on a cyclic extension of \(\mathbb{Z}/n\mathbb{Z}\),\, see [\textit{J.-M. Couveignes} and \textit{T. Ezome}, Rend. Circ. Mat. Palermo (2) 61, No. 2, 261--278 (2012; Zbl 1257.11106)]. As the authors point out the Miller-Rabin test is more efficient when \(n\)\, has many prime divisors while the Galois test is more efficient when \(n\)\, has few prime divisors.\N\NThe obtained results are synthesizes in Section 1, Theorem 1.1 (for the arithmetic mean) and Theorem 1.2 (for the geometric mean). These theorems are proven in the rest of the paper.\N\NSection 2 deals with the Galois test; 2.1 determines bounds for below and for above for the arithmetic mean of the number of bad witnesses of this test (Theorems 2.2 and 2.3) and subsection 2.3 studies the geometric mean (Theorem 2.4). \N\NFinally Section 3 proves the lower and upper bounds for the arithmetic and geometric mean in the case of the product test, see Theorem 3.1 and Theorem 3.2.

Recommendations

• A faster pseudo-primality test
• On the number of primality witnesses of composite integers
• On the Number of False Witnesses for a Composite Number
• scientific article; zbMATH DE number 721898
• Improved error bounds for the Fermat primality test on random inputs

Cites work

• A faster pseudo-primality test
• Average liar count for degree-2 Frobenius pseudoprimes
• Elliptic periods and primality proving
• Four primality testing algorithms
• Frobenius pseudoprimes
• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 3141365 (Why is no real title available?)
• scientific article; zbMATH DE number 3943948 (Why is no real title available?)
• scientific article; zbMATH DE number 799757 (Why is no real title available?)
• scientific article; zbMATH DE number 6308078 (Why is no real title available?)
• Lucas Pseudoprimes
• On the normal number of prime factors of \(p - 1\) and some related problems concerning Euler's \(\varphi\)-function.
• On the Number of False Witnesses for a Composite Number
• Popular values of Euler's function
• Probabilistic algorithm for testing primality
• Riemann's hypothesis and tests for primality
• Shifted primes without large prime factors
• Strengthening the Baillie-PSW primality test
• There are infinitely many Carmichael numbers
• Некоторые критерии простоты чисел, связанные с малой теоремой Ферма

Cited in

(1)

• Novel performant primality test on a Pell's cubic

This page was built for publication: Bad witnesses for a composite number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6606883)