pseudo-random permutation of $[0,N)$

140 Views Asked by At

Given a positive integer:

$$\begin{align*} N \in \mathbb{Z}^+ \end{align*}$$

I would like a function:

$$\begin{align*} f : \mathbb{Z}^2 \rightarrow \mathbb{Z} \end{align*}$$

such that

$$\begin{align*} (f(N,0), f(N,1), f(N,2), \dots , f(N,N-1)) \end{align*}$$

is a deterministic but "pseudo-random" permutation of the identity N-vector:

$$\begin{align*} (0, 1, 2, \dots, N-1) \end{align*}$$

What is a simple closed form or algorithm for $f$?

1

There are 1 best solutions below

4
On BEST ANSWER

Let $\alpha=(\sqrt5-1)/2$, let $g(n)$ be the integer nearest $\alpha n$ among the integers relatively prime to $n$, and let $f(r,s)$ be $(s+g(r))g(r)$ reduced modulo $r$.