# 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<u\le\lceil\log_2N\rceil$, 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 believed 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