# Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?

Suppose that we are given $\mathbb{Z}_{N}$ and an element $x^u \in \mathbb{Z}_{N}$ with $u \in (0,l]$ where $l$ is the bit-size of $N$. Is it difficult to recover $x$ by knowing $u$ without knowing the factorization of $N$?

Yes, the problem of finding unknown random $$x\in\mathbb Z_N$$ given $$N\in\mathbb N$$, $$u\in\mathbb N$$ with $$1, and $$x^u$$ computed in $$\mathbb Z_N$$, is believed hard unless the factorization of $$N$$ can be determined, which itself is believed hard for appropriately constructed RSA moduli $$N$$. Moreover, depending on $$u$$ and $$N$$, there might be several solutions with no way to tell the right one (if $$u$$ is odd and $$N$$ squarefree with no divisor up to $$\lceil\log_2N\rceil$$ then there is a single solution). Notice that I have excluded $$u=1$$ (which the question allows), for it makes finding $$x$$ trivial.

When $$u$$ is odd this is the RSA problem with small exponent, which is believed hard when the factorization of $$N$$ can't be determined (with the caveat that a usual definition of that problem asks that $$N$$ is squarefree and without small divisors).

When $$u$$ is $$2$$, this is the square root modulo unknown composite problem, which is demonstrably hard when the factorization of $$N$$ can't be determined.

Ability to consistently solve both that square root problem and the RSA problem implies ability to find a solution to the question's problem, by writing $$u$$ as $$e\cdot2^s$$ with odd $$e$$, solving the RSA problem for exponent $$e$$, and solving the square root problem $$s$$ times.

Addition: this answer is for version 5 of the question. As correctly noted in another answer for an earlier version of the question, knowing that $$N$$ is a square does not make the problem easier if the factorization of $$N$$ remains unknown.

• It is easy to find the inverse of any given element of $$\mathbb Z_N$$ when its exists, using the Extended Euclidian algorithm.
• It is hard to exhibit $$a\in\mathbb Z_N$$ that has no inverse modulo $$N$$, other than $$0$$ or a multiple of an easily found factor of $$N$$ (argument: if such an $$a$$ was found, then $$\gcd(a,N)$$ would be a non-trivial divisor of $$N$$ contributing towards finding the full factorization of $$N$$).
• If $$\gcd(u,N)=1$$ (which we'll assume hereafter), it is thus easy to find non-negative integers $$v$$ and $$k$$ with $$u\cdot v=k\cdot N+1$$, otherwise said with $$v\equiv u^{-1}\pmod N$$.
• It does follow that $$\forall x\in\mathbb Z_N$$, $$(x^u)^v=x^{k\cdot N+1}=(x^N)^k\cdot x$$.
• That does not seem to help finding $$x$$, because we have nothing telling us that $$x^N=1$$; on the contrary, $$x^N=1$$ seldom holds when $$x\ne 1$$; in particular $$x^N=1$$ holds only for $$x=1$$ when $$N$$ is prime, since in this case: $$\forall x\in\mathbb Z_N$$, $$x^N=x$$ by Fermat's little theorem.
• Does this imply that finding inverses mod $N=pq$ is also hard as long you don't know the factorization of $N$ – curious Apr 1 '15 at 8:05
• @curious Not at all. Multiplicative inverses can easily be found using the extended Euclidean algorithm. – Aleph Apr 1 '15 at 8:09
• @Aleph Then why finding $x \mod N$ from $x^u \mod N$ is difficult? You compute $v=u^{-1}$ and then $x= (x^{u})^v=x^{uu^{-1}} \mod N$ – curious Apr 1 '15 at 8:54
• @curious Because $v \equiv u^{-1} \pmod {\varphi(N)}$, if $v, u$ and $\varphi(N)$ are coprime. Given $N$, it is assumed that $\varphi(N)$ cannot be found easily (this would be equivalent to factoring $N$). – Aleph Apr 1 '15 at 10:35
• @curious The inverse you want (need) is modulo $\varphi(N)$, the one modulo $N$ has no relation with the one you want. They are completely different things. – Thomas Apr 1 '15 at 11:26

I'm not sure if this is what you meant, but computing arbitrary roots modulo a composite number IS the RSA-problem, which is considered hard.
I'm pretty sure that squaring the modulus won't make a difference in the hardness, as you still don't know the prime-factors, but don't think that it's "more" secure than with normal N, and it will certainly be slower due to the larger modulus.

• RSA problem states that it is difficult to compute multiplicative inverses moduli $\phi(N)$ – curious Mar 31 '15 at 12:40
• @curious, cited from Handbook of Applied Cryptography, page 98 chapter 3.3: "Definition the RSA problem (RSAP) is the following: given a positive integer n that is a product of two distinct odd primes p and q, a positive integer e such that gcd(e,(p-1)(q-1))=1, and an integer c, find an integer m such that m^e=c (mod n). In other words, the RSA problem is that of finding e-th roots modulo a composite integer n." – SEJPM Mar 31 '15 at 13:06
• The solution to the RSA problem as you said is the inverse of $e$ moduli $\phi(N)=(p-1)(q-1)$. And it is believed that if the factorization $(p,q)$ is not known you cannot find the inverse. – curious Mar 31 '15 at 14:00
• @curious Knowing the inverse is equivalent to knowing the factorization, since if you know $u$ and $u^{-1}$ modulo $\varphi(n)$ (or $\varphi(n^2)$) then the latter divides $u u^{-1} - 1$ and you are done. – Thomas Mar 31 '15 at 14:13
• Yes but my concern is that i want the inverse not moduli $\phi(N^2)$ but $(N^2)$ – curious Mar 31 '15 at 14:16