State of PRNG code in GMP

Torbjörn Granlund tg at
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_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).

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list