std::mt19937 Sınıfı - Mersenne Twister Algoritması Bir Pseudo-random number generator (PRNG)

Giriş
mt19937 dışarıya uint32 yani 0 - 2^32 -1 arasında bir değer döndürür. Kendi içinde ise 624 x 32 bit yani 19968 bit büyüklüğünde state saklar.  19937 sayısı aslında state içinde kullanılan bit sayısını gösterir.

Açıklaması şöyle. Yani bu nesneyi yaratmak maliyetli

Pseudo-random number generators (PRNGs), like default_random_engine or mt19937, are usually semi-cheap to create, but expensive to seed. How expensive this is largely depends on the size of the state they keep internally, and what the seeding procedure is. For example, the std::mersenne_twister_engine in the standard library keeps a "large" (leaning towards "huge") state which makes it very expensive to create.

Algoritma belli olduğu için şu cümle tanımlı.

Required behavior: The 10000th consecutive invocation of a default-constructed object of type mt19937 shall produce the value 4123659995.

Dolayısıyla "Cryptographically Secure" değildir. Açıklaması şöyle

A Mersenne Twister based pseudorandom number generator is not cryptographically secure.

The reason a MT isn't good for crypto purposes is because given some set of outputs you can start making accurate predictions on the next output.

Cryptographically secure requires all primitives and the underlying protocol to be cryptographically sound without sacrificing entropy or uniformity.

Typedef
Bu sınıf aslında bir typedef. Şöyledir.

typedef mersenne_twister_engine<uint_fast32_t,
  32,624,397,31,0x9908b0df,11,0xffffffff,7,0x9d2c5680,15,0xefc60000,18,1812433253>
       mt19937;

Bu typdef yerine tüm parametreleri kendimiz template olarak kullanmak istersek şöyle yaparız.

#define MT_TARGLIST UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f

template<MT_TPARAMS>
void foo(std::mersenne_twister_engine<MT_TARGLIST>& mt) {
  ...
}

Distribution Sınıfları
std::mt19937 genellikle bir bir distribution sınıfı ile birlikte kullanılır.

Örnek
Şöyle yaparız.

std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist(0, 100);
int index = dist(mt);

Constructor - random_device
Örnek
Şöyle yaparız.

auto gen = std::mt19937 { std::random_device{}() };

Örnek
Şöyle yaparız.

std::random_device rd;  
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 5);
dis(gen);

Bu kod eleştirilere maruz kalıyor. Sebepleri şöyle. Tüm bunlar şu anlama geliyor mt19937'yi ilklendirmek için random_device yeterli değil.

1. rd() returns a single unsigned int. This has at least 16 bits and probably 32. That's not enough to seed MT's 19937 bits of state.

2. Using std::mt19937 gen(rd());gen() (seeding with 32 bits and looking at the first output) doesn't give a good output distribution. 7 and 13 can never be the first output. Two seeds produce 0. Twelve seeds produce 1226181350.

3. std::random_device can be, and sometimes is, implemented as a simple PRNG with a fixed seed. It might therefore produce the same sequence on every run. (Link) This is even worse than time(NULL).

Constructor - time

Örnek
Şöyle yaparız.

std::mt19937 gen(static_cast<std::mt19937::result_type>(std::time(nullptr)));

Örnek
Şöyle yaparız.

 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

Constructor - seed_seq
Şöyle yaparız. Bazı uygulamalarda bu sınıf önce ısındırılıyor (warm-up)

std::array<int, std::mt19937::state_size> seed_data;
std::random_device r;
std::generate_n(seed_data.data(), seed_data.size(), std::ref(r));
std::seed_seq seq(std::begin(seed_data), std::end(seed_data));

std::mt19937 eng(seq);

Eğer istenirse seed dizisi şöyle de verilebilir.

std::seed_seq seq{1, 2, 3, 4, 5};
std::mt19937 eng(seq);

Constructor - windows
Bu kod portable değil ancak random_device ile ilklendirmeye göre daha iyi. Şöyle yaparız

bool acquire_context(HCRYPTPROV *ctx)
{
  if (!CryptAcquireContext(ctx, nullptr, nullptr, PROV_RSA_FULL, 0)) {
    return CryptAcquireContext(ctx, nullptr, nullptr, PROV_RSA_FULL,
      CRYPT_NEWKEYSET);
  }
  return true;
}


size_t sysrandom(void* dst, size_t dstlen)
{
  HCRYPTPROV ctx;
  if (!acquire_context(&ctx)) {
    throw std::runtime_error("Unable to initialize Win32 crypt library.");
  }

  BYTE* buffer = reinterpret_cast<BYTE*>(dst);
  if(!CryptGenRandom(ctx, dstlen, buffer)) {
    throw std::runtime_error("Unable to generate random bytes.");
  }

  if (!CryptReleaseContext(ctx, 0)) {
    throw std::runtime_error("Unable to release Win32 crypt library.");
  }
  return dstlen;
}

Kullanmak için şöyle yaparız.

std::uint_least32_t seed;    
sysrandom(&seed, sizeof(seed));
std::mt19937 gen(seed);

Constructor - linux
Şöyle yaparız. /dev/urandom dışında linux'ta getrandom(), openbsd'de getentropy() metodları kullanılabilir.

size_t sysrandom(void* dst, size_t dstlen)
{
  char* buffer = reinterpret_cast<char*>(dst);
  std::ifstream stream("/dev/urandom", std::ios_base::binary | std::ios_base::in);
  stream.read(buffer, dstlen);

  return dstlen;
}

Kullanmak için şöyle yaparız.

std::uint_fast32_t[std::mt19937::state_size] state;
sysrandom(state, sizeof(state));
std::seed_seq s(std::begin(state), std::end(state));

std::mt19937 g;
g.seed(s);

operator << metodu
Akıma yazmak için şöyle yaparız.

std::mt19937 & mt = ...;
std::ostringstream oss;
if (!(oss << mt))
  throw std::invalid_argument("mersenne_twister_engine state");

operator >> metodu

Stream'den okumak için şöyle yaparız.

std::mt19937 mt;
std::string text;
std::istringstream iss(text);

if (!(iss >> mt))
  throw std::invalid_argument("mersenne_twister_engine state");

seed metodu
Şöyle yaparız.

std::uint_fast32_t[std::mt19937::state_size] state;
...
//populate state array with random data
std::mt19937 gen;
gen.seed(s);

state_size alanı
Sınıfın kendi içinde kaç bit state sakladığını belirtir. Şöyle yaparız.

std::uint_fast32_t[std::mt19937::state_size] state;