# Solve DLOG using a probabilistic algorithm for DLOG lsb

Following the question Can I know from a Bitcoin public key if the private key is odd or even?

The answer there gives a simple algorithm for solving the Discrete Logarithm Problem when given an oracle which gives the LSB of the DLOG. The answer hints this may be possible but not so easy with a probabilistic solution. So naturally I want to follow up with the harder question.

I can think of two such probabilistic setups (Which might be two different questions really, but I think it reasonable to ask both here):

• Given an algorithm/Oracle which with some non negligible probability p finds the LSB, and with probability (1-p) returns failure.

• Given an algorithm/Oracle which always returns some bit which with some probability p>0.5 is the LSB

It seems to me, neither should be sufficient without some assumption on the independence of this, If the algorithm actually consistently succeeds only on certain types of inputs it might be hard to leverage to a general solution, but I may be off here.

Really since my question is curiosity driven and not from a specific need, it's rather broad: Which types of probabilistic solutions to find the LSB of the DLOG will lead to solving the DLOG problem.

Consider a type 1 algorithm oracle where the probability of success is, say, about 1 in a million. Given a discrete logarithm problem $$y=g^x$$ (given $$y$$ find $$0\le x<\ell$$) we can make an assumption on, say, the bottom 4 bits of $$x$$ by repeating 16 times. This will make our problem equivalent to solving $$y'=g^{[x/16]}$$ and the bits of $$[x/16]$$ are the bits of $$x$$ shifted down by 4. As usual we recover the discrete logarithm bitwise and shift. To recover the low bit of $$[x/16]$$ we choose a few million random $$r$$ in the range $$[0,\ell-\ell/16]$$ and run our algorithm on $$y'g^r$$ (which has discrete logarithm $$0\le [x/16]+r<\ell$$. We expect to succeed at least once and the low bit of $$[x/16]$$ will be the bit returned by our algorithm XOR with the least significant bit of $$r$$. Rinse; repeat.
Likewise for a type 2 algorithm with probability, say, 0.501 we construct the same $$y'$$ and again sample, say 100 million $$r$$. We get 100 million predictions for the least significant bit of $$[x/16]$$ of which about 50,100,000 are correct and about 49,900,000 are incorrect the chance of getting more incorrect prediction than correct ones is very small. Rinse; repeat.