<p>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$.)</p>

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

<p>One exception to the last point, arguably, is the <a href="http://en.wikipedia.org/wiki/Feistel_network" rel="nofollow">standard Feistel network</a> 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}^+$.</p>

<p>(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).)</p>

<ds.algorithms><permutations><pseudorandom-generators>
Efficient (non-crypto-grade?) pseudorandom permutations with arbitrary domain size
kjo
# Efficient (non-crypto-grade?) pseudorandom permutations with arbitrary domain size

(Asked by: username_0 on 2014-07-04)

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](http://en.wikipedia.org/wiki/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).)

**Tags:** ds.algorithms, permutations, pseudorandom-generators

---

## 0 answers

