Score:0

Computing the eth root in Z(N)* i.e set of all elements coprime to N

tt flag

I understand that it is easy to compute eth root in Z(P)* but what about with Z(N)? I know that it requires the factorization of N but what does that actually mean? What is an example of calculating the eth root in the set Z(N) (the set of all elements coprime to N)

Score:2
my flag

I know that it requires the factorization of N but what does that actually mean?

I means pretty much what it say on the tin - we don't know a way of efficiently computing the $e$-th root of a value $x$ modulo a value $N$ without the full factorization of $N$ (and a partial factorization of $N$, such as $N = p \cdot q \cdot c.$ where $c$ is a large composite, doesn't help). That is, we don't know a practical way of finding $y$ s.t. $y^e \equiv x \pmod N$.

In fact, this problem is known as the RSA problem; that is, if you can solve it, you've broken RSA.

What is an example of calculating the eth root in the set Z(N) (the set of all elements coprime to N)

If you do know the factorization of $N = p_1^{e_1} p_2^{e_2} ... p_n^{e_n}$ where $p_1, p_2, ..., p_n$ are prime, then it is easy:

For each $p_i^{e_i}$, solve the problem $y_i^e \equiv x \pmod {p_i^{e_i}}$ (and if there is an $i$ where there isn't a solution, there's no solution for the overall problem). You already know how to solve it for $e_i=1$; solving it for $e_i > 1$ isn't that much more difficult.

Once you have all the $y_i$ values, use the Chinese Remainder Theorem to combine them into a $y$ value - that's your solution.

I sit in a Tesla and translated this thread with Ai:

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.