python_伪随机数算法实现
(一). 线性同余法 生成伪随机数_算法
1.线性同余法原理:(见下图)
2.示例:(a=12,c=8,m=22,X0=6)
{14,0,8,16,2,10,18,4,12,20,6…} 利用线性同余法产生此随机序列,序列周期为11
3.代码实现
def random1(): global x0 x0 = x0 * a + c #线性同余法规则 return int(x0 % m)if __name__=='__main__': a = int(input("请输入a(0=<a<m):")) c = int(input("请输入c(0=<c<m):")) m = int(input("请输入m(m>0):")) x0 = int(input("请输入x0(0=<x0<m):")) r= [] for i in range(0,50): #生成计算50次范围内 r.append(random1()) if r[0] == r[i] and i!=0: print("周期:",i) break print(r[i])
演示
a=1103515245 , c =12345 , m=666 , x =222
4.小结
各位童鞋在利用此算法生成随机数序列时需注意一点,就是序列周期,有可能会大于你所划定的计算次数,此时就会出现序列周期为0的情况,所以各位童鞋在使用时尽量将计算次数选大一点(图中我选的是50次)
(二).BBS伪随机数比特产生器
1.原理
寻找两个大素数p, q, 满足 p ≡ q ≡ 3(mod 4)
设n=pq, 找一个随机数s(这里我们称之为种子seed), s和n互素,即gcd(s,n)=1,令 X0 = s^2 mod n(如下图所示)
2.示例:(p=101,q=409,s=101009)
3.代码实现
def bbs(n,s): x = [] x.append(s**2%n) B = [] for i in range(1,100): #设定产生100个随机比特位 num = x[i-1]**2%n x.append(num) B.append(x[i]%2) print(B) if __name__=='__main__': p=int(input("请输入p(素数):")) q=int(input("请输入q(素数):")) s=int(input("请输入s(s与p*q互素):")) bbs(p*q,s)
演示
p= 157 ,q = 409 , s = 101197