MT19937(梅森旋转算法)

这篇具有很好参考价值的文章主要介绍了MT19937(梅森旋转算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

梅森旋转算法

定义:梅森旋转算法(Mersenne twister)是一个伪随机数发生算法。由松本真和西村拓士在1997年开发,基于有限二进制字段上的矩阵线性递归。可以快速产生高质量的伪随机数,修正了古典随机数发生算法的很多缺陷。

其中,最为广泛使用Mersenne Twister的一种变体是MT19937,可以产生32位整数序列。具有以下的优点:

  1. 周期非常长,达到2−1。尽管如此长的周期并不必然意味着高质量的伪随机数,但短周期(比如许多旧版本软件包提供的2)确实会带来许多问题。

  2. 在1 ≤k≤ 623的维度之间都可以均等分布(参见定义)。

  3. 除了在统计学意义上的不正确的随机数生成器以外,在所有伪随机数生成器法中是最快的(当时

实现过程:

整个算法主要分为三个阶段:

第一阶段:获得基础的梅森旋转链;

第二阶段:对于旋转链进行旋转算法;

第三阶段:对于旋转算法所得的结果进行处理;

算法实现的过程中,参数的选取取决于梅森素数,故此得名。

MT19937

在讨论之前,引入MT19937-32的生成python代码:(此代码在 [0,2^32-1] 生成的伪随机数基本大致相同)

def _int32(x):
    return int(0xFFFFFFFF & x)

class MT19937:
    # 根据seed初始化624的state
    def __init__(self, seed):
        self.mt = [0] * 624
        self.mt[0] = seed
        self.mti = 0
        for i in range(1, 624):
            self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)

    # 提取伪随机数
    def extract_number(self):
        if self.mti == 0:
            self.twist()
        y = self.mt[self.mti]
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        self.mti = (self.mti + 1) % 624
        return _int32(y)

    # 对状态进行旋转
    def twist(self):
        for i in range(0, 624):
            y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
            self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]

            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df

接下来,我们观察上面MT19937的代码,我们可以发现代码分为四个部分:

一、_int32(x)模块

返回一个32位的二进制代码。

二、__init__(self, seed):

首先,我们必须要知道seed在代码中是种子,意思是基于已知的seed生成624个state块(伪随机数通过对不同的state块进行变换求得),我们先将state的第一个数值定为seed,代码中的623个循环便是通过state间的变换求出求出剩下的state块。

三、extract_number(self)

MT19937算法通过此模块来得到不同的伪随机数。首先,我们先进行判断,如果此时self.mti指向第一个state,我们运行__init__(self, seed):得到623个state值,如果不是,则直接进入下面的伪随机数生成过程:用通过seed求得的state值进行代码中的变换求得并返回我们所需的伪随机数。

四、twist(self):

如果只有上面的块,那么只能求得624个不同的伪随机数,但是MT19937-32却可以求出2^32-1个不同的伪随机数便是因为这个模块。旋转模块基于上一次循环中我们已经使用过的624个state值,一一对应,通过原代码中的:

y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]

if y % 2 != 0:
self.mt[i] = self.mt[i] ^ 0x9908b0df

求得新的624个与上一次循环中不同的state值,并进入新的循环中。

MT19937的反推导

引入反推导代码:

#python2
from Crypto.Util import number

# right shift inverse
def inverse_right(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift
    return tmp


# right shift with mask inverse
def inverse_right_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp

# left shift inverse
def inverse_left(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift
    return tmp


# left shift with mask inverse
def inverse_left_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp


def extract_number(y):
    y = y ^ y >> 11
    y = y ^ y << 7 & 2636928640
    y = y ^ y << 15 & 4022730752
    y = y ^ y >> 18
    return y&0xffffffff

def recover(y):
    y = inverse_right(y,18)
    y = inverse_left_mask(y,15,4022730752)
    y = inverse_left_mask(y,7,2636928640)
    y = inverse_right(y,11)
    return y&0xffffffff


def transform(message):
    assert len(message) % 4 == 0
    new_message = ''
    for i in range(len(message) / 4):
        block = message[i * 4 : i * 4 +4]
        block = number.bytes_to_long(block)
        block = convert(block)
        block = number.long_to_bytes(block, 4)
        new_message += block
    return new_message

transformed_flag = '641460a9e3953b1aaa21f3a2'
c = transformed_flag.decode('hex')
flag = transform(c)
print flag.encode('hex')

反推导就是我们在知道通过Mt19937算法求得的y1,来反推出用于MT19937算法的state原始值y。而异或的反推则是再异或相同的数就可以消去这个相同的数。

那么,我们先分析生成代码中所有的不同生成方式(主要分为 ">>" "<<" ">> &" "<< &"),所以,我们可以看到反推导代码中先将不同的生成方式写出(前四个),在其中,bits // shift是个难点,我们可以作以下分析:mt19937,crypto,python,安全

 MT19937算法的基本思路大致如此。文章来源地址https://www.toymoban.com/news/detail-578424.html

到了这里,关于MT19937(梅森旋转算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法竞赛入门【码蹄集进阶塔335题】(MT2291-2295)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月06日
    浏览(32)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2126-2150)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2023年04月19日
    浏览(39)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2281-2285)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月07日
    浏览(40)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2076-2100)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2023年04月19日
    浏览(48)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2176-2200)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月09日
    浏览(43)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2226-2250)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月11日
    浏览(38)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2286-2290)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月06日
    浏览(35)
  • 算法竞赛入门【码蹄集新手村600题】(MT1020-1040)

    码蹄集网站地址:https://www.matiji.net/exam/ojquestionlist (1)题目 输入一个实数,第一次按实型输出;第二次保留2位小数输出;第三次保留3位小数但最小列宽8列输出,空格分隔。 格式 样例1 (2)参考代码 (1)题目 输出3.1415926、12345678.123456789的小数、指数形式。 格式 样例1 (

    2024年02月16日
    浏览(45)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2151-2175)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月02日
    浏览(54)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2301-2305)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月06日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包