Why would this method of discrete logarithm finding not work?

Question

Say we do know $b$ but not $k$, and are given $g$ such that $g\equiv b^k\pmod p$. And say there exist factors $E = e + m'p$ ($e \equiv b^i \bmod p$) and $F = f + m''p$ ($f \equiv b^j \bmod p$) of $g$. Then $EF = g + pm = b^k$ for some $m$, $m'$ and $m''$.

So if we can find the right $(m, m')$ we can factor $G = g+pm = EF$. Then $E$ is congruent modulo $p$ to a power of $b$, and so is $F$. But note that $E$ and $F$ may not be perfect powers of $b$.

So we generate values of $E$ that are perfect powers of $b$, and then see if we can factor a member of the congruence class of $g$ mod $p$ — i.e. are any members of the congruence class of $g$ mod $p$ multiples of $E$? We can use the Extended Euclidean algorithm for this if $g$ is $\pm1$. Maybe we could also use the EEA for this if $g$ is any number $d$, by reducing the $g+pm$ and $E$ by the multiplicative inverse of $g$ mod $p$ (which we can find).

So if we can find a solution in $F$ to : $g \equiv b^i F\bmod p$ then we can reduce the problem to finding the exponent (to base $b$) of $F$ mod $p$. So then shouldn't we be able to find a sequence of exponents of our perfect power (the $E$s, the exponents being the $i$s) = until $F = 1$. At that time the sum of those exponents will be congruent (mod $p$) to the exponent of $g$.

It is on this basis that I claim that factoring is equivalent to the discrete log problem.

Is this hopelessly confused, or is there something here?

Answer 1

The flaw in your reasoning lies in your assumption that finding the discrete log of $f$ is any easier than finding the discrete log of $g$. It just isn't. That assumption is not correct. And if you try to recurse and apply your procedure to $f$, you'll recurse for a very long time, and your algorithm will take exponentially long.

Let me summarize your algorithm: to find the discrete log of $g$, you suggest we pick some specific power of $b$, say $e \equiv b^3 \pmod p$, then compute $f \equiv g/e \equiv g b^{-3} \pmod p$, then somehow magically find the discrete log of $f$. The problem with this algorithm is that "magic" doesn't exist. If you want to find the discrete log of $f$, that's every bit as hard as finding the discrete log of $g$. So the "factoring" hasn't helped you one bit.

I imagine you're going to be tempted to respond "but I just recurse, and apply my method recursively to $f$!", so let me proactively explain why that ain't gonna work: first, you have not identified any base case, so your recursion never terminates; and second, if you identify a reasonable base case (e.g., if $g$ is a perfect power of $b$, stop immediately), you'll find that you will need to recurse an exponential number of times, so the running time of your algorithm will be worse than brute-force search.

There is no known reduction that proves that the discrete log is as easy as factoring. Lots of people have tried to find one, and failed.

Answer 2

Before you edited it, both $b$ and $k$ were unknowns. Now $k$ is known and the challenge is to find $b$. Assuming $p$ is prime, and that $gcd(k,p-1)=1$ this can be done by raising $g$ to the power of the inverse of $k \mod p-1$. This is the same as RSA decryption where the modulus is prime and similar to decrypting where the factorization of the composite modulus is known.

However in the third paragraph of your question, you talk about generating values which are powers of $b$ which is tricky if $b$ is unknown. Similarly, the fourth paragraph only makes sense if the whole problem is that $b$ is known and we're trying to find $k$.

Assuming this is your real intent then your method makes more sense and runs along similar lines to the existing best methods for calculating discrete logs in $F_p$.

One problem is that your method for generating $E$ will generally result in numbers which are not significantly smaller than p. No matter how many $E$ values you generate, for problems of interest, the chance that you will find a power of b that is a non-trivial multiple of any E is negligible.

This is with a charitable interpretation of your idea. From what I understand of paragraph 4, your handling of $F$ smacks of some sort of recursive application of your algorithm and if this is the case then I'm confident that it will perform much worse than exhaustive search.

My advice, get hold of GP/Pari (it runs on Unix and Windows) and see if you can implement an algorithm that outperforms a simple search.