Abstract :
Some of the witnesses (a mod n) for an odd composite integer n > 1, in the probabilistic primality test of Miller and Rabin, provide a non-trivial divisor of n of the form gcd(a2kn′ − 1, n), where n − 1 = 2ν2(n − 1)n′ and 0 ≤ k ≤ ν2(n − 1). Considered here are extreme values of both the number of such withnesses for n and the ratio between this number and the total number of witnesses for n.
