State of PRNG code in GMP
Torbjörn Granlund
tg at gmplib.org
Mon Jun 1 10:10:19 UTC 2020
I am looking into adding AES CTR as a new, fast PRNG in GMP.
Unfortunately, the current code is somewhat confusing.
The main structure for storing random state is the following:
typedef struct
{
mpz_t _mp_seed; /* _mp_d member points to state of the generator. */
gmp_randalg_t _mp_alg; /* Currently unused. */
union {
void *_mp_lc; /* Pointer to function pointers structure. */
} _mp_algdata;
} __gmp_randstate_struct;
typedef __gmp_randstate_struct gmp_randstate_t[1];
Question 1: Why is _mp_lc wrapped in a union?
Question 2: "_lc" = Linear Congruential? This is supposed to be a
generic structure, right?
A few lines before the above declaration, we have this:
/* Available random number generation algorithms. */
typedef enum
{
GMP_RAND_ALG_DEFAULT = 0,
GMP_RAND_ALG_LC = GMP_RAND_ALG_DEFAULT /* Linear congruential. */
} gmp_randalg_t;
So LC is the default? And that's the one choice? The manual says about
Mersenne Twister: "Randomness properties are also very good and this is
the default algorithm used by GMP."
Let's look at what functions we have for initialising a gmp_randstate_t:
void gmp_randinit (gmp_randstate_t, gmp_randalg_t, ...);
void gmp_randinit_default (gmp_randstate_t);
I have understood that the latter, gmp_randinit_default chooses Mersenne
Twister. One would expect
gmp_randinit (my_randstate, GMP_RAND_ALG_DEFAULT)
to also choose Mersenne Twister. But GMP_RAND_ALG_DEFAULT =
GMP_RAND_ALG_LC as per the enum definition.
Question 3: What algorithm does the call
gmp_randinit (my_randstate, GMP_RAND_ALG_DEFAULT)
choose? Is it Mersenne Twister? Good, I guess as we're then consistent
with what we call the default PRNG algorithm. Bad, since then the call
gmp_randinit (my_randstate, GMP_RAND_ALG_LC)
also chooses Mersenne Twister, which is really confusing!
Question 4: How should a user who really wants LC choose that?
This all looks very strange to me.
Perhaps we should start anew with a new set of random state functions
and a new type (where all fields are actually used!). The name
gmp_prngstate_t might be useful.
A side note about using AES or other block ciphers as PRNGs: While
Mersenne Twister is considered a good PRNG, piggybacking on well-studied
block cipher algorithms seems even better. Furthermore, AES is
extremely fast, proof-of-concept code I wrote yields generate about 100
Gbit/s on a current AMD CPU per core (and about 50 Gbit/s on a current
Intel CPU per core).
--
Torbjörn
Please encrypt, key id 0xC8601622
More information about the gmp-devel
mailing list