# Randomizing Prime Field Elements

I need my code to generate random elements from $GF(p)$ ($F_p$ or $Z_p$, if you will).

The Crypto API I have available provides one with random bit strings. To tailor that to my needs, I can think of two possible solutions, each with its downside.

Solution 1: Sample $\lceil\log_2p\rceil$ bits, and reduce its corresponding integer modulo $p$ or $2^{\lfloor\log_2p\rfloor}$. This is efficient and easy but the resulting distribution is not uniform.

Solution 2: Repeatedly sample $\lceil\log_2p\rceil$ bits until the output integer is less than $p$. This gives a nice uniform distribution but is not constant time and may leak something about the internals of the random generator.

Is either of these a good idea, or is another method commonly practiced?

Edit: The accepted answer works for any set of elements (not necessarily a field) of any size (not necessarily prime).

is another method commonly practiced?

Sample $\lceil \log_2p \rceil+64$ bits, and reduce its corresponding integer modulo $p$.

There will still be a bias, but it is tiny. And, assuming that you use a constant time modulo operation, it's constant time...

• Thanks. Is there a formal analysis of this method? – Arya Pourtabatabaie Sep 13 '18 at 20:58
• @AryaPourtabatabaie: I'm not sure if anyone bothered publishing anything, but it's fairly straightforward to show that someone looking at the outputs cannot distinguish it from a random unbiased output stream with much less than $2^{128}$ outputs – poncho Sep 13 '18 at 21:03
• One could say for $n=r \mod p$, $x\in_RZ_n$ and $t=x \mod p$ we have: $P\{t=t_0|t_0<r\}=\frac{n-r}n\times \frac 1 p + \frac 1 n$ and $P\{t=t_0|t_0\geq r\}=\frac{n-r}n\times \frac 1 p$. These probabilities converge to each other and to $\frac 1 p$ as $n$ grows, giving us statistical indistinguishability. – Arya Pourtabatabaie Sep 13 '18 at 21:33

Hi @AryaPourtabatabaie

I've been having the exact same problem and would like to find a way to generate a distribution statistically close to uniform on $$F_p$$. This is my analysis of the above scheme.

I have a prime $$p$$ and random strings with length $$n$$. Let $$S = \{0,1\}^n$$ and define the function

$$H : S \rightarrow F_p, ~~~ H(x) \mapsto x \bmod p$$

Define $$U_p$$ to be the uniform distribution over $$F_p$$, and let $$H_p$$ mean the distribution of the output of $$H$$ when its inputs are uniformly distributed.

I want to compute the statistical distance between $$U_p$$ and $$H_p$$, $$\Delta(U_p, H_p)$$.

Observe that if $$p$$ evenly divided $$S$$, then all residue classes would have the same number of elements, that is, $$|S|/p$$. But because $$p$$ is a large prime and $$S$$ is a power of $$2$$, this will never be the case. There will be a set of residues that will be hit once more than the others, namely those less than $$|S| \bmod p$$. To compute the statistical distance, it is enough to compute the probability difference of these residues in both distributions.

Define: $$m = |S| \bmod p$$

$$k = \lfloor ~|S|/p~ \rfloor$$

We can partition $$F_p$$ in two sets:

$$A = \{0, \ldots, m-1\}$$

$$B = \{m, \ldots, p-1\}$$

The residues in $$A$$ are each generated by $$k+1$$ elements of $$S$$, while the residues in $$B$$ are generated by $$k$$ elements. You can see that

$$U_p(x) < H_p(x), \mbox{ for } x \in A$$

$$U_p(x) > H_p(x), \mbox{ for } x \in B$$

Specifically:

$$U_p(x) = 1/p$$

$$H_p(x | x \in A) = (k+1)/|S|$$

$$H_p(x | x \in B) = k/|S|$$

Then,

$$\Delta(U_p, H_p) = \Pr_{H_p}(A) - \Pr_{U_p}(A) = m \cdot \left(\frac{k+1}{|S|} - \frac{1}{p} \right)$$

The crucial part is this:

$$m \cdot \left(\frac{k+1}{|S|} - \frac{1}{p} \right) \leq$$

$$m \cdot \left(\frac{|S|/p + 1}{|S|} - \frac{1}{p} \right) =$$

$$(|S| \bmod p) \cdot \frac{1}{|S|} <$$

$$\frac{p}{|S|}$$

And now you can see, that if you fix your $$p$$, you can play around with the length of the bit strings that you need. If you use random strings of a similar size to $$p$$, you'll likely not get a decently small distance. But @poncho's suggestion will guarantee that you have at most $$2^{-64}$$ statistical distance, and you can control how low you can get.

If you go, for example, for standard hash lengths, you have 224, 256, 384, 512. For a prime around 256 bits, for example, take the next hash length at 384 and you get a statistical distance of at most $$2^{-128}$$ which is comfortably safe for today's standards.