[HN Gopher] Storing binary data in playing cards (2014)
       ___________________________________________________________________
        
       Storing binary data in playing cards (2014)
        
       Author : vmoore
       Score  : 31 points
       Date   : 2024-03-03 17:47 UTC (5 hours ago)
        
 (HTM) web link (www.timwarriner.com)
 (TXT) w3m dump (www.timwarriner.com)
        
       | styfle wrote:
       | This reminded me of the De Bruijn Sequence card trick.
       | 
       | https://sites.math.washington.edu/~billey/classes/562.winter...
        
       | qsort wrote:
       | I don't understand the claim that this is more efficient, it's
       | trivial to find a method that's information-theoretically
       | optimal: choose an arbitrary order for the cards, and encode
       | log(52!)/log(2) bits as the lexicographic order of the
       | permutation, doing a binary search each time.
       | 
       | Shouldn't be too hard to do even with pen and paper since the
       | 2-adic eval of 52! is large.
        
         | shiftingleft wrote:
         | > Shouldn't be too hard to do even with pen and paper since the
         | 2-adic eval of 52! is large.
         | 
         | Could you elaborate?
        
           | Y_Y wrote:
           | https://en.wikipedia.org/wiki/P-adic_valuation
           | 
           | It's nothing fancy, get the prime power decomposition of your
           | number and pick the exponent of p.
           | 
           | There's a clever way to do that for a factorial, but I have
           | the Pari/GP app on my phone so I just did:
           | valuation(52!,2)
           | 
           | which gives the answer 49, so 52! is divisible by 2 forty-
           | nine times. Interestingly chatgpt4 turbo got it right with no
           | extra prodding needed.
        
             | theamk wrote:
             | Does not seem right, the number is way too low.. after all,
             | just the last factor (52) can be divided by 2 at least 5
             | times.
             | 
             | My calculator says 225 bits, and text suggests the same.
             | Looks like chatgpt4 was wrong as usual:)
        
               | wiredfool wrote:
               | And 50 of the factors of 52! are greater than 2.
        
               | rmgk wrote:
               | The 2-adic valuation is about how often 2 is a prime
               | factor of a number.
               | 
               | For just 52 for example 2 is a prime factor twice,
               | because (52/2)/2 = 13, which is no longer divisible by 2.
               | 
               | Or in other words 52! / (2^49) is an integer, but 52! /
               | (2^50) is not, thus 49 is the correct answer.
        
           | qsort wrote:
           | The basic method would be to assign a number, 0 through
           | 52!-1, to each permutation in lexicographic order. Because
           | 52! is not a power of 2, if you want to encode binary bits,
           | you can only use 2^N permutations, where that number is the
           | largest power of 2 less than 52!. You can not losslessly
           | encode more than N bits, that's a hard bound, they just won't
           | fit.
           | 
           | If you wanted to turn this into an actual protocol, you would
           | presumably flag some permutations as invalid and use the
           | other ones. You would then encode one bit at a time doing a
           | binary search of the set of valid permutations.
           | 
           | Because 52! has a large number of 2s in its factorization,
           | for a careful choice of the valid permutations it should be
           | practical (or at least not significantly more impractical
           | than the OP's proposed method) to perform this by hand
           | because you would be able to "eyeball" most splits of the
           | binary search.
        
       | satori99 wrote:
       | This reminds me of Pontifex, the playing card based cipher
       | designed by Bruce Schneier for Neal Stephenson's _Cryptonomion_.
       | 
       | https://www.schneier.com/academic/solitaire/
        
       | jvandonsel wrote:
       | They seem to be ignoring another useful aspect of a deck of
       | cards. Each card could be placed face-up or face-down in the
       | deck.
        
         | rerdavies wrote:
         | And another 51 bits of info for whether the picture of the
         | puppy on the back of the card is right-side-up or upside-down!
         | (Or, absent puppies, any other asymmetrical pattern or image
         | that you chose for the message deck).
         | 
         | Because your recipient has to be able to determine the
         | reference orientation of the deck, you get 51 bits of extra
         | information from puppy orientation, and another 50 bits of
         | extra information from face-up/face-down orientation.
         | 
         | To place the deck in correct orientation, in preparation for
         | decoding, ensure that the top and bottom card are face up, and
         | that the puppy on the back of the top card isn't upside-down.
         | 
         | An extra 101 bits of information is significant!
        
       ___________________________________________________________________
       (page generated 2024-03-03 23:00 UTC)