# Does knowing modular eth roots help in factoring n?

Consider $$x^e \equiv a\pmod n$$, given $$n$$, $$a$$, and $$e>2$$, with $$n$$ being a composite integer and unknown $$x$$.

Can a hypothetical function $$f(a)=x$$, an $$eth$$ root extractor, be used / adapted to factor $$n$$, in the same way that the multiplicative order of $$x \space modulo\space n$$ can be used to factor $$n$$ like in the classical part of Shor's algorithm?

The RSA problem, which you describe, is not known to be equivalent to factoring and there is evidence both ways. In [BV] it is shown that this barrier might be inherent: using a black-box separation technique called meta-reductions, they show that certain restricted class of reductions are not possible. On the other hand, it was shown later in [AM] that in the generic ring model (see [JS]), these problems are equivalent. That is, any speed-up in breaking RSA has to exploit the representation of $$\mathbb{Z}_N^*$$.