[选译]关于随机函数发生器的简单讨论

（[tc]不是翻译人员，这篇包含个人感情的东西仅供参考）

　　今天有幸看到DONALD E. KNUTH先生的《THE ART OF COMPUTER PROGRAMMING》SECOND EDITION，第2卷：Seminumerical Algorithms，第1部分论述的是随机函数。揭示了[tc]几天前用到的自定义随机函数。
　　其中最简单的函数莫过于Linear Congruential Method，以下译为“线性余数法”。

　　线性余数法1949年发明于D. H. Lehmer，定义了下面的迭代函数，产生一个序列，用于简单的计算机（伪）随机序列：
　　Xn+1 = (aXn + c) mod m,n>=0
　　其中X0为“种子”。对于常数X0,a,c,m的选取，原作进行了详细的讨论，选译如下。

　　定义b=a-1
　　可证a>=2, b>=1时
　　X n+k = (a^k Xn + (a^k - l)c/b) mod m, k >= 0, n >= 0,

定理A：当且仅当m,a,c,X0满足下列条件时，具有长度为m的周期：
1、c与m为互质数
2、b=a-1是p的倍数，p为m的一切质因子
3、如果m是4的倍数，那么b也是
证明稿据说起源于100年前的定理，M.Greenberger将之推广到m=2^e。证明过程反正我也没看懂就不译了。

定理B：令λ(p^e) = (p-1) p^(e-1) , p>2
当c=0时能达到的最大周期是λ(m)。该周期满足下列条件时可以达到。
1、X0与m为互质数
2、a是模m的素元（[tc]：素元是指整环R中的非零非可逆元素。如果p能整除R中某两个元素的乘积（如ab），则必整除其中一个（如p|a或p|b））

问题在于：如何寻找模m的素元？于是：
定理C：满足下列条件之一时，数a是模p^e的素元
1、p^e=2,a为奇数；或者p^e=4,a mod 4=3；或者p^e=8,a mod 8=3,5,7；或者p=2,e>=4,a mod 8=3,5
2、p为奇数，e=1,a<>0(mod p),a^(p-1)<>1(mod p)
3、p为奇数，e>1，a满足第二条，a^(p-1)<>1(mod p^2)
正定理可用于计算机中较大的p的试验

定理D：如果m=10^e,e>=5,c=0,X0不是2或5的倍数，线性余数法周期为5*10^(e-2)。当且仅当a mod 200=下列数之一：
3,11,13,19,21,27,29,37,53,59,61,67,69,77,83,91,109,117,123,131,133,139,141,147,163,131,173,179,181,187,189,197

小结：
　　满足上述要求的a=z^k+1,2<=k<=e
　　若取c=1，则：Xn+1=((z^k+1)Xn+1)mod z^e
（[tc]：这一部分的论述，我认为原作所用的计算方法已经过时了，没有摘抄）

若设X0=0，那么再次出现0可认为是一个周期，所以有
　　Xn=((a^n-1)*c/b) mod m
并且，用二项式展开式展开a^n-1=(b+1)^n-1，化简得：
Xn=c(n+[n,2]b+...+[n,s]b^(s-1))mod m
（[tc]：其中比b^s更高阶的项由于是m的整数倍，被忽略了。式中的[n,2]是排列组合公式）。
（1）基数为1：a=1。Xn=cn(mod m)，显然不随机
（2）基数为2：Xn=cn+cb (n,2)，也不够随机。
(Xn, X(n+1), X(n+2))总是依赖于d+m,d-m,d,d-2m四个位面
（3）基数为3：序列开始比较随机，但是在Xn, X(n+1), X(n+2)中存在高阶相关性。试验表明序列效果一般
总之，基数到达5，看起来才足够随机。

　　例如：m=2^35,a=2^k+1。那么b=2^k。此时k>=18时b^2=2^(2k)是m的倍数，基数为2。如果k=17,16,...,12，基数为3。基数为4时k=11,10,9。因此k<=8，即a<=257.
稍后将会看到，小的乘积因子有可能被忽略。这样我们就排除了所有的成绩因子的取值。

　　假设w是计算机字长，m=w+1或w-1，那么基本上m不可能是质数的大的倍数，较高的基数也是不可能的。因此最大的周期是无法达到的。这就是为什么（当初会提出）c=0。
另外值得强调的是，大的基数也不是必要的。

-----------------------------------------
看到这里，来分析一下[tc]用过的随机函数。
（1）VC++（VS 2005）
　　X0=0, a=214013/(2^17)=3.266, c=2531011/(2^17)=38.620, m=0x7fff=32767
　　这个，OTL，居然是小数，不知道怎么分析。

（2）VB6
　　X0=327680, a=0x43fd43fd=1140671485, c=0xc39ec3=12820163, m=0xffffff+1=16777216
　　
应用定理A：
（1）
12820163的因子为：1, 2293, 5591, 12820163
16777216的因子为：1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216
的确互质。
（2）
1140671485-1的质因子为：2
满足条件。

应用定理B：
327680的因子为：1, 2, 4, 5, 8, 10, 16, 20, 32, 40, 64, 80, 128, 160, 256, 320, 512, 640, 1024, 1280, 2048, 2560, 4096, 5120, 8192, 10240, 16384, 20480, 32768, 40960, 65536, 81920, 163840, 327680
可见X0与m不互质，不过这个不影响。

m=2^24
p=2
e=24
1140671485 mod 8 =5
满足素元要求。

所以这组数据可以满足随机函数要求。