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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.