~skeeto/public-inbox

1

Re: Billions of Code Name Permutations in 32 bits

Yaron Inger
Details
Message ID
<CAGtNdvubiZdcDULe23TGDusvpK5NfsS0DZocF9Eui3QCkPCVjQ@mail.gmail.com>
DKIM signature
pass
Download raw message
Thank you for the article!

The chain-walking (or chaining in general) assumes that the
permutation is full-period. For LCGs, the properties you specified
indeed guarantee that (by Hull–Dobell Theorem).

I wonder, though, whether this is true for the Kensler permutation as
well. I couldn't find any reference to it in the linked article or the
original paper.

Cheers!

Re: Billions of Code Name Permutations in 32 bits

Details
Message ID
<20210917193521.vi4idlxw35xepkkv@nullprogram.com>
In-Reply-To
<CAGtNdvubiZdcDULe23TGDusvpK5NfsS0DZocF9Eui3QCkPCVjQ@mail.gmail.com> (view parent)
DKIM signature
missing
Download raw message
The cycle-walking of the Kensler permutation does not require a full 
period, so that's probably why you couldn't find this information. :-) In 
fact, the permutations it's typically built on, including mine, have lots 
of independent cycles, and even fixed points.

How could this possibly work? It's subtle, and it's tripped me up every 
time I revisit it: The starting index is guaranteed to be in range since 
the caller must only ask for an index in range. Before considering this 
index, it's permuted, potentially going out of range. Eventually this 
cycle-walk must come back into range since it started in range with the 
original index.
Reply to thread Export thread (mbox)