MT19937分析

前言

• 本内容是2022发在cryptography-wiki上的文章了，现在转回到blog上

正文

• MT19937即梅森旋转算法（Mersenne twister）由松本眞（日语：松本真）和西村拓士在1997年开发，基于二进制有限域$\mathbb{F}_2$上的矩阵线性递归，可以快速产生高质量的伪随机数。

  该算法的周期为$2^{19937}-1$，故名为MT19937。该算法具有以下优点

  1. 周期非常长，为$2^{19937}-1$
  2. 在$1\le k \le 623$都满足$k$-分布
  3. 能比硬件实现的方法更快产生随机数

• $k$-分布：一个周期为$P$的$w$位整数的伪随机数序列$x_i$，如果下列成立则称其$v$-比特精度的$k$-分布成立。

  令$\mathrm{trunc_v(x)}$表示由$x$的前$v$位形成的数，并考虑$P$中$k$个$v$位向量。

  $$(\mathrm{trunc_v(x_i)},\mathrm{trunc_v(x_{i+1})},\dots,\mathrm{trunc_v(x_{i+k-1})})\ (0\le i< P)$$

  然后，$2^{kv}$个组合中每一个都在一个周期内出现次数相同（全0组合出现次数较少除外）。

再探格密码

关于格密码的学习从很久以前已经开始，本篇博文主要是从头梳理再做一次系统的记录。

前言

什么是格

我们可以这样定义格，它是一组向量在$n$维空间中有着周期性的点集，或者说对于$n$个线性无关的向量$v_1,v_2,\dots,v_n \in \mathbb{R}^n$，这些向量的整系数组合构成的点集即为一个格，即

密码学

一些学习笔记，以下是目录