精华内容
下载资源
问答
  • 随机数生成器与线性同余法产生随机数 1、随机数生成器与/dev/random: 随机数生成器,顾名思义就是能随机产生数字,不能根据已经产生的数预测下次所产生的数的“器”(器存在软件与硬件之分),真正的随机数生成器...

    随机数生成器与线性同余法产生随机数

    1、随机数生成器与/dev/random:

    随机数生成器,顾名思义就是能随机产生数字,不能根据已经产生的数预测下次所产生的数的“器”(器存在软件与硬件之分),真正的随机数生成器其产生的随机数具有随机性不可预测性不可重现性

    什么是真正的随机数生成器?指的是由传感器采集设备外部温度、噪声等不可预测的自然量产生的随机数。比如Linux的/dev/random设备文件其根据设备中断(键盘中断、鼠标中断等)来产生随机数,由于鼠标的操作(移动方向、点击)是随机的、不可预测的也是不可重现的,所以产生的随机数是真随机数。/dev/random即所谓的随机数池,当通信过程(如https安全套接层SSL)需要加密密钥时,就从随机数池中取出所需长度的随机数作为密钥,这样的密钥就不会被攻击者(Attacker)猜测出。但是由于/dev/random是采集系统中断来生成随机数的,所以在无系统中断时,读取/dev/random是处于阻塞状态的,如下所示(鼠标移动与否决定了cat /dev/random的显示结果,cat /dev/random | od -x先显示的4行是查看该设备文件前,系统中断被采集而产生的随机数,而之后的随机数则是鼠标移动锁产生的随机数):

    这里写图片描述

    cat读取/dev/radom测试效果.gif

     

    在Linux上还存在随机数生成器/dev/urandom,而读取该随机数池是不会阻塞的,因为其不受实时变化的因素影响,所以/dev/urandom是一个伪随机数生成器,而C语言的rand()库函数所产生的随机数也是伪随机数。/dev/random与/dev/urandom的区别在于一个阻塞一个非阻塞,一个更安全一个较安全。对于/dev/random来说,如果需要的随机数长度小于随机数池中的随机数,则直接返回获取到的随机数,并且池中的随机数长度减去获取长度,如果要获取的随机数长度大于池中已有的长度,则获取的进程处于阻塞状态等待新的生成的随机数部分注入池中。

    2、伪随机数生成器:

    所谓伪随机数生成器,指的是其生成的数在特定条件下是具有真随机数的特性的。伪随机数采用“软件算法+随机数种子”的方式来实现,算法一般不保密,而种子则必须要保密,其基本结构如下所示:

    这里写图片描述 

    (图1)伪随机数生成器结构图

     

    所谓种子类似于密码算法中的加密密钥,不同的种子(密钥)对应不同的随机数(密文)。内部状态指的是每一个状态下,随机数生成器中的数值状态,初始状态则是由种子来决定的。而将内部状态计算伪随机数的方法和内部状态改变的方法组合起来就是伪随机数生成器的算法

    3、rand()函数采用的随机数生成器算法:

    rand()函数是C语言的库函数,其产生随机数的算法为线性同余法(linear congruential method),其遵循“算法+种子”的伪随机数生成器结构,线性同余法的具体结构如下图所示:

    这里写图片描述

    (图2)线性同余法算法结构图

     

    其基本伪代码为:

    M = 正整数;
    A = 大于0且小于M的正整数;
    C = 大于0且小于M的正整数;
    内部状态 = 种子seed;
    while(true){
        伪随机数 = (A × 内部状态 + C) mod M;
        内部状态 = 伪随机数;
        输出伪随机数;
    }
    •  

    对于rand()函数来说,其种子seed常用当前时间戳(srand(time(NULL));)。由于对M取余,所以该随机数具有周期性,而M的大小决定了周期长短(M-1),而A和C也会影响周期(使得周期小于M-1),A、C、M的取值决定了产生的数是否具有不可预测性。比如当A=1,C=0,M=7时,产生的数只能是seed%7,周期为1。不具备随机数特征。所以A、C、M的选取是否得当十分重要(关于A、C、M、seed的取值如何才能比较好,可参考http://blog.csdn.net/memray/article/details/8932518)。

    4、rand()与srand()函数代码实现:

    srand()函数只是用种子初始化内部状态,因为srand()与rand()中都会对内部状态进行改变,所以内部状态的变量需要定义为静态全局变量。

    VC中对于rand()的实现为:

    //文件位置C:\Program Files\Microsoft Visual Studio\VC98\CRT\SRC\rand.c
    #include <cruntime.h>
    #include <mtdll.h>
    #include <stddef.h>
    #include <stdlib.h>
    
    #ifndef _MT
    //MT为multithread(多线程)的缩写
    //如果不是多线程则定义holdrand为内部状态变量
    static long holdrand = 1L;
    #endif  /* _MT */
    
    
    void __cdecl srand (unsigned int seed)
    {
        #ifdef _MT
            _getptd()->_holdrand = (unsigned long)seed;//线程中分别初始化
        #else
            holdrand = (long)seed;
        #endif
    }
    
    /**************************************************
    其中:A=214013、C=2531011、M=65536(2^16)
    在这里C=7 x 17 x 21269因此C与M是互为质数的,但是M比A和C都小,所以产生的随机数周期小于M
    holdrand最初是seed,经过rand()之后holdrand就变为(holdrand × A + C) mod M
    ***************************************************/
    
    int __cdecl rand (void)
    {
        #ifdef _MT
            _ptiddata ptd = _getptd();//在不同线程中获取各自的内部状态,避免混淆
            return( ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) & 0x7fff );
        #else
            return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
        #endif
    }
    •  

    线性同余法只是常用在编程语言函数库中产生随机数(VC中的库函数是比较简单的版本,但是比较容易理解,glibc-2.21中的实现更为复杂,可参考http://ftp.gnu.org/gnu/glibc/glibc-2.21.tar.gz中glibc-2.21/stdlib/目录下的rand.c、rand_r.c和random.c、random_r.c),但是不适用于加密密钥的生成。因为当被攻击者获取到某些随机数之后,其种子seed以及A、C、M都会被反向计算出来,即有可能根据以往随机数预测出之后还未产生的随机数。而使用单向散列函数法(单向性作为不可预测的基础)、密码法(保密性作为不可预测的基础)、ANSI X9.17方法(PGP加密软件使用的伪随机数生成器算法,也是采用加密方式来确保随机数的不可预测性)的随机数生成器来确保随机数的不可预测性。

    参考资料:《图解密码技术》

    转自:https://blog.csdn.net/Apollon_krj/article/details/78718598

    展开全文
  • 线性同余方法(LCG)是个产生伪随机数的方法。它是根据递归公式:其中是产生器设定的常数...线性同余算法有m 、a 、c 和X0 4个参数,通过置Xn + 1 ≡aXn + c (mod m) ,求得随机数序列< Xn > , 这个序列称作线性同...

    线性同余方法(LCG)是个产生伪随机数的方法。

    它是根据递归公式:

    a08759df1391746a1d696d7d28f250ab.png

    其中

    4b79b4979b727252f6da724a53d72dde.png是产生器设定的常数。

    LCG的周期最大为

    d77481f824b37cfd3268543e11e249c2.png,但大部分情况都会少于M。要令LCG达到最大周期,应符合以下条件:

    d77481f824b37cfd3268543e11e249c2.png的所有质因子的积能整除

    f9db9c9606c0b0ad625c25c3c0b07d9c.png

    d77481f824b37cfd3268543e11e249c2.png是4的倍数,

    f9db9c9606c0b0ad625c25c3c0b07d9c.png也是;

    d45bd85b13c0367bde00bf39169713c9.png都比

    d77481f824b37cfd3268543e11e249c2.png小;

    d3e10928cf5902811a9c945a5101e897.png是正整数。

    线性同余算法有m 、a 、c 和X0 4个参数,通过置Xn + 1 ≡aXn + c (mod m) ,求得随机数序列< Xn > , 这个序列称作线性同余序列。m、a 、c 和X0 分别称做模数、乘数、增量和初始值。线性同余方法速度快,如果对乘数和模数进行适当的选择,可以满足用于评价一个随机数产生器的3 种准则:

    1.这个函数应该是一个完整周期的产生函数。也就是说,这个函数应该在重复之前产生出0 到m之间的所有数;

    2.产生的序列应该看起来是随机的;

    3.这个函数应该用32bit 算术高效实现。

    在我的算法中,a=7^5;c=0;m=2^31-1; x0为系统时间;

    我的代码如下:

    #include 

    #include 

    static unsigned long rand_seed;

    void mysrand (unsigned long int);

    void myrand ();

    int

    main (void)

    {

    int i;

    mysrand (time (NULL));

    for (i = 0; i 

    {

    myrand ();

    }

    return 0;

    }

    void

    mysrand (unsigned long seed)

    {

    rand_seed = seed;

    }

    void

    myrand ()

    {

    rand_seed = (rand_seed * 16807L) % ((1 <

    printf ("%ld ", rand_seed);

    }

    ===============PS==================

    产生随机种子的方法很多,目前用得比较多的是使用系统时间为种子。我觉得这种方法也不妥当。假如我批量执行程序,程序执行的时间是几个ms,那么几个相邻程序的种子就是一样的,产生的结果因此也是一样的。(因为系统时间是按照秒来计算的,一秒内执行多少次,产生的随机种子就有多少相同的。)

    比较流行的是使用seed = (seed * 9301 + 49297) % 233280;

    return seed /(233280.0);

    展开全文
  • 线性同余法生成随机数

    千次阅读 2020-01-09 12:44:39
    线性同余法生成随机数 以当前时间作为随机种子,生成30个0-1的随机数 srand()函数产生一个以当前时间开始的随机种子.应该放在for等循环语句前面 不然要很长时间等待 #include <stdio.h> #include <...

    线性同余法生成随机数

    以当前时间作为随机种子,生成30个0-1的随机数
    srand()函数产生一个以当前时间开始的随机种子.应该放在for等循环语句前面 不然要很长时间等待

    #include <stdio.h>
    #include <iostream>
    #include <time.h>
    using namespace std;
    int main(int argc, char* argv[])
    {
     int  MAX = 2;
     srand((unsigned)time(NULL));//srand()函数产生一个以当前时间开始的随机种子.应该放在for等循环语句前面 不然要很长时间等待
     for (int i = 0; i < 30; i++)
     {
      cout << rand() % MAX << endl;//MAX为最大值,其随机域为0~MAX-1
     }
     return 0;
    }

    结果显示

    第一次显示

    在这里插入图片描述
    第二次运行
    在这里插入图片描述

    展开全文
  • 线性同余法随机数

    千次阅读 2016-07-01 23:16:36
    线性同余法求伪随机数,Linear-Congruential: (a * x + c) % m, a > 0, m > 0, m % a 首先,说明一下取随机数一般会用rand函数,取time.h文件中的clock()作为种子,产生我们需要的随机数 #include #...

    线性同余法求伪随机数,Linear-Congruential: (a * x + c) % m, a > 0, m > 0, m % a < m / a.


    首先,说明一下取随机数一般会用rand函数,取time.h文件中的clock()作为种子,产生我们需要的随机数


    #include <stdio.h>
    #include <stdlib.h> //srand()、rand()
    #include <time.h> //time();
    int main() {
        int n;
        srand((unsigned)time(NULL)); //设置随机数种子
        for (int i= 0; i< 10; i++) {
    	n = (rand() % 10) + 1 ;//产生1~10的随机数
        //rand()产生的是一个很大的数,对其求余就可以达到限定范围的目的
        printf("%d ", n);
    }
        return 0;
    }
    

    但是如果我们产生随机数种子的周期小于1s,那么就会产生一系列相同的随机数。总而言之,当产生随机数的周期非常非常小时,用<time.h>已无法满足这一需求。因此,我们采用线性同余法,也就是较为简便的方法,那就是用现有的随机数种子来产生新的种子,也就是Linear-Congruential generator(线性同余数发生器)。

    它是根据递归公式:

    seed = (a*seed) mod m;
    or
    seed = (a*seed + c) mod m;
    
    这条公式需要满足:
    a, m为正整数,m> a, m> seed;

    它产生的随机数是以m为周期的,一般我们以2^32- 1为周期,a又不能取太大,所以为了避免取模溢出,

    我们用一种方法解决:

    Schrage’s Method Revealed算法,将公式形式变换,避免了溢出。

    x = (a*x) mod m
    = a*(x mod Q) - R*[xi/Q];
    if (x > 0) result_seed = x;
    else result_seed = x + m;
    具体实现:

    random_my.h文件

    namespace RAND_GEN {
    class mod_my {
      public:
        long long m, a, c;
        mod_my(long long _m, long long _a, long long _c) : m(_m), a(_a), c(_c) {}
     
        //  General case for x = (ax + c) mod m -- use Schrage's algorithm
        //  to avoid integer overflow.
        //  (ax + c) mod m can be rewritten as:
        //    a(x mod q) - r(x / q)  if >= 0
        //    a(x mod q) - r(x / q)  otherwise
        //  where: q = m / a , r = m mod a
        //
        //  Preconditions:  a > 0, m > 0.
        //
        //  Note: only works correctly for m % a < m / a.
        long long calc(long long x) {
            if (a == 1) {
                x %= m;
            } else {
                long long q = m / a;
                long long r = m % a;
                long long t1 = a * (x % q);
                long long t2 = r * (x / q);
                if (t1 >= t2) x = t1 - t2;
                else x = m - t2 + t1;
            }
            if (c != 0) {
                const long long d = m - x;
                if (d > c) x += c;
                else x = c - d;
            }
            return x;
        }
    };
     
    class linear_congruential_engine_my {
      public:
        long long multiplier, increment, modulus;
        unsigned long long default_seed_my, seed_my;
        mod_my mod_temp;
     
        linear_congruential_engine_my()
        : multiplier(16807), increment(1), modulus(2147483647)
        , default_seed_my(1u), mod_temp(modulus, multiplier, increment)
        { seed(default_seed_my); }
     
        linear_congruential_engine_my(long long _m, long long _a,
        long long _c, long long _s)
        : multiplier(_a), increment(_c), modulus(_m)
        , default_seed_my(_s), mod_temp(modulus, multiplier, increment)
        { seed(default_seed_my); }
     
        void seed(unsigned long long s)
        { seed_my = s; }
     
        long long min()
        { return  increment == 0u ? 1u : 0u; }
     
        long long max()
        { return modulus - 1u; }
     
        void discard(unsigned long long z)
        { for (; z != 0ULL; --z) (*this)(); }
     
        long long operator()() {
            seed_my = mod_temp.calc(seed_my);
            return seed_my;
        }
    };
     
    }
    main.cpp

    #include <iostream>
    #include "random_my.h"
    using namespace std;
    using namespace RAND_GEN;
     
    void test_calc() {
        mod_my mod_1(9223372036854775807, 16807, 1);
        if (mod_1.calc(9223372036854775) != 7443261233741790514 ||
            mod_1.calc(922337203685477580) != 6456360425798331301 ||
            mod_1.calc(9223372036852222220) != 9223371993936639099 ||
            mod_1.calc(922337203685473330) != 6456360425726901551 ||
            mod_1.calc(9223372022254775806) != 9223126654654759001)
            cout << "Your calc() is wrong.\n";
        else cout << "Pass all tests for calc().\n";
    }
     
    void test_engin() {
        linear_congruential_engine_my lce;
        int count = 1000;
        int num[1001] = {0};
        while (count--) num[lce()%5]++;
        if (num[0] != 216 || num[1] != 190 ||
            num[2] != 203 || num[3] != 216 ||
            num[4] != 175) {
            cout << "Your engin class is wrong in generator.\n";
            return;
        } else if (lce.min() != (lce.increment == 0u ? 1u : 0u)) {
            cout << "Your engin class is wrong in min().\n";
            return;
        } else if (lce.max() != (lce.modulus - 1u)) {
            cout << "Your engin class is wrong in max().\n";
            return;
        }
        else cout << "Pass all tests for class engin.\n";
    }
     
    void hard_test() {
        long long m, a, c, n, num[5] = {0};
        unsigned long long s;
        unsigned long long discard_n;
        cin >> m >> a >> c >> s;
        mod_my mod_1(m, a, c);
        for (int i = 0; i < 5; i++) {
            cin >> n;
            cout << "(MOD CALC) ";
            cout << n << ": " << mod_1.calc(n) << endl;
        }
        linear_congruential_engine_my lce(m, a, c, s);
        cin >> discard_n;
        lce.discard(discard_n);
        cin >> n;
        while (n--) num[lce()%5]++;
        for (int i = 0; i < 5; i++) {
            cout << "(ENGIN) ";
            cout << i << ": " << num[i] << endl;
        }
    }
     
    int main() {
        int t;
        cin >> t;
        if (t == 0) {
            test_calc();
            test_engin();
        } else {
            hard_test();
        }
        return 0;
    }





    展开全文
  • 随机数在概率算法中扮演着重要的作用,在现实的计算机系统无法产生真正的随机数,因此概率算法在实际中使用...线性同余法是经典的随机数产生算法,详细介绍请参照计算机算法设计与分析>>,王小东著. 本代码是用matlab开发的
  • 上篇博客中,我们了解了基于物理现象的真随机数生成器,然而,真随机数产生速度较慢,为了实际计算需要,计算机中的随机数都是由程序算法,也就是某些公式函数生成的,只不过对于同一随机种子与函数,得到的随机数列...
  • 线性同余法产生1000个随机数

    千次阅读 2017-10-13 21:54:00
    设计思路:根据同余法产生随机数线性同余算法有m 、a 、c 和X0 4个参数,通过置Xn ≡aXn + c (mod m) ,求得随机数序列< Xn > , 这个序列称作线性同余序列。m、a 、c 和X0 分别称做模数、乘数、增量和初始值。从...
  • 线性同余法产生(0,1)均匀分布的随机数 原理 maltab代码 clear all close all clc a=16807; c=0; M=2^32; X(1)=10^4; N=4096; for n=1:N-1 X(n+1)=mod(a*X(n),M); end X=X/(M-1); figure(1) plot(X) ...
  • 利用线性同余法随机数,也可称作利用线性同余法求伪随机序列. 线性同余法是一种求随机数的方法,它所求得得随机数的序列是成周期性,同时它是根据公式计算求得得随机数并非是由硬件产生随机数所以被称作伪随机序列...
  • 线性同余法生成“伪”随机数

    万次阅读 2013-05-15 21:41:39
    线性同余方法(LCG)是个产生伪随机数的方法。 它是根据递归公式: 其中是产生器设定的常数。 LCG的周期最大为,但大部分情况都会少于M。要令LCG达到最大周期,应符合以下条件: 互质;的所有质...
  • 而且产生的随机数序列质量会对仿真结果产生比较大的影响,因此如何在仿真中产生随机数也是一个值得研究的课题。事实上,通过计算机编程不可能实现真正的随机序列,因为产生的序列达到一定的长度后,会出现重复序列,...
  • 线性同余法

    2014-10-28 13:25:26
    线性同余方法是目前应用广泛的伪随机数生成算法,其基本思想是通过对前一个数进行线性运算并取模从而得到下一个数。...线性同余法的最大周期是m,但一般情况下会小于m。要使周期达到最大,应该满足以下条件
  • 线性同余法生成伪随机数 在计算机上可以用物理方法来产生随机数,但价格昂贵,不能重复,使用不便。另一种方法是用数学递推公式产生,这样产生的序列与真正的随机数序列不同,所以称为伪随机数或伪随机序列,只要...
  • ![图片说明](https://img-ask.csdn.net/upload/201810/30/1540860486_441255.png)
  • 伪随机数生成算法(1)线性同余法

    千次阅读 2014-04-29 09:05:22
    线性同随机数生成器介绍: 古老的LCG(linear congruential generator)代表了最好最朴素的伪随机数产生器算法。主要原因是容易理解,容易实现,而且速度快。  LCG 算法数学上基于公式: X(n+1) = ...
  • rand()函数实现原理:线性同余法

    万次阅读 2014-11-21 20:14:45
    关于“随机数”的产生有许多算法,但无论如何,都不可能产生真正的随机数,因为电脑程序是个确定状态转换机,一种输入必定产生一种确定的输出。  但要实现“不可预知”还是可以做到的,只需有“不可预知”的输入...
  • 计算机上可以用物理方法来产生随机数,但价格昂贵,不能重复,使用不便。另一种方法是用数学递推公式产生,这样产生的序列与真正的随机数序列不同,所以称为伪随机数或伪随机序列,只要方法和参数选择合适,所产生的...
  • 线性同余发生器-随机数

    千次阅读 2016-11-23 11:49:23
    简介 随机数在概率算法设计中是必须的。在计算机上无法产生真正的随机数,一般使用伪随机数发生器产生的伪随机数。 ...线性同余发生器:线性同余法产生的随机序列a1,a2,……,an,满足 1、a0=d; 2
  • 在新算法中,以原线性余发生器中的模数为基础,通过相同种子数平均分配构造产生随机数;由于算法分段实现,使得随机数的产生在计算量上不会有明显的增加,能满足购车摇号所需。统计检验结果表明,该算法对随机...
  • C++产生随机数

    2020-06-20 14:56:13
    目录C++产生随机数rand()srand()为了方便的使用我们可以用宏定义来替换 rand函数其他的随机数的范围...不过,由于rand()的内部实现是用线性同余法做的,所以生成的并不是真正的随机数,而是在一定范围内可看为随机
  • 如何产生随机数

    2020-11-19 22:39:55
    不过,由于rand()的内部实现是用线性同余法做的,所以生成的并不是真正的随机数,而是在一定范围内可看为随机的伪随机数。 rand() 单纯的rand()会返回一个0至RAND_MAX之间的随机数值,而RAND_MAX的值与int位数有关...
  • 文章目录1.随机数生成1.1 随机数发生器 rand()1.2 随机数种子2.时间记录2.1 clock()计时函数2.2 每秒的时钟单元数3....其形式 int rand(void) 内部使用线性同余法产生随机数,是“伪随机数”,只不...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 235
精华内容 94
关键字:

线性同余法产生随机数