I'm trying to understand one aspect of a secure shuffle using Fisher-Yates. For reference, here is Fisher-Yates to shuffle an array x of n elements (numbered from 0 to n-1) (from Securing a Shuffle Algorithm):
for all i from 0 to n-1 let j = rnd(n - i) + i swap x[i] with x[j]
I don't quite understand what Tom Leeks is getting at in his explanation of the
rnd function at Securing a Shuffle Algorithm:
rnd(k): while true let z = next-random-word let r = z mod k if z - r + k <= 2^32 return r
r be used directly, and why is the
if z - r + k <= 2^32 needed?
I think my problem is I don't appreciate on understand the bias in the reduction.