Unique random number set computation

Permutation polynomial

One can notice that every application $F_p \rightarrow F_p$ can be written as a polynomial of $F_p[X]$. Indeed, for instance, given $F$ an application, a chebytchev polynomial equivalent to $F$ can always be found.

Thus, every element of $S_p$ can be described as a polynomial of $F_p[X]$.

Trivial algorithm

That way, one (still not-so-trivial ;)) algorithm would be:

• Generate a random polynomial of $F_p[X]$. This is equivalent to compute $p$ random coefficients ;

• Check if this polynom represents a permutation ;

• If not, go back to the first step.

But wait... There are multiple issues here.

First, these $p$ coefficients need to be stored in memory, giving a memory footprint of $O(p)$ bytes.

Moreover, the problem of checking whether a polynomial is a permutation one or not can be somehow complex and slow. Probabilistic methods exist (shown in [6]), but it still leaves us with some potential errors. The performance cost of all of this could be important. We didn't take the time to benchmark this algorithm as it suffers from the $O(p)$ memory issue...

And finally, left to generate a buffer of $p$ integers, we could just stick to the first "trivial" algorithm described at the beginning of this paper.

The real great stuff

We need to find a better way to generate these polynomials. We will use the $F_p$ division ring properties.

Indeed, it can be demonstrated that, in $F_p$, every permutation is a bijection, and every bijection is a permutation.

Thus, a whole set of polynomials can be described:

• for every $(a,b) \in (F_p^*,F_p), X \mapsto a*X+b$ is a bijection, and thus belongs to $S_p$ (Equation 1)

• for every $c$ such as $gcd(c,p-1) = 1$, $X^c$ is also a bijection [6], and belongs to $S_p$ (Equation 2).

Moreover, as the combination of two bijection functions is a bijection, combining these two sets of polynomials will produce new ones.

What's even more interesting is that it can be demonstrated that, for every $a \in F_p* \{X+1, a*X, X^{p-2}\}$ is a generator of the $S_p$ group, using the composition law. [6]

So, the final result is that, theoretically, every permutation of $S_p$ can be defined as a combination of these polynomials aforementioned.

Entropy and equiprobability: how random is random?

For the following, we will defines three sets :

• $G_a = F_p^*$, the values that can take a in (Equation 1) ;

• $G_b = F_p$, the values that can take b in (Equation 1) ;

• $G_c = \{c \in F_p \ / \ gcd(c,p-1)=1\}$, the values that can take $c$ in (Equation 2).

Let's define these two applications:

The first idea coming to our mind is to randomly combine the polynomials generated by these applications.

Let's define $GS_p$ ($S_p$ stands for 'seed part') as $G_a \times G_b \times G_c$.

For instance, let's randomly choose $S0=(a_0,b_0,c_0) \in GS_p$ and $S1=(a_1,b_1,c_1) \in GS_p$. The couple $(S0,S1) \in GS=GS_p \times GS_p$ can be considered as the seed of our random number generator.

We know that $L(a_0,b_0) \circ L(a_1,b_1)$ is a permutation polynomial, $L(a_0,b_0) \circ G(c_0)$ is another one, $G(c_0) \circ G(c_1)$ also, etc...

(Note: $\circ$ is the function composition, which means that, for instance, $(L(a,b) \circ G(c))(X) = a*X^c+b$)

Thus, every 'seed' values that belongs to $GS$ can produce a set of permutations.

Unfortunately, there are main issues with this approach, that we will call "entropy reduction". Indeed, we know that we can create permutations by composing $L(a_0,b_0), L(a_1,b_1), G(c_0)$ and $G(c_1)$, but :

• $L(a_0,b_0) \circ L(a_1,b_1)$ can also be expressed as $L(a_0*a_1, b_1*a_0+b_0)$. In other words, a combination of affine functions is an affine function). Moreover, as shown in Appendix A, choosing independently $a_0$ and $a_1$ in $G_a$ and computing $a_0*a_1$ is equivalent to randomly choose a number in $G_a$. The same goes with $b_1*a_0+b_0$. Thus, if we choose one seed $(S_0,S_1) \in (G_a \times G_b)^2$ and compute $L(a_0,b_0) \circ L(a_1,b_1)$, this is equivalent to choose a seed $S_0 ∈ (G_a \times G_b)$ ;

• The same issue comes with $G(c_0) \circ G(c_1)$, which is equals to $G(c_0*c_1)$ ;

• Even by combining $L(a_0,b_0) \text{ with } G(c_0)$, then with $L(a_1,b_1)$ and $G(c_1)$, (giving $L(a_1,b_1) \circ G(c_1) \circ L(a_0,b_0) \circ G(c_0)$), the following question must be answered:

is there any couple $(S_0,S_1) \in GS'xGS'$ such as $UPRNG(S_0) = UPRNG(S_1)$ ?

Another way to formalize this problem is as follows: given a seed taking values in a space $S \text{ of } s$ integers from $\mathbb{Z}/p\mathbb{Z}$ ($s$ unknown), is:

a bijective function?

Now, let's demonstrate a somehow intuitive result.

If $F$ is a bijection, then $\|S\| = \|S_p\|$, which gives $s = p!$. This means that, in order to generate a random permutation of $S_p$, we must choose a seed number between the $p!$ ones. In other words, we must choose $p$ unique random numbers. Well, this has just sent us back to the beginning of this article.

Our method for compromises

But the game is not yet finished, we haven't gone this far for nothing. So let's work a bit with our results.

We now understand that, somehow, some compromises have to be made. We know that the size of the seed must be reduced. By doing this, we know that we won't be able to uniquely generate all the possible permutations of $S_p$. Moreover, we want to do this in such a way that these properties will be conserved the best way:

• we still reach a fairly "reasonable" amount of permutations among $S_p$ ;

• all these permutations are unique (or a "lot of" them) ;

• all of this has still "good" performances (we haven't talk yet a lot about this one, but we don't forget it :)).

At this point, we decided to study the following UPRNG (named $UPRNGcomp$):

This choice is made because it produces a function that can be easily computed, and can still give interesting results.

Number of generated permutations

If $n$ is randomly chosen in $\llbracket 1,N \llbracket$, then the number of generated permutations with this method, is : $p*(p-1)*Phi(p-1)*N$ (with $Phi$ the Euler totient function [3]).

As we've seen above, the number of unique generated permutations may be inferior to this.

Thus, if we have for instance $n=2$, we can search for the set of $seeds \in GS$ for which same UPRNG is the same.

Let

• $(S_0,S_1) \in G_a \times G_b \times Gc$ ;

• $S_0 = (a_0,b_0,c_0)$ ;

• $S_1 = (a_1,b_1,c_1)$.

We need to resolve:

The complete resolution of this equation being a bit human-time consuming, we'll do it with $c_0=c_1=3$, and using mathematical software, we can find these solutions :

• obviously, $\{a_0=a_1, b_0=b_1\}$ ;

• and $\{a_0=p-a_1, b_0=b_1=0\}$.

Which means than, when $b_0=b_1=0$, only half the numbers of possible values for $a$ will give a unique permutation. By the way, this proves the fact that our UPRNG function isn't bijective.

We can test this easily with $p=17$. $gcd(3,17)$ being equals to 1, we can define:

And this python code:

def l(x,a,b,p): return (a*x+b)%p
def g(x,c,p):   return (x**c)%p
def lgn(x,a,b,c,p,n):
    for i in xrange(0,n):
        x = g(l(x,a,b,p),c,p)
    return x

list_x0 = list()
list_x1 = list()
p = 17
a = 5
b = 0
c = 3
n = 2
for x in range(0,p):
    list_x0.append(lgn(x, a, b, c, p, 2))
    list_x1.append(lgn(x, p-a, b, c, p, 2))

print(list_x0)
print(list_x1)

Which gives:

[0, 4, 8, 5, 16, 14, 10, 6, 15, 2, 11, 7, 3, 1, 12, 9, 13]
[0, 4, 8, 5, 16, 14, 10, 6, 15, 2, 11, 7, 3, 1, 12, 9, 13]

One possible solution is to reduce the space of $G_a$, for instance with $G_a=[1,\frac{p-1}{2}]$. But, without the full resolution of the (equation 1), this is just a partial resolution.

Appendix A

Let:

• $p$ a prime number ;

• $F_p = \mathbb{Z}/p\mathbb{Z}$ (which is a division ring) ;

• $X \text{ and } Y$ two independant random variables of $F_p$.

First, we have:

We have, for every $n \in F_p$,

Let $x \in F_p$ and $y \in F_p$, such as $x+y=n$, Thus, $x$ can have $p$ different values, and $y=n-x$ is unique for a fixed $x$. The number of $(x,y) \in F_p^2$ such as $x+y=n$ is then $p$.

So,

which means that choosing independently two random numbers in $F_p$ and sum the two of them is equivalent to only choose one random number in $F_p$.

Let's demonstrate the same result with $X*Y$.

Let $x \in F_p$ and $y \in F_p$ such as $x*y=n$,

Thus, $x$ can have $p$ different values. As $F_p$ is a division ring, we have $y=n*x^{-1}$ which is unique for a given $x$. So, the number of $(x,y) \in F_p^2$ such as $x*y=n \text{ is }p$, and

If we take these two results, and let $X, Y \text{ and } Z \in F_p$,

Let $y$ and $z \in F_p$, then $x=(n-z)*y^{-1}$ exists and is unique for a given $y$ and $z$. Thus, the number of $(x,y,z) \in F_p^3$ such as $x*y+z=n$ is $p^2$, and: