  We demonstrate that a modification of the classical index calculus algorithm
can be used to factor integers. More generally, we reduce the factoring problem
to finding an overdetermined system of multiplicative relations in any factor
base modulo $n$, where $n$ is the integer whose factorization is sought. The
algorithm has subexponential runtime $\exp(O(\sqrt{\log n \log \log n}))$ (or
$\exp(O( (\log n)^{1/3} (\log \log n)^{2/3} ))$ with the addition of a number
field sieve), but requires a rational linear algebra phase, which is more
intensive than the linear algebra phase of the classical index calculus
algorithm. The algorithm is certainly slower than the best known factoring
algorithms, but is perhaps somewhat notable for its simplicity and its
similarity to the index calculus.
