phc-discussions - Re: [PHC] OT: Pw0nd the tech riddle

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CAOLP8p4bNuST4zNrMH2TnTvNXtb4aGgO=54W=4hgWUQrmAe42A@mail.gmail.com>
Date: Mon, 19 May 2014 08:01:10 -0400
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] OT: Pw0nd the tech riddle

I find this problem particularly fun because even very smart computer geeks
seem to have some trouble with it.  I would not want to use this as an
interview question for this reason, but it makes a good puzzle.

Christian, your algorithm is exactly the one I came up with when the person
posing this puzzle seemed to want me to compare against middle-ish values.
 It's not bad, but it takes (1/2)N*log2(N) comparisons worst case.  The guy
really seemed to want me to do one comparison on the middle element, and
then recurse in 3 N/2xN/2 sub-matrices, but I am quite familiar with how
recursions that expand faster than they trim can explode exponentially
(TwoCats relies on this in the 2nd loop for TMTO resistance).  Recursing on
3 sub-matricis is the slowest algorithm proposed on the site, but the
person posing the puzzle seemed to view it as the "correct" answer.  The
binary search on the diagonal followed by searching two sub-matrices is
considerably faster.

Dmitry, I made the same mistake as you initially.  Who would have a matrix
sorted in each row and column, but not sorted such that each row contained
only elements greater than previous rows and less than following rows?
 It's hard to even make a random matrix like this.  Here's a tiny example:

1 3 4
2 7 8
5 7 9

Looking for 4, you can't just skip row 1 and search only row 2.  To prove
the target element is not there, you have to check the adjacent elements
spanning the target on all diagonals from the upper left to lower right.
 This requires 2*N-2 comparisons worst-case.

Another oddity about this problem is how unnatural it feels.  Data simply
does not wind up partially sorted in this pattern in real life, so all the
years of intuition we've built up for data search has to be questioned
carefully.  My initial reaction was "Why would anyone sort data this way?"
 It's a fun puzzle, but SFAIK, it has zero practical application.

Bill

Content of type "text/html" skipped