1

As I understand it the discrete logarithm problem is about identifying $x$ given $a^x \equiv b \ mod \ p$ and $a,b,p$.

While researching this I have become interested in the inverted problem, i.e. identifying $y$ given $y^a \equiv b \ mod \ p$ and $a,b,p$; e.g. $y^4 \equiv 7 \ mod \ 23$.

I believe this is simpler but am not clear on how to solve it. Any clarification or explanation would be appreciated.

gautam
  • 183
  • 1
    There is a vast difference between the two problems: in the discrete logarithm problem, there is always an $a$ and an $x$ given $b$ that can satisfy the congruence. This is because a primitive root exists in $\mathbb{F}_p$. Therefore, the problem is "only" to compute $x$ (given a primitive root $a$, say). The problem you are posing has an extra dimension: you are not guaranteed that a solution $y$ exists given $b$ and $a$. For instance, how do you know $7$ is a fourth root mod 23? Can you generalize? Generalizing this leads to higher reciprocity laws and class field theory. – guest Jan 09 '16 at 20:30
  • For 'fourth root' above of course substitute 'fourth power', or 'has a fourth root'. – guest Jan 09 '16 at 20:50
  • Thanks. I understand that equations like this might not always have a solution. I am interested in being able to determine whether they have a solution or not and if they do how to get the solution. – gautam Jan 09 '16 at 21:52
  • Well, that's the problem: determining whether your equation has a solution or not involves all the classical class field theory, and algorithmically doing so is an active research area. The most readable introduction I have is the book Numbers of the form $x^2+ny^2$ by David Cox. – guest Jan 09 '16 at 21:54
  • If you google 'higher reciprocity laws' you can get further references, but they require a heavy background on algebraic and analytic number theory. – guest Jan 09 '16 at 21:56

0 Answers0