677. Weaknesses in seed_seq::randomize [rand.util.seedseq]

Section: [rand.util.seedseq] Status: CD1 Submitter: Charles Karney Opened: 2007-05-15 Last modified: 2016-01-28 10:19:27 UTC

Priority: Not Prioritized

View all other issues in [rand.util.seedseq].

View all issues with CD1 status.


seed_seq::randomize provides a mechanism for initializing random number engines which ideally would yield "distant" states when given "close" seeds. The algorithm for seed_seq::randomize given in the current Working Draft for C++, N2284 (2007-05-08), has 3 weaknesses

  1. Collisions in state. Because of the way the state is initialized, seeds of different lengths may result in the same state. The current version of seed_seq has the following properties:

    The proposed algorithm (below) has the considerably stronger properties:

  2. Poor mixing of v's entropy into the state. Consider v.size() == n and hold v[n/2] thru v[n-1] fixed while varying v[0] thru v[n/2-1], a total of 2^(16n) possibilities. Because of the simple recursion used in seed_seq, begin[n/2] thru begin[n-1] can take on only 2^64 possible states.

    The proposed algorithm uses a more complex recursion which results in much better mixing.

  3. seed_seq::randomize is undefined for v.size() == 0. The proposed algorithm remedies this.

The current algorithm for seed_seq::randomize is adapted by me from the initialization procedure for the Mersenne Twister by Makoto Matsumoto and Takuji Nishimura. The weakness (2) given above was communicated to me by Matsumoto last year.

The proposed replacement for seed_seq::randomize is due to Mutsuo Saito, a student of Matsumoto, and is given in the implementation of the SIMD-oriented Fast Mersenne Twister random number generator SFMT. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/SFMT-src-1.2.tar.gz

See Mutsuo Saito, An Application of Finite Field: Design and Implementation of 128-bit Instruction-Based Fast Pseudorandom Number Generator, Master's Thesis, Dept. of Math., Hiroshima University (Feb. 2007) http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/M062821.pdf

One change has been made here, namely to treat the case of small n (setting t = (n-1)/2 for n < 7).

Since seed_seq was introduced relatively recently there is little cost in making this incompatible improvement to it.

See N2391 and N2423 for some further discussion.

Proposed resolution:

Adopt the proposed resolution in N2423.

[ Kona (2007): The LWG adopted the proposed resolution of N2423 for this issue. The LWG voted to accelerate this issue to Ready status to be voted into the WP at Kona. ]