6
$\begingroup$

I am looking for an invertible discrete function $f:\{0,1,2,\dots,n-1\} \to \{0,1,2,\dots,n-1\}$ for some given integer $n$. I want $f(0),f(1),\dots,f(n-1)$ to return all the integers in range $[0..n)$ exactly once, but in a "messy", random-seeming arrangement. I anticipate that $n$ will be not bigger than $2^{30}$.

I thought about finding a generator for the group <Zn,*>, but I'm not sure if it would work for any given $n$ (would it?). Any other ideas?

|cite|improve this question
$\endgroup$
  • $\begingroup$ If $n$ is a prime then you can try $ax^{-1} + b$, where $0^{-1} = 0$. $\endgroup$ – Yuval Filmus Mar 9 '16 at 22:07
  • $\begingroup$ nothing garauntees me that n is prime... need a solution for any n, and i also didnt really see hows the suggested solution fit the needs... but thanks for trying :) $\endgroup$ – Ofek Ron Mar 9 '16 at 22:08
  • 1
    $\begingroup$ Approximately how large is $n$? Which algorithms are practical depends on the order of magnitude. $\endgroup$ – Gilles 'SO- stop being evil' Mar 9 '16 at 22:12
  • $\begingroup$ n can be any integer most likely not bigger then 2^30, if it helps 2^20 would also be nice. $\endgroup$ – Ofek Ron Mar 9 '16 at 22:14
  • $\begingroup$ Would keyed families work? ​ If needed, one could probably come up with a sort-of-"canonical" PRF and key. ​ ​ ​ ​ $\endgroup$ – user12859 Mar 9 '16 at 22:49
4
$\begingroup$

You are looking for a pseudorandom permutation on the set $\{0,1,2,\dots,n-1\}$. In cryptography, this has been studied under the (counter-intuitive) name "format-preserving encryption". There are a number of constructions you could use for your purposes.

There's a bunch of research literature on the problem, with different schemes that are optimized for different values of $n$. You can also find some summaries on Cryptography.SE.

I recommend you start by reading the question and the answers at Lazily computing a random permutation of the positive integers and Encrypting a 180-bit plaintext into a 180 bit ciphertext with a 128-bit block cipher and What are the examples of the easily computable "wild" permutations?.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Well, What i do isnt for encryption and i was looking for something quick and simple, what i did was finding the highest prime p that is smaller than n and a generator g in the group <Z_p,*> , and used the following f :

f(i) = (g^i)modp - 1 if i<n, i otherwise.

I know that the last n-p images are in order but oh well...

|cite|improve this answer
$\endgroup$
  • $\begingroup$ That doesn't solve the problem that you listed in the question, because the resulting map is not a bijection from $\{0,\dots,n-1\}$ to $\{0,\dots,n-1\}$. For instance, suppose $n=3$, so $p=2$, and $g=1$; then your function is $f(0) = 0$, $f(1) = 0$, $f(2) = 0$. That's not a bijection. Or, suppose $n=4$, so $p=3$, and $g=2$; then your function is $f(0) = 0$, $f(1) = 1$, $f(2) = 0$, $f(3) = 1$; again, not a bijection. If you meant i<p instead of i<n, it's still not a bijection; consider the same parameters. $\endgroup$ – D.W.♦ Mar 11 '16 at 4:13
  • $\begingroup$ the group is <Z_p,*> not <Z_p,+>, so g you mentioned is not a generator edited my answer $\endgroup$ – Ofek Ron Mar 11 '16 at 9:34
  • $\begingroup$ I think you haven't understood my comment, or you are confused about the definition of generator. $g=2$ certainly is a generator for the multiplicative group of integers modulo $p=3$, i.e., for the group $\mathbb{Z}_3^*$. (And $g=1$ is a generator for the multiplicative group of integers modulo $p=2$.) $\endgroup$ – D.W.♦ Mar 11 '16 at 10:03
  • $\begingroup$ g=1 is not a generator for p=2, you cant create 0 using 1^i, anyhow, the solution i wrote works for me, so thanks. $\endgroup$ – Ofek Ron Mar 11 '16 at 13:24
  • 1
    $\begingroup$ 0 is not an element of the multiplicative group, as it is not invertible: $\mathbb{Z}_p^*= (\{1,2,3,\dots,p-1\},\times)$. $\endgroup$ – D.W.♦ Mar 11 '16 at 15:46

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.