A Las Vegas algorithm to solve the elliptic curve discrete logarithm problem [pdf]
arxiv.org
arxiv.org
The commonly used curve P-256 has the prime order 115792089210356248762697446949407573529996955224135760342422259061068512044369.
From the paper "The largest group of elliptic group of prime order that we tested is 129159847, in which a discrete logarithm problem was solved.".
> However, we felt that computing the determinant for all possible sub matrices is a bottleneck for this algorithm and ways should be found to make this more efficient.
That last step is obviously of exponential complexity in the parameters r and t. I wonder whether the algorithm's total run-time becomes more acceptable when that last step is replaced by a polynomial-complexity computation.
To me it looks like an O(log(n)*n³) algorithm should be feasible, by replacing the submatrix-determinants with operations on determinants on large matrices that are generated in a way that ensures det=0 when any of the sub-matrices has det=0.
Unfortunately I don't really understand enough about the remainder of the paper to actually see how the useful the algorithm would be with that "bottleneck" removed.
Just because it (currently) only works on a small modulus doesn't make it a "boring non-result". It's the concept that matters.
Edit: TIL that they are different. (Thanks for the explanations below! esp: gmfawcett and 1001101)
Monte Carlo = Probably Correct, Always Fast
- Las Vegas: Correct, Time unbounded
- Monte Carlo: Not always correct, Time bounded
A Monte Carlo algorithm runs in a deterministic amount of time, and computes a probabilistic (approximate) result. For example: Monte Carlo numerical integration, or Miller-Rabin primality testing.
A Las Vegas algorithm takes a non-deterministic amount of time, but is guaranteed to return a correct result. For example: quicksort with a random choice of pivot.
Because it might sort faster or slower depending on how the pivot gets picked. But you'd get the sorted list in the end. A Monte Carlo solution might run for 5 seconds but you might get a partially sorted list only.
Let's say you want to simulate a 1/3-biased coin with a fair coin.
One solution is to flip the fair coin twice, then output heads if you get HH, output tails if you get TH or HT, otherwise retry (if TT).
Then this process is guaranteed to always output heads with 1/3 probability and tails with 2/3 probability if it ever ends. The runtime complexity is unbounded since you can keep getting TT forever but the expected runtime is constant.
The expectation is a stranger and more dangerous beast than would be easily expected.