5 of 5
deleted 9 characters in body
curious
  • 5.6k
  • 5
  • 27
  • 42

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$?

curious
  • 5.6k
  • 5
  • 27
  • 42