2
$\begingroup$

I am searching a fast pseudo-random permutation function with the following requirements.

Given a predefined set of values $V$ and an integer $k$. Split $V$ to $k$ subset, and iterate over any subset in order.

In more detail, we need an $n$-length ordered value set $V$ splitted to $k$ (contiguous) partitions. Partitioning is represented by (1) the function $part(v): V \to N$ wich returns with the partition index of the value $v$, and (2) the function $rng(p): N \to V_2$ ($p \in N$, the partition index) which returns with the bounds of the partition associated to $p$. In the same time we need the permutation function $perm(v): V \to V$, where partitions are stable:

$$v_1 < v_2 ~ ~ \land ~ ~ part(v_1) = part(v_2) ~ ~ \implies ~ ~ perm(v_1) < perm(v_2)$$

Partition number is predefined, there can be empty partitions. Permutation and partitioning must be key based: with a different key we get totally different results.

We are searching for such a $part(v)$, $rng(p)$ and $perm(v)$ (and $perm'(v)$, if possible)

It would be nice if partitions could be predefined, or at least controlled in some way (e. g. binomial distribution). It would be also nice if v (∈ V) could have an arbitrary length. The algorithms should be as fast as possible. Cryptographical secureness is a nice-to-have.

Here is an example visualization:

Demonstration of a permutation with stable partitions

Where (indices from $0$):

  • $part(3) = 0$
  • $part(C) = 2$
  • $rng(1) = [4, A]$
  • $perm(4) = 1$
  • $perm'(4) = C$
Improve this question
$\endgroup$
2
  • $\begingroup$ How large is $|V|$? What does it mean to you to have a pseudorandom permutation algorithm? Do you want an algorithm to output the entire permutation (i.e., the entire truth table with all $|V|$ entries)? Or do you want it to give you a function that given $v$, outputs $perm(v)$, without generating or storing the entire permutation? (e.g., in time polynomial in $\lg |V|$, say) Are there any running time requirements? $\endgroup$ – D.W.♦ Oct 13 '20 at 7:40
  • $\begingroup$ @D.W. Hm, the first sentence is just a lame introduction. There are no strict bound in space and time (even if $|V|$ is limited, we could extend it to be working with larger values, with some limitations; $lg |V|$ with a low constant factor would be acceptable). But (unextended) maximum of $|V|$ must be large (ideally at least millions), it would be nice if it could be arbitrary (bound or not). We don't want to store the entire permutation (the major goal is not to do so), we are searching for the four (or three if $perm'(v)$ is impossible) functions described above. $\endgroup$ – Dávid Horváth Oct 13 '20 at 9:07

Your Answer

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

Browse other questions tagged or ask your own question.