16 Haziran 2020 Salı

std::mt19937 Sınıfı - Mersenne Twister Algoritması

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.

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 genellike 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
Ben böyle kodları sevmiyorum. random_device ile ilklendirmek çok daha okunaklı.

Ö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;

Hiç yorum yok:

Yorum Gönder