Invertible function that randomizes order - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T03:28:06Z https://cs.stackexchange.com/feeds/question/54227 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/54227 6 Invertible function that randomizes order Ofek Ron https://cs.stackexchange.com/users/1033 2016-03-09T22:05:30Z 2016-03-11T09:33:53Z <p>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}$.</p> <p>I thought about finding a generator for the group <code>&lt;Zn,*&gt;</code>, but I'm not sure if it would work for any given $n$ (would it?). Any other ideas?</p> https://cs.stackexchange.com/questions/54227/-/54271#54271 4 Answer by D.W. for Invertible function that randomizes order D.W. https://cs.stackexchange.com/users/755 2016-03-10T19:42:19Z 2016-03-10T19:48:34Z <p>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 "<a href="https://en.wikipedia.org/wiki/Format-preserving_encryption" rel="nofollow noreferrer">format-preserving encryption</a>". There are a number of constructions you could use for your purposes.</p> <p>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.</p> <p>I recommend you start by reading the question and the answers at <a href="https://cs.stackexchange.com/q/29822/755">Lazily computing a random permutation of the positive integers</a> and <a href="https://cs.stackexchange.com/q/47775/755">Encrypting a 180-bit plaintext into a 180 bit ciphertext with a 128-bit block cipher</a> and <a href="https://cs.stackexchange.com/q/41124/755">What are the examples of the easily computable &quot;wild&quot; permutations?</a>.</p> https://cs.stackexchange.com/questions/54227/-/54273#54273 0 Answer by Ofek Ron for Invertible function that randomizes order Ofek Ron https://cs.stackexchange.com/users/1033 2016-03-10T20:55:29Z 2016-03-11T09:33:53Z <p>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 <code>&lt;Z_p,*&gt;</code> , and used the following f :</p> <pre><code>f(i) = (g^i)modp - 1 if i&lt;n, i otherwise. </code></pre> <p>I know that the last n-p images are in order but oh well...</p>