News for hackers. Stuff that matters.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by rawnlq on Monday April 03, 2017 @04:19PM (#14026754)
There's a popular interview question that has a las vegas algorithm as a solution. It's a more illustrative example since it takes an unbounded amount of time.

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.

Re:A Las Vegas algorithm to solve the elliptic curve discret... by curuinor on Monday April 03, 2017 @05:33PM (#14027389)
Similary to St. Petersburg paradox (https://en.wikipedia.org/wiki/St._Petersburg_paradox).

The expectation is a stranger and more dangerous beast than would be easily expected.