Unknown Exponent In Modular Equation

Question

If $(9^{4})^{x} \equiv 12 \pmod{23}$, then how do I find $x$?

I have tried solving this, but I was thinking if there is a step by step formula. I know that any number from the group order may suffice.

Will I still be able to find $x$ when the numbers involved are huge, such as, a large prime instead of $23$ and a large number instead of $4$?

This is a difficult problem in general. Look up discrete logarithm. A lot of cryptography is predicated on this problem continuing to be difficult. — Callus - Reinstate Monica, Aug 19 '18 at 02:49

score 0 · Answer 1 · answered Aug 19 '18 at 02:44

0

$$3^{8x-1}\equiv4\pmod{23}\equiv3^3$$

$$\iff3^{8x-4}\equiv1$$

$3^2\not\equiv1,3^3\equiv4,3^{11}\equiv9(4^3)\equiv1$

$$\implies8x-4\equiv0\pmod{11}$$

answered Aug 19 '18 at 02:44

lab bhattacharjee

1 Answers1