Can modular exponentiation be used to shuffle a list? I have noticed that modular exponentiation sometimes repeats every number only once, and therefore works like a shuffle mechanism for a list. I do not exactly know within what constraints it does this. I am interested in modular exponentiation for shuffling lists to reduce the computation needed to know the new position of any given object (that each object can know its new position, without knowing the position of every other object or the list as a whole).
Asked
Active
Viewed 25 times
1
-
If, for example the length of the list is $p-1$ and $\operatorname {ord}(2 \bmod {p}) = p-1$, we can map each element $x$ to $2^x \pmod {p}$ without collisions. Using $p=11$, we get the mapping $1\to2$, $2\to4$, $3\to 8$, $4\to 5$, etc.. Also, note that $p=7$ cannot be used as we would get collisions. Sadly the period of these cycles are $p-1$, thus failing to iterate over all $(p-1)!$ permutations, but nonetheless shuffling the list. – jorisperrenet May 29 '23 at 08:40
-
Is there limitations to what lengths for lists can be shuffled with modular exponentiation? Or, can any length be shuffled with it? – BipedalJoe May 30 '23 at 15:40