2
$\begingroup$

I'm looking for an efficient/simple (even if not necessarily cryptographically strong) algorithm for implementing pseudorandom permutations with domain cardinality other than a power of 2. (FWIW, the domain cardinality I'm interested in at the moment is $900,000$.)

All the algorithms I've found for doing this aim for cryptographic strength, and tend to be relatively slow and intricate.

One exception to the last point, arguably, is the standard Feistel network algorithm, which is at least fairly simple. Unfortunately, AFAICT, this algorithm works only for permutations with domain size $2^{2m}$, with $m\in\mathbb{Z}^+$.

(I've found some generalizations of Feistel networks to arbitrary domain sizes, but they all aim for cryptographic strength, at the expense of performance (and simplicity).)

$\endgroup$
3
$\begingroup$

unbalanced numeric Feistel (page 10)
swap-or-not
FastPRP

Those are all cryptographically strong; I'm not aware of
any way to get better performance by sacrificing that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.