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...