Question

Suppose 2 is a primitive root of 29. Find all solutions to 4x^12 = -23 mod 29

Answer 1

I've reduced it down (barely) to
2x^12 = 3 mod 29

But I'm not sure how to proceed without basically recreating an entire indice table.

Answer 2

can you explain primitive root

Answer 3

There is some k such that
2^k is congruent to j for all j relatively prime to 29.

Answer 4

take discrete logarithm both sides and isolate x

Answer 5

So if I have like ind2(3) mod 28

How would I even solve that?

Answer 6

\[2x^{12}\equiv 3\pmod{29}~~~ \iff~~~ \text{ind}_2(2x^{12})\equiv \text{ind}_2(3) \pmod{28}\]

Answer 7

I'd have 2^k = 3 mod 28 for some k, but I wouldn't know how to find that k without guessing and checking/ without a table?

Answer 8

you don't need a table to compute \(\text{ind}_2(2)\) because \(\text{ind}_b b=1\)

Answer 9

Right that makes sense

Answer 10

use logarithm properties and break it down as much as possible first

Answer 11

I'm not following. What logarithm properties should I be considering?

Answer 12

\[\text{ind}(mn) = \text{ind}(m) + \text{ind}(n)\]

and

\[\text{ind}(m^n) = n*\text{ind}(m) \]

Answer 13

Right so I'd have something like

1+12ind2(x) = ind2(3) mod 28

I don't know how to deal with the right side though

Answer 14

looks good, next you need to find \(\text{ind}_2(3)\)

Answer 15

you need to work it, there is no other way :

2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32 = 3

so the index of 3 is 5

Answer 16

i mean to say there is no other way, you need to try the exponents till you get what you want

Answer 17

Oh okay then. Fair enough

Answer 18

rest should be easy

Answer 19

1+12ind2(x) = ind2(3) mod 28

1+12ind2(x) = 5 mod 28

12ind2(x) =4 mod 28

3ind2(x) =1 mod 7

ind2(x) = 5 mod 7

Answer 20

so we get
\[\text{ind}_2(x) = 5, 12, 19, 26\]

Answer 21

consequently the solutions would be
\[x \equiv 2^5,~2^{12},~2^{19},~2^{26}\pmod{29}\]

Answer 22

Right, that all makes sense. Thank you so much for everything you've done today. You've been absolutely phenomenal

Answer 23

yeah that keeps me going for trying ur next problem ;p
yw :)

Answer 24

Haha gotta sweet talk ya' to make sure you do all the problems. You've figured me out.

But for real though, you've been amazing thank you.