2

So I have a question as follows

Evaluate the cube root of $2 \mod 59$

So it is my understanding that I need to find $x$, where $x^3 = 2 \mod{59}$

I have tried different values for $x$ all the way up to $30$ and I still haven't found one that satisfies the equation. Can anyone help me out? Is there an easier and more efficient method of calculate cubed roots?

dfeuer
  • 9,069
dunika
  • 433
  • My answer at http://math.stackexchange.com/a/632977/589 says how. – lhf Jan 13 '14 at 17:53
  • How is this question different from your previous one? http://math.stackexchange.com/questions/632971/modular-arithmetic-evaluate-find-square-roots – lhf Jan 13 '14 at 17:57

2 Answers2

1

Another easier way to solve this is use simple arithmetic, observing that $$120 ≡ 2 \mod 59$$ so you have just to find two cubes whose product is $120$ (you have already calculated them up to 30, right?):

$$ 2^3 = 8 \mod 59 \\ 19^3 = 6859 ≡ 15 \mod 59 $$

so the product of the roots will give your solution.

rewritten
  • 3,092
  • Okay I have another question:Evaluate the cube root of 2 mod 83.

    85 = 2 mod 83, 85 = 5 * 17

    So I get

    14^3 = 5 mod 83

    I can't find an x for which x^3 = 17 mod 83 can you help me out?

     – dunika Jan 13 '14 at 18:01
  • @rewritten, do you think this method is really universal? Is finding $\pmod{59}$ of cubes like $11,13,17,19$ really trivial? – lab bhattacharjee Jan 13 '14 at 18:08
  • I can guarantee that a solution exists (as $83≡2\mod 3$), keep trying. The point is not to find any product, but to find an easy one, like 168=8·21. – rewritten Jan 13 '14 at 18:08
  • @labbhattacharjee I don't think the method is universal, but also I don't hink the OP needs an universal method, just hints on how to look for explicit solutions. – rewritten Jan 13 '14 at 18:09
  • @rewritten I ended up with 2^3 = 8 mod 83 and 25^3 = 21 mod 83

    So what do I do now to get my answer for the question? Do I multiply 2^3 * 25^3 and then mod 83 it?

     – dunika Jan 14 '14 at 16:39
0

HINT:

As $\displaystyle2^6=64\equiv5\pmod{59},2^{12}\equiv5^2,2^{18}\equiv5^3\equiv7,$

$\displaystyle 2^{30}=2^{18}\cdot2^{12}\equiv7\cdot25\equiv175\equiv-2\pmod{59}$

As $\displaystyle(2,59)=1,$

using $\#12$ of this, $\displaystyle2^{29}\equiv-1\pmod{59}\implies 2$ is a primitive root $\pmod{59}$

Apply Discrete Logarithm to convert the problem to Linear Congruence Equation

lab bhattacharjee
  • 274,582