Simultaneous equations with discrete log problem

Question

I know discrete log problem is a hard problem with one, lets say $m^{23} \mod 320 \equiv 300$

But would it be easy and possible to solve, lets say $m^{23} \mod 320 \equiv 300$ and $m^{31} \mod 320 \equiv 261$

How does one go about solving it? If it is not possible, why not?

Answer 1

It is unsolvable: $\ {\rm mod}\ 2\!:\ x^n\equiv x\,\Rightarrow\, m\equiv m^{23}\equiv300\equiv\color{#c00} 0\ $ contra $\ m\equiv m^{31}\equiv 261\equiv\color{#c00} 1 $

---

If instead the modulus is coprime to $\color{#0a0}{300}$ or $\color{#c00}{261}$ you could then argue either

$\,\qquad 31(3)-23(4)\, = \,1\ $ so $\ m \equiv (m^{\large 31})^{\large 3} \ \, (m^{\large 23})^{\large -4}\, \equiv\, 261^{\large 3}\ \color{#0a0}{300^{\large -4}}\equiv\ \ldots$

or $\,\ 23(27)-31(20) = 1\ $ so $\ m \equiv (m^{\large 23})^{\large 27} (m^{\large 31})^{\large -20} \equiv 300^{\large 27} \color{#c00}{261^{\large -20}}\equiv\ \ldots$

and then verify if the computed value is indeed a solution.

Answer 2

This system has no solution.

Given, $m^{23} \equiv 300 (\mod 320)$ and $m^{31} \equiv 261 (\mod 320)$.

Now, $m^{31} \equiv 261 (\mod 320)$

$\implies m^{23+8} \equiv 261 (\mod 320)$

$\implies m^{23} \times m^8 \equiv 261 (\mod 320)$

$\implies 300m^{8} \equiv 261 (\mod 320)$

$\implies 300m^{8} -320k=261$, for some integer $k$.

But this is not possible. Because the LHS of the equation is divisible by $10$, but the RHS isn't.