Estimating the Distribution of Witnesses of the Primality of the Miller-Rabin Test

Alisher Zhumaniezov, Kazan Federal University, Russian Federation


This article investigates the error distribution of the Miller-Rabin test for the class of tripleprime numbers. At first the current results on the class of semiprimes are presented. Further, a theoretical estimation of the average frequency for triple prime numbers on an interval is derived, and a comparative analysis with a practical result is demonstrated. Graphs and intermediate conclusions accompany all comparisons. A conclusion is also made about a possible direction for improving this estimation.


Miller-Rabin test, strong pseudoprime, number theory, frequency distribution.