For those of you that don't know, the modular/discrete logarithm problem:
Calculate b given the others: $a^b≡c$ mod d
I am aware that there is no general algorithm for the discrete logarithm, making it intractable. ($O(n^2)$ and worse for n digits is generally considered intractable, though exponential is for sure)
Even though it isn't standard, for simplicity I'll label time complexities here with the first letter:
- $M(n)$ for multiplication
- $D(n)$ for division
- $E(n)$ for exponentiation
I have two conditions to work with:
- d is a power of 2, so $d=2^n$ for some known n (this is convenient because modulo, which is $D(n)$, can be replaced by bitwise AND, which is $O(n)$)
- a and c are odd, if not primes, which they probably will be (this could be inferred, since a has to be odd to generate all other odd values, of which c is one)
Naive brute force search would then be $O(2^nE(n))$. The best any algorithm (that I've heard of) does is subexponential - still not polynomial, which is what I'm aiming for.
I have algorithms for some of the other (non-trivial) ones, namely:
(Modular) Division
- $D(n)=O(n^2)$ or so
- Tested with 65536-bit numbers (Python, took a few seconds)
(Modular) Exponentiation
- $E(n)=O(M(n)n)$, in my case, $M(n)=O(n^2)$ so $E(n)=O(n^3)$
- Tested with 16384-bit numbers (Python, took a few seconds)
Discrete logarithm has me stumped. Since modulus power of 2 allows usage of various bit twiddling hacks and other shortcuts that normally would never work, I think it can be done in polynomial time for this case. No idea how though.
\log
for $\log$. $\endgroup$