【密码学】一文读懂MT19937
![]MO$QND[_P_8_@G]TCR8GZI.jpg](https://ucc.alicdn.com/pic/developer-ecology/ed62190ee103450cb62cc57f28733711.jpg?x-oss-process=image/resize,w_1400/format,webp "]MO$QND[_P_8_@G]TCR8GZI.jpg")
瞄了一眼redis的源码，然后发现里面好玩的东西还挺多的，本文来聊一聊redis当中用到的一个随机数生成算法 mt19937，具体源码参见文末的参考资料，在这里就不贴到文本当中了。对于redis源码里面用的是mt19937-64本文先来看一下32位的版本，对于64位的版本，只不过状态当中元素用的是64位的元素，整个运算过程框架是类似的。
「梅森旋转算法」（「Mersenne twister」）是一个伪随机数生成算法，由松本真和西村拓士在1997年提出来的，可以快速产生高质量的伪随机数，修正了古典随机数生成算法当中的很多缺陷。19937这个名字来源于周期长度为梅森素数 。
生成器结构
![OBAK1U[T7G]C@CA0)UAVAKD.png](https://ucc.alicdn.com/pic/developer-ecology/2d5c3d89479b428ba1da495a9616883b.png?x-oss-process=image/resize,w_1400/format,webp "OBAK1U[T7G]C@CA0)UAVAKD.png")
MT19937生成器结构
如上图所示，mt19937的随机数生成器结构首先需要一个uint32的种子，然后生成一个具有624个uint32数组的状态数组。生成状态数组之后，进行一次旋转，最终可以输出624个随机的uint32。然后重复执行旋转操作，就可以得到一个周期为 的随机数生成器了。
对于mt19937整个计算过程来说，虽然比我之前提到过的线性同余法复杂不少，但是整个流程还是比较清晰的，对于里面的原理，我其实也了解的不是很多，因此在这里就不展开讲了，如果想了解原理的读者，可以参考文末的参考资料当中的论文进行学习，本文是指来聊一下这个东西具体是怎么计算的。到这里，这篇文章我就水完了，逃~~~
代码实现
老样子了，还是给出我写的两个语言的参考，注意本文讲的是32位的mt19937，再去看redis源码当中的实现的时候用的是mt19937-64。
Go
const ( n = 624 m = 397 ) type MT19937 struct { state []uint32 index int } func New(seed uint32) *MT19937 { mt := &MT19937{ state: make([]uint32, n), index: 0, } mt.state[0] = seed for i := uint32(1); i < n; i++ { mt.state[i] = 1812433253*(mt.state[i-1]^mt.state[i-1]>>30) + i } return mt } func (mt *MT19937) twist() { for i := uint32(0); i < n; i++ { y := (mt.state[i] & 0x80000000) + (mt.state[(i+1)%n] & 0x7fffffff) mt.state[i] = (y >> 1) ^ mt.state[(i+m)%n] if y%2 != 0 { mt.state[i] = mt.state[i] ^ 0x9908b0df } } } func (mt *MT19937) Uint32() uint32 { if mt.index == 0 { mt.twist() } y := mt.state[mt.index] y = y ^ y>>11 y = y ^ y<<7&2636928640 y = y ^ y<<15&4022730752 y = y ^ y>>18 mt.index = (mt.index + 1) % n return y }
Rust
const N: usize = 624; struct MT19937 { state: [u32; N], index: usize, } impl MT19937 { pub fn new(seed: u32) -> Self { let mut mt = MT19937 { state: [0; N], index: 0, }; mt.state[0] = seed; for i in 1..N { mt.state[i] = 1812433253 * (mt.state[i - 1] ^ (mt.state[i - 1] >> 30)) + i as u32; } mt } fn twist(&mut self) { for i in 0..N { let x = (self.state[i] & 0x80000000) | (self.state[(i + 1) % N] & 0x7fffffff); let mut x_a = x >> 1; if x % 2 != 0 { x_a ^= 0x9908b0df; } self.state[i] = self.state[(i + 397) % N] ^ x_a; } self.index = 0; } fn rand(&mut self) -> u32 { if self.index >= N { self.twist(); } let y = self.state[self.index]; self.index += 1; y ^ y >> 11 } }
