Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
BTW did you check Henri Cohen's book Computational Algebraic Number Theory to see if such case is there? –  user2468 Apr 13 '12 at 1:56
    
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. –  Henning Makholm Apr 13 '12 at 22:22

2 Answers 2

If $\gcd(a,n)=g>1$ then if $g\nmid b$ there's clearly no solution. Otherwise write $a=g\alpha$, $b=g\beta$, $n=g\nu$, so $$ a^x\equiv b\pmod{n} \iff g^{x-1}\alpha^x\equiv \beta \pmod{\nu} $$ Since $\gcd(\alpha,\nu)=1$, $\alpha$ has an inverse mod $\nu$. Divide through by $\alpha$ to get $$(g\alpha)^{x-1} = a^{x-1} \equiv \beta\alpha^{-1} \pmod{\nu}$$ If $\gcd(a,\nu)=1$ then you can use your preferred algorithm for the relatively prime case, otherwise repeat this reduction.

Example 1: $6^x \equiv 4 \pmod{44}$

Using $3\cdot 15 \equiv 1 \pmod{22}$ and $3\cdot 4 \equiv 1 \pmod{11}$: $$ \begin{align} 2^{x-1}3^x & \equiv 2 \pmod{22} \\ 6^{x-1} & \equiv 2\cdot 15 \equiv 8 \pmod{22} \\ 2^{x-2}3^{x-1} & \equiv 4 \pmod{11} \\ 6^{x-2} & \equiv 4\cdot4 \equiv 5 \pmod{11} \\ \end{align} $$ Now $\gcd(6,11)=1$, so if you can solve this you might get $x-2=6$, $x=8$.

Example 2: $6^x \equiv 2 \pmod{44}$

Starting as in Example 1: $$ \begin{align} 2^{x-1}3^x & \equiv 1 \pmod{22} \\ 6^{x-1} & \equiv 2\cdot 15 \equiv 15 \pmod{22} \\ \end{align} $$ and this has no solution since $\gcd(6,22) \nmid 15$.

share|improve this answer

This is very incomplete.

Since there are only a finite number of elements, eventually the sequence {ak mod n}k$\ge$0 must become cyclic. So there are natural numbers $\sigma$ and $\lambda$ such that a$\sigma$ + v$\lambda$ = a$\sigma$ for all v.

So there are exactly two elements where you can't calculate the element that came before it like you can in a cyclic group. The first is obviously 1 itself, the second is the first element of the cyclic part which is equal to both a$\sigma$-1a and a$\sigma$+$\lambda$-1a.

The problem is I think $\sigma$ can approach n so we'd spend all our time moving along the tail.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.