Score:1

Which of the following is considered cryptographically hard/easy?

sa flag

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

kelalaka avatar
in flag
[case 1 is conjectured to be hard](https://crypto.stackexchange.com/a/70600/18298) and the hint of the second case was [here](https://crypto.stackexchange.com/q/60708/18298) and more [here](https://math.stackexchange.com/q/673418/338051)
Maarten Bodewes avatar
in flag
Thank you for keeping to our [homework policy](https://crypto.meta.stackexchange.com/search?q=homework) 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).
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.