3
$\begingroup$

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.

$\endgroup$

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.