News for hackers. Stuff that matters.

A comment on Shortest bit sequence that's never been sent over the Internet (2017). Parent comment

Re:Shortest bit sequence that's never been sent over the Int... by bigiain on Thursday April 19, 2018 @01:50AM (#16873609)
Another possible detail this misses - I learnt about De Bruijn sequences from Samy Kamkar here:

http://samy.pl/opensesame/

(scroll about 1/3rd way down to the "(U) The OpenSesame Attack" section for the bits relevant to this discussion...)

You don't need to enumerate every n-bit sequence, you just need to enumerate a (shorter - by 62% in Samy's 12 bit case) sequence that contains all the n-bit sequences.

[ Parent | on HN ]
Re:Shortest bit sequence that's never been sent over the Int... by saagarjha on Thursday April 19, 2018 @02:09AM (#16873694)
Interestingly, there was an old USAMTS problem that had De Bruijn sequences in it, though I wasn't aware of it at the time: http://www.usamts.org/Tests/Problems_25_1.pdf
[ Parent | on HN ]
Re:Shortest bit sequence that's never been sent over the Int... by gumby on Thursday April 19, 2018 @02:20AM (#16873744)
This is the heart of the Boyer-Moore string searching algorithm too.
[ Parent | on HN ]