# Bounds on failure probability for universal exponent method?

The following definition is from Trappe and Washington, "Introduction to Cryptography with Coding Theory". Given a number $$n$$ and an integer $$r > 0$$ such that $$a^r \equiv 1 \pmod{n}$$ for all integers $$a$$ with $$\gcd(a,n) = 1$$, the universal exponent method attempts to factor $$n$$ as follows:

• Choose a random integer $$a$$ with $$1 < a < n-1$$.
• If $$\gcd(a,n) \neq 1$$, return this gcd as a nontrivial factor.
• Otherwise, write $$r = 2^km$$ with $$m$$ odd, and compute $$b_0 \equiv a^m \pmod{n}$$. If $$b_0 \equiv 1 \pmod{n}$$, start over with a different $$a$$.
• Otherwise, repeatedly compute $$b_i \equiv {b_{i-1}}^2 \pmod{n}$$ for $$i=1, \ldots, k$$.
• If we obtain $$b_i \equiv 1 \pmod{n}$$ before obtaining any $$b_i \equiv -1 \pmod{n}$$, stop and return $$\gcd(b_{i-1} - 1, n)$$ as a nontrivial factor of $$n$$.
• Otherwise, if we obtain $$b_i \equiv -1 \pmod{n}$$ before reaching any $$b_i \equiv 1 \pmod{n}$$, start over with a different choice of $$a$$.

(As a side question, since Trappe and Washington don't give a specific citation for this method, I'd be interested in knowing if there's someone specific I should credit the method to.)

This factorization method is obviously closely related to the Miller--Rabin primality test, and in Miller--Rabin we know that if $$n$$ is composite, then there is at most a $$1/4$$ chance of a randomly chosen $$a$$ failing to prove compositeness.

Assuming again that $$n$$ is composite, is there any analogous bound for the probability of a randomly chosen $$a$$ failing to factor $$n$$ with this method? (What I'm really interested in here, I think, is the worst-case probability over all $$r > 0$$ satisfying the hypothesis.) I'm not really familiar with the tools used to prove the Miller--Rabin bound, so maybe they give an easy answer to this.