0
$\begingroup$

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)

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Also,if $e$ is coprime to $\varphi(n),$ then we can compute $m = 1÷e$ (mod $\varphi(n)$).

And so for every $a$ coprime to $n,$ we get $$(a^m)^e = a.$$

I.e. $a^m$ is the $e^{th}$ root of $a.$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.