Which of the following are easy, if any? Which are hard? and why.

Case 1) Given $x^3 \bmod N$, where $N$ is a composite number and we don't know any of the factors of $N$, find $x$.

Case 2) Given $x^3 \bmod p$, where $p$ is prime, find $x$.

Here is what I think but I don't fully understand it.

For case 1, this is assumed to be hard? In the RSA assumption, where $e = 3$, imagine $N$ being a large product of 2 primes. If we don't have any of the factors, can we say that this is hard? What other reasons can we say that this is hard? (or is this actually easy?)

For case 2, we assume to know all the factors of $p$, which apparently means this is cryptographically easy? We know that the number of elements (order) in $\mathbb{Z}_p^*$ is $p-1$. Does this mean that $3$ has an inverse $\bmod p - 1$? Using this fact, how can we recover $x$ given $x^3$?

  • 2
    $\begingroup$ case 1 is conjectured to be hard and the hint of the second case was here and more here $\endgroup$
    – kelalaka
    Dec 9 '21 at 10:04
  • 2
    $\begingroup$ Thank you for keeping to our homework policy Diego. Note that homework related questions may still be closed e.g. if similar questions have been asked before. Don't forget to upvote helpful answers in the links (you should be able to upvote from 15 rep onwards). $\endgroup$
    – Maarten Bodewes
    Dec 9 '21 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.