Possible alternative numer-theoretic shuffling algorithm #323
Description
Motivation
Construct a shuffling algorithm where you can compute the value in the shuffled list at any specific position relatively cheaply without computing all of the other values at the same time. This could be used to replace the current shuffle.
Helpers
def is_prime(x):
return [i for i in range(2, int(x**0.5)+1) if x%i == 0] == []Algorithm
def value_at_position(n, value, seed):
# We do the shuffling mod p, the lowest prime >= n, but if we actually shuffle into
# the "forbidden" [n...p-1] slice we just reshuffle until we get out of that slice
p = n
while not is_prime(p):
p += 1
# x -> x**power is a permutation mod p
power = 3
while (p-1) % power == 0 or not is_prime(power):
power += 2
for round in range(40):
a = int.from_bytes(seed[(round % 8)*4: (round % 8)*4 + 4], 'big')
value = (pow(value, power, p) + a) % p
while value >= n:
value = (pow(value, power, p) + a) % p
# Update the seed if needed
if round % 8 == 0:
seed = hash(seed)
return value
def shuffle(values, seed):
return [values[value_at_position(len(values), i, seed)] for i in range(len(values))]Note that the above is a maximally simple definition, not an optimal implementation. An optimal implementation would calculate the prime, the exponent, and the a values once, and pass them as inputs to value_at_position, which would then need to do much less work per value.
The main weaknesses are: (i) the computation of the total shuffle is slower even with optimizations, and (ii) the security argument is more heuristic ("it repeats x -> x**3 + k[i] so it's like MIMC") than the current Fisher-Yates shuffle. However, the strengths may be worth it, especially if we wish to cease storing the shuffling in the state.