On the number of primality witnesses of composite integers (Q2066454)

The Miller-Rabin test tries to determine the primality of a given odd number \(n\), see [\textit{M. O. Rabin}, J. Number Theory 12, 128--138 (1980; Zbl 0426.10006)]. The test has several rounds; in each of them one takes a number \(a<n,\,(a,n)=1\)\, and it is computed if two conditions are verified (conditions (1)). If (1) holds \(n\)\, is declared probably prime (otherwise \(n\)\, is certainly composite) and \(a\)\, is called a primality witnesses for \(n\).\par Rabin proved that the error probability (the probably prime is in fact composite) in each round, what depends on the number of witnesses for \(n\), is at most \(1/4\). There are infinitely numbers \(n\)\, with this error probability, but in general the probability is lesser.\par The present paper gives estimates of the average error for a given set \(A\)\, of semiprime numbers \(n=pq,\, p<q\), numbers bounded for a certain \(X\). The paper, assuming the uniform distribution of primes in \([1, X/p]\), give estimations of the average frequency for two extreme cases of \(A: A_1=\{pq\le X;\, \gcd(p-1,q-1)=p-1\}\)\, (Theorem 1) and \(A_2=\{pq\le X;\, \gcd(p-1,q-1)=2\}\)\, (Theorem 2). These two results provide upper and lower bounds for the general case \(A=\{pq\le X\}\).\par Then the paper, keeping in mind that the assumption about the uniform distribution of primes is not really true, provides a refinement of the above results (Theorems 3 and 4).