小谈随机数
in python with 0 comment

小谈随机数

in python with 0 comment

随机数

随机数在计算机科学中扮演者重要的角色。在 Python 中可以通过简单的设定上下限获取某一区间内的随机数。比如:

def test_random(max=9):
    _max = max
    x = random.randint(0, _max)
    return x

但是我们也明白这种随机数是伪随机数,它们肯定通过某一种算法产生。既然有了算法,也就有了 hack 的可能。

为了避免 hack 的可能性,计算机通常会通过设定一个 seed 值(不确定因素)。可能会使用时间,键盘敲击次数等多种数据综合设定。参考指标越多,伪随机数就越接近真正的随机生成。

随机数的检验标准

根据德国联邦信息安全办公室给出的随机数评定标准:

K1 — A sequence of random numbers with a low probability of containing identical consecutive elements.
K2 — A sequence of numbers which is indistinguishable from 'true random' numbers according to specified statistical tests.
K3 — It should be impossible for any attacker (for all practical purposes) to calculate, or otherwise guess, from any given sub-sequence, any previous or future values in the sequence, nor any inner state of the generator.
K4 — It should be impossible, for all practical purposes, for an attacker to calculate, or guess from an inner state of the generator, any previous numbers in the sequence or any previous inner generator states.

大体翻译为:

K1——相同序列的概率非常低。
K2——符合统计学的平均性,比如所有数字出现概率应该相同,卡方检验应该能通过,超长游程长度概略应该非常小,自相关应该只有一个尖峰,任何长度的同一数字之后别的数字出现概率应该仍然是相等的等等。
K3——不应该能够从一段序列猜测出随机数发生器的工作状态或者下一个随机数。
K4——不应该从随机数发生器的状态能猜测出随机数发生器以前的工作状态。

一般程序开发中所用到的随机数发生器只需要达到 K2 即可
满足需求,在加密应用(算法)中,则需要达到 K4。

验证 Python 随机数

如何验证 Python 的 random 库符合 K2?我做了如下的测试:
对[0, 9]的整数进行随机选取(random.randint),统计每个元素出现的次数。
结果如下:

Counter({0: 100362, 1: 100356, 8: 100219, 9: 100195, 6: 100177, 5: 100030, 7: 99884, 3: 99777, 4: 99593, 2: 99407})

如果觉得这个比较抽象的话,绘图如下:
CP4kQI.png

当然代码在这里(如何安装 pygal 和如何使用 Counter 前文有所提及):

import random
import pygal
import tempfile
from collections import Counter


def picture(**kwargs):
    path = tempfile.mktemp(".png", prefix="random_")
    line_chart = pygal.Bar(print_values=True)
    line_chart.title = kwargs.get('title', None)
    for k, v in kwargs.get('data', None).items():
        line_chart.add(str(k), v)
    line_chart.render_to_png(path)
    return path


def test_random(max=9):
    _max = max
    x = random.randint(0, _max)
    return x


def test():
    result = list()
    for i in range(1000000):
        result.append(test_random())
    _c = Counter(result)
    counter = dict(_c)
    picture(data=counter, title='result of random.randint')


if __name__ == '__main__':
    test()

当然,我也统计了每十次产生的随机数的标准差,在经过一百万次模拟之后,基本会得到这样一个结果:
CisH9P.png

伪随机数算法

下面是一些比较知名的伪随机数的算法 Python 的实现。

平方取中法

这个算法由大佬冯·诺依曼提出,是一个很古老的算法。
CPIuxs.png

import time


def random_msm(seed, n):
    if n == 1:
        return 0
    seed = int(seed)
    seed_len = len(str(seed))
    seed = int(seed**2 / pow(10, seed_len / 2)) % int(pow(10, seed_len))
    random_msm(seed=seed, n=n - 1)


def test():
    seed = time.time()
    random_msm(seed=seed, n=100)


if __name__ == '__main__':
    test()
[452404327, 967508832, 333999800, 586640004, 649429312, 843128479, 563210085, 559984570, 271863808, 993010026, 891173652, 47801901, 2173921, 5932514, 4722360, 683969, 813592, 931942, 515891, 143523, 598851, 622520, 531150, 120322, 477383, 894528, 180342, 523236, 775911, 37879, 48186, 18905, 73990, 45201, 31304, 99404, 11552, 34487, 93531, 80479, 68694, 88656, 98863, 38927, 53113, 9907, 1486, 2081, 3305, 9230, 1929, 7210, 9841, 8452, 4363, 357, 744, 353, 460, 160, 560, 360, 960, 160, 560, 360, 960, 160, 560, 360, 960, 160, 560, 360, 960, 160, 560, 360, 960, 160, 560, 360, 960, 160, 560, 360, 960, 160, 560, 360, 960, 160, 560, 360, 960, 160, 560, 360, 960]

可以看出这种算法十分脆弱,但是胜在速度极快。

线性同余法

这种方式又被称为混合同余法,公式大体如下:
CiJUyt.png
BTW,Typecho 的 LaTeX 体验十分糟糕。
同余的概念就是余数相同,也就是给定一个正整数 m,两个整数 a 和 b,如果 a 和 b 除以 m 余数相同,则称为 a 和 b 膜 m 同余。

from time import time, clock

a = 20180409
b = 22
m = 2**32


def gen(seed):
    seed = (a * seed + b) % m
    return seed / (m - 1)


def test():
    _min = int(input('min:'))
    _max = int(input('max:'))
    seed = time()
    rd = gen(seed=seed)
    res = int((_max - _min) * rd) + _min
    return res


if __name__ == '__main__':
    test()

对于这个方法,良好的初始值意味着不错的结果,对于 A、B、M 来讲应该符合下面的规范:
M:对于随机数的生成而言,随机数序列周期越长, 它就能够在 [0, 1] 上均匀分布及相互独立,M 越大周期就越大。
A:对于M的任何一个质因子P,A-1能被P整除。如果4是M的因子,则a除以4余1(证明见参考)。
B:增量B和M互质(证明见参考)。
以上条件可以用于生成高质量随机数,也就是将随机数的循环达到M的值(其他情况下都是小于循环M)。

当然这种方式也存在着显然易见的的问题,比如随机数周期过短和脆弱的生成序列等。

参考:
马华, 张晓清, 张鹏鸽. 一种基于线性同余算法的伪随机数产生器[J]. 纯粹数学与应用数学, 2005, 21(3):206-209.

Comments are closed.