1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ case 1 is conjectured to be hard and the hint of the second case was here and more here $\endgroup$
    – kelalaka
    Commented Dec 9, 2021 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 ♦
    Commented Dec 9, 2021 at 11:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.