什么是随机数(来源于百度百科)
根据密码学原理,随机数的随机性检验可以分为三个标准:
统计学伪随机性。统计学伪随机性指的是在给定的随机比特流样本中,1的数量大致等于0的数量,同理,“10”“01”“00”“11”四者数量大致相等。类似的标准被称为统计学随机性。满足这类要求的数字在人类“一眼看上去”是随机的。
密码学安全伪随机性。其定义为,给定随机样本的一部分和随机算法,不能有效的演算出随机样本的剩余部分。
真随机性。其定义为随机样本不可重现。实际上只要给定边界条件,真随机数并不存在,可是如果产生一个真随机数样本的边界条件十分复杂且难以捕捉(比如计算机当地的本底辐射波动值),可以认为用这个方法演算出来了真随机数。
相应的,随机数也分为三类:
伪随机数:满足第一个条件的随机数。
密码学安全的伪随机数:同时满足前两个条件的随机数。可以通过密码学安全伪随机数生成器计算得出。
真随机数:同时满足三个条件的随机数。
真正的随机数是使用物理现象产生的:比如掷钱币、骰子、转轮、使用电子元件的噪音、核裂变等等,这样的随机数发生器叫做物理性随机数发生器,它们的缺点是技术要求比较高。
使用计算机产生真随机数的方法是获取cpu频率与温度的不确定性以及统计一段时间的运算次数每次都会产生不同的值,系统时间的误差以及声卡的底噪等。
在实际应用中往往使用伪随机数就足够了。这些数列是“似乎”随机的数,实际上它们是通过一个固定的、可以重复的计算方法产生的。计算机或计算器产生的随机数有很长的周期性。它们不真正地随机,因为它们实际上是可以计算出来的,但是它们具有类似于随机数的统计特征。这样的发生器叫做伪随机数发生器。
python编程中也常常需要用到随机数,最常见的方法就是使用 random 库函数,具体用法详见: 《Python 随机数模块random最常用的8个方法》。最最常用的就是 random.random()函数,其它函数也就是在此基础上写的以减少编程工作量。
那么问题来了:如果不给用random库,怎样产生随机数呢?
第一个想到了向python要答案,查阅了库文件夹中的 random.py 文件, 函数random.random()最核心的功能可以精简成一行代码:
>>> int.from_bytes(__import__('os').urandom(7), 'big')/2**56 0.09013223780767188 >>> int.from_bytes(__import__('os').urandom(7), 'big')/2**56 0.9650436894658889 # 或者导入nt库 >>> import nt >>> int.from_bytes(__import__('nt').urandom(7), 'big')/2**56 0.3542357188572307 >>> int.from_bytes(__import__('nt').urandom(7), 'big')/2**56 0.9618276475349845 >>>
函数测试:
>>> import os >>> os.urandom(7) b'\xf1\x84\xfe\xc3djw' >>> os.urandom(7) b'\xbd\xcd\r\x9e\xefp%' >>> os.urandom(3) b'!\x9c\xf3' >>> os.urandom(10) b'\x88"\xe2\x96LQ\xda~\x05\xb1' >>> os.urandom(50) b'\x0bj\xf8\xf5\xa5 \x06\x1e\xf6\xc4F\x13>yh\xf6\xc14y\xbd#\xf1B\xc68\xfb\x98\xfb\x03\xea\xd2\xc2k\xbcW\xf2\xeeP\xf3\x19\x1cl{C)\xfb;:\x18L' >>> len(b'\x88"\xe2\x96LQ\xda~\x05\xb1') 10 >>> len(b'\x0bj\xf8\xf5\xa5 \x06\x1e\xf6\xc4F\x13>yh\xf6\xc14y\xbd#\xf1B\xc68\xfb\x98\xfb\x03\xea\xd2\xc2k\xbcW\xf2\xeeP\xf3\x19\x1cl{C)\xfb;:\x18L') 50 >>> import nt # windows版本可用nt模块 >>> int.from_bytes(nt.urandom(7), 'big') 2306667593785244 >>> int.from_bytes(nt.urandom(7), 'big') 69590181037056784 >>> int.from_bytes(nt.urandom(7), 'little') 21781942293812511 >>> >>> int.from_bytes(nt.urandom(50), 'big') 1069720869084249861368160549175273630208421249913479589421661681088056615165558546864053057967465294818199845931432043487
随机功能主要是os.urandom() 函数产生的,它返回一个包含适合加密使用的随机字节的bytes对象。代码先用它生成一个7字节的bytes对象,然后用 int.from_bytes()转成一个长整型数,再除以2的56次方就得到一个随机纯小数了。(估计是为了照顾老版本的python,原代码中长整型数先右移3位再乘以2的-53次方)
定义两个函数:
>>> random = lambda:int.from_bytes(__import__('os').urandom(7), 'big')/2**56 >>> randint = lambda a,b:round(a+(b-a)*int.from_bytes(__import__('os').urandom(7), 'big')/2**56) >>> random() 0.9292853490365796 >>> random() 0.6640972585301943 >>> random() 0.8963245292184984 >>> randint(1,9) 6 >>> randint(1,9) 2 >>> randint(1,9) 7 >>> [randint(1,9) for _ in range(16)] [1, 5, 6, 7, 7, 9, 4, 8, 2, 9, 3, 1, 3, 7, 9, 1] >>> [randint(1,9) for _ in range(20)] [8, 7, 7, 4, 9, 4, 7, 5, 7, 2, 6, 3, 8, 3, 7, 5, 2, 2, 1, 6] >>> >>> # 自定义函数与random.random()功能一致 >>> [__import__('random').randint(1,9) for _ in range(20)] [9, 4, 9, 7, 2, 9, 7, 4, 4, 5, 6, 7, 7, 4, 9, 6, 8, 9, 7, 1] >>> [__import__('random').randint(1,9) for _ in range(20)] [1, 4, 7, 1, 1, 3, 3, 9, 2, 6, 4, 7, 2, 9, 7, 3, 9, 3, 6, 9]
os.urandom()的本质是产生随机字符串,转码后做随机密码还是很赞的:
>>> from os import urandom as urnd >>> from base64 import b64encode >>> b = [urnd(9) for _ in range(30)] >>> [b64encode(i).decode() for i in b] ['skXfm5YLmlQr', 'nYSXOTwlnGi9', 'i4gYbYx+Xhyv', '/3F5cMRiHZ7A', '0j5637jtmrZh', 'fCyGfakN2Q33', 'hhGNRAGZx508', 'BVgi4qfdG0hg', 'ZZqyS0Vfigp4', 'ivcnDarmMJsm', 'GH8wBSf2tDgM', 'dJ6deMnRkazQ', 'Sk+G3mdSUVDp', 'Qzh+ZOJvCLOy', '3NQagF2rBpop', '8OzQgYGjbx8r', 'AWrg2PdqBvKY', 'DW2hv37pgAne', 'G7cdNUOsF1bJ', 'iDj+oFq38GYY', 'jcCCa1YvL1JK', '490X7cqIQBT9', 'vuPmV08BKmJx', 'sVKoHjQkd7At', 'St5VLSAF60z1', 'Rgl/W9ooFCuJ', '68xT85BaQSuh', 'o9/rqZRpZHo3', 'qWERX6CRqxxj', 'oCehldmw+emo'] >>> >>> # 当然用string和random库也能实现随机字符串: >>> import string,random >>> [''.join(random.sample(string.printable[:-6],10)) for _ in range(30)] ['\\T[~(]J#"+', '):0~He7Dam', 'zw=?>7a(&^', 'v<c@W:!&VP', 'y\\~W6{u:P1', 'R)il~3p+;y', "PGQ_'{.k15", 'Z"^w=P&3{R', 'yMGR[g_65$', "4.)Q7$COd'", 'WTptgYS$Nj', 'Ra$4Lrvu2)', ',V$z.C8>L(', '/YwfR#ZuM@', '>~){Q7ayUo', 'Ol]54z|a;\\', 'Dp80fV,\\-@', '[kB{he98&r', "E]$'Q@R-`0", 'm{qMBRD.p2', '=.Is;r>%/x', 'o7zS{DQ~Tx', 'hH:E{s?#Gt', 'WB]`%\\f.FT', 'Mbxu&8YEN_', '5Et+3dGAf%', 'k5#o_]2Y?T', '$K3(yD7wvJ', '^5kJ*Nn:jz', '8,q7/Oyb*3'] >>> >>> [''.join(random.sample(string.ascii_letters+string.digits*5,10)) for _ in range(30)] ['ugON2AoS10', '3E62mQ2sP8', 'sL76c4Ppyj', 'hS967O15bX', '7n8580rq01', 'B75C178051', '8Mvc0g52wd', 'Zv08H3GED8', '158F1Kd36o', '914FM222TK', 'n5I5aqY66h', '91Tz8P5yMf', '22K9tPLoHn', 'gR5862BZj9', '319pO53389', 'z31R67r811', 'E1duG7mzPS', 't6kx344cCU', '3b66u5yOc3', '387s3bj031', 'J665322viO', 'N4Y76QmfO9', '9d4038O7fD', '2lQ8D41z3G', 'l03P7146G4', 'n716wj2b9c', '4av2g6dDb7', '6q65ro2z43', 'LJC77i56xq', 'hHBGA547a5'] >>>
os.urandom()的源代码暂时没找到,只好另找头绪。后又在我的硬盘上找到一个旧版本的 random.py 文件,其中random()函数是用time.time()产生的,简化后的代码如下:
>>> def random1(): import time a = int(time.time() * 256000) a, x = divmod(a, 30268) a, y = divmod(a, 30306) a, z = divmod(a, 30322) x, y, z = int(x)+1, int(y)+1, int(z)+1 x = (171 * x) % 30269 y = (172 * y) % 30307 z = (170 * z) % 30323 return (x/30269.0 + y/30307.0 + z/30323.0) % 1.0 >>> for i in range(10): print(random1()) 0.30599469339556284 0.12074854519943568 0.7181253994067105 0.3098529094004334 0.9072297636077082 0.10198347202225788 0.6993603262295327 0.9054386353990269 0.5084648338198536 0.10019234381357656 >>> >>> for i in range(10): print(round(random1()*9+1)) 2 2 7 7 4 9 9 5 2 2 >>>
同样,用time.time_ns()加以改造也可以产生伪随机数来:
>>> import time >>> for i in range(10): print(time.time_ns()//1000%10**5/10**5) 0.74003 0.89627 0.89627 0.05256 0.2088 0.2088 0.36505 0.52129 0.67755 0.67755 >>>
那么问题又来了:选择什么样的常量可以更好地生产随机数?
选择不好会产生相同的数字,在上面的测试中出现有3对相同数字,显然就用几个10的几次方作计算常量是不合格的。后在知乎上找到了答案,先看一段javascript脚本:
function rnd( seed ){ seed = ( seed * 9301 + 49297 ) % 233280; //为何使用这三个数? return seed / ( 233280.0 ); }; function rand(number){ today = new Date(); seed = today.getTime(); return Math.ceil( rnd( seed ) * number ); }; myNum=(rand(5));
改变成python代码:
>>> from time import * >>> rnd=lambda:(int(str(time_ns())[10:-3])*9301+49297)%233280/233280 >>> >>> rnd() 0.24925411522633745 >>> rnd() 0.8790166323731139 >>> rnd() 0.5397505144032921 >>> rnd() 0.3207733196159122 >>> rnd() 0.9701517489711934 >>> >>> for i in range(10): print(rnd()) sleep(0.01) 0.4546467764060357 0.38059842249657067 0.35781464334705076 0.33503086419753086 0.27237654320987653 0.28946330589849106 0.2666795267489712 0.2438957475994513 0.22111196844993142 0.19832818930041152 >>>
为什么要用9301、49297、233280这三个常量呢?
理论有点高深,直接引用部分答案来作收尾吧,再搞下去脑瓜疼 ^_^
伪随机数生成器叫做线性同余生成器(LCG, Linear Congruential Generator),几乎所有的运行库提供的rand都是采用的LCG,形如:
X_{n+1} = a ( X_{n} + c )\,\, mod\, \, m
生成的伪随机数序列最大周期m,范围在0到m-1之间。
要达到这个最大周期,必须满足:
1.) c与m互质
2.) a - 1可以被m的所有质因数整除
3.) 如果m是4的倍数,a - 1也必须是4的倍数
以上三条被称为Hull-Dobell定理。
作为一个伪随机数生成器,周期足够大是基本要求之一。
可以看到,a=9301, c = 49297, m = 233280这组参数,以上三条全部满足。
遗留一个奇怪的问题:用time.time()写的自定义随机函数用在列表推导式中,会得到同一随机值。可能机器时间间隔太小以至于产生的时间值全部相同。用了循环语句加一个time.sleep()就可以出不同的数,但连续取数时离散性还是不够。为什么?
哪位达人可以解答这个问题?请留言,谢谢!