[Cryptography] quantum computers & crypto

[Viktor Dukhovni]

> On 9 Nov 2021, at 9:10 pm, John Levine <johnl at iecc.com> wrote:
> 
>> Really? Did you mean to write 52! perfect shuffles in a row?
> 
> No, he meant to write 8.  

Actually, no, he meant 52.  You're both right, but 52 is "more right".

In the 8-shuffle cycle the top and bottom cards never move, and many
cards go through short cycles:

  * 48 cards make four 8-cycles
  * 2  cards make a 2-cycle
  * 2 cards make two 1-cycles

The shuffle works by numbering the cards 0 to 51, and at each step
sending x -> 2 * x and subtract 51 (cards 0 and 51 stay put).
Because 2^8 = 1 mod 51 this repeats after 8 steps.

In the 52-shuffle cycle every card moves, and each card occupies
each position exactly once.  The entire sequence of shuffles is
a single 52-cycle.  Here we number the cards from 1 to 52.  At
each step we send x -> 2 * x and subtract 53 if the result is
54 or larger.

Since 53 and 2 is a generator of its multiplication group, the
each, for each x, the sequence x, 2x, 4x, ..., (2^52)x takes
each value exactly once.  The cards move cyclically through
the sequence of powers of 2 mod 53.

If I were watching someone shuffling cards, and the top and
bottom cards never moved, that'd be rather dodgy.  The shuffle
where the card from the lower half of the dock comes to the
top looks more reasonable, and actually shuffles the deck
"better".

Although of course in either case the number of permutations
of the deck in the orbit of the shuffle is rather small,
both 8 and 52 are a lot less than 52 factorial.

-- 
	Viktor.