0
$\begingroup$

The general discrete logarithm problem is to find $x$ given $a, b$ and $n$ such that $$a^x \equiv b\pmod{n}.$$ Normally one can use the "baby-steps giant-steps" algorithm to solve it fairly quickly. But when $\gcd(a,n) \neq 1,$ it is not possible to compute $a^{-1}\pmod{n},$ which the algorithm requires.

What algorithms are available to solve this problem in this case (apart from brute force of course)? Are there any theoretical limits on how fast such an algorithm could run?

  • 0
    BTW did you check Henri Cohen's book *Computational Algebraic Number Theory* to see if such case is there?2012-04-13
  • 0
    If you have a "fairly quick" way to compute discrete logarithms in the $a$, $n$ coprime case, you should be out there making a name for yourself demolishing cryptographic algorithms.2012-04-13

2 Answers 2