计算机科学

首页 > 计算机科学

伪随机性

2018-08-23 10:22:01     所属分类:理论计算机科学

伪随机性英语:Pseudorandomness)是一个过程似乎是随机的,但实际上并不是。例如伪随机数是使用一个确定性的算法计算出来的似乎是随机的数序,因此伪随机数实际上并不随机。在计算伪随机数时假如使用的开始值不变的话,那么伪随机数的数序也不变。伪随机数的随机性可以用它的统计特性来衡量,其主要特征是每个数出现的可能性和它出现时与数序中其它数的关系。伪随机数的优点是它的计算比较简单,而且只使用少数数值很难推算出计算它的算法。一般人们使用一个假的随机数,比如计算机上的时间作为计算伪随机数的开始值。

目录

  • 1 计算机伪随机数函数
    • 1.1 C语言
  • 2 使用
  • 3 参见
  • 4 延伸阅读
  • 5 外部链接

计算机伪随机数函数

用来计算伪随机数的函数被称为随机函数,使用随机函数产生随机数的算法称为随机数生成器。一些随机函数是周期性的,虽然一般来说使用非周期性的函数要好得多,但周期性的随机函数往往快得多。有些周期函数的系数可以调整,之后它们的周期非常大,基本上与非周期的函数效果一样。

C语言

/* 使用 ANSI C 可移植算法 */
static unsigned long int next = 1;    // 种子

int rand(void)                        // 生成伪随机数
{
    next = next * 1103515245 + 12345;
    return (unsigned int) (next / 65536) % 32768;
}

void srand(unsigned int seed)         // 修改种子
{
    next = seed;
}

可见,伪随机数是由一套产生随机数的算法实现的。

使用

在计算机模拟中伪随机数用来模拟产生随机的过程,背景噪声产生器中也可应用伪随机数。由于伪随机数不是真的随机数,在有些方面它们不能被使用,例如在密码学中使用伪随机数要小心,因为其可计算性是一个可以攻击的地方。统计学、蒙特·卡罗方法上使用的伪随机数也必须挑选周期极长、随机性够高的随机函数,以确保计算结果有足够的随机性。

伪随机数的一个特别大的优点是它们的计算不需要外部的特殊硬件的支持,因此在计算机科学中伪随机数依然被使用。真正的随机数必须使用专门的设备,比如热噪信号、量子力学的效应、放射性元素的衰退辐射,或使用无法预测的现象,譬如用户按键盘的位置与速度、用户运动鼠标的路径坐标等来产生。对于移动式计算,采用加速度传感器协助随机数生成亦是一种普遍做法。

参见

  • 线性同余方法
  • 平方取中法
  • M-sequence
  • 梅森旋转算法
  • 伪随机数二进制数列

延伸阅读

  • Donald E. Knuth (1997) The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition). Addison-Wesley Professional, ISBN 0-201-89684-2
  • Oded Goldreich. (2008) Computational Complexity: a conceptual perspective. Cambridge University Press. ISBN 978-0-521-88473-0.(Limited preview at Google Books)
  • Salil P. Vadhan. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science: 1–336. [2018-04-02]. doi:10.1561/0400000010. 

外部链接

  • HotBits: Genuine random numbers, generated by radioactive decay
  • Using and Creating Cryptographic-Quality Random Numbers
  • In RFC 1750, the use of pseudorandom number sequences in cryptography is discussed at length.
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/339242.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


上一篇:伪多项式时间
下一篇:权益证明
广告
相关推荐
爱淘宝