News for hackers. Stuff that matters.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by brohee on Monday April 03, 2017 @02:36PM (#14025687)
Interesting, but no more.

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.".

Re:A Las Vegas algorithm to solve the elliptic curve discret... by dvdkhlng on Wednesday April 05, 2017 @07:59AM (#14041402)
The paper closes with

> 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.

Re:A Las Vegas algorithm to solve the elliptic curve discret... by dvdkhlng on Wednesday April 05, 2017 @10:59PM (#14047583)
Too late to edit my comment, but for correctness' sake: the algorithm as described is exponential in k (and thus n), not r and t.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by PaulAJ on Monday April 03, 2017 @02:47PM (#14025816)
Thanks. I was just about to ask.