重塑我们对随机性在计算中的作用的理解

2023年图灵奖，最近刚刚颁给普林斯顿数学教授 Avi Wigderson！作为理论计算机科学领域的领军人物，他对于理解计算中的随机性和伪随机性的作用，作出了开创性贡献。

Avi Wigderson 的履历

自 1999 年以来，Wigderson 一直担任普林斯顿高等研究院数学学院赫伯特-H-马斯教授。此前，他曾担任耶路撒冷希伯来大学教授，并在普林斯顿大学、加州大学伯克利分校、IBM 等机构担任客座教授。

Wigderson 毕业于以色列理工学院，并获得普林斯顿大学计算机科学硕士、MSE 和博士学位。

他获得的荣誉包括阿贝尔奖、IMU 算盘奖、唐纳德-E-克努特奖、Edsger W. Dijkstra 分布式计算奖和哥德尔奖。他是 ACM Fellow、美国国家科学院和美国艺术与科学院院士。

Avi Wigderson教授在计算复杂性理论的贡献

提示：Avi Wigderson教授在计算复杂性理论方面的工作是其获得图灵奖的主要贡献之一。他的研究不仅推动了理论计算机科学的发展，还对现代计算产生了深远的影响。

从根本上说，计算机是确定性系统；应用于任何给定输入的算法指令集唯一地决定了其计算，尤其是其输出。换句话说，确定性算法遵循的是一种可预测的模式。相比之下，随机性则缺乏明确的模式，或者说事件或结果缺乏可预测性。

由于我们生活的世界中充满了天气系统、生物和量子现象等随机事件，计算机科学家丰富了算法，允许它们在计算过程中做出随机选择，借此提高算法的效率。

事实上，许多没有已知高效确定性算法的问题，已经通过概率算法得到了高效解决，尽管存在一些小概率错误（可以有效减少）。

理解计算中随机性和伪随机性，加深对计算中随机性动态的理解，可以帮助我们开发出更好的算法，并加深我们对计算本身性质的理解。

从计算机科学诞生之初，研究人员就认识到，随机性是为各种应用设计更快算法的一种方法。为更好地理解随机性所做的努力将继续为我们的领域带来重要益处。

随机数，也即“随机选择的数”，是在一个有限数集上的一个一致分布的随机序列。随机数在许多方面有应用，如仿真、抽样、数值分析、计算机程序、娱乐等方面都有所应用。计算机用确定算法计算出来的随机数系列是伪随机数，并不是真正的随机数，但是其具有随机数的统计特征，如均匀性、独立性等。

在上世纪初，冯诺伊曼建议用平方，然后取结果中间的数据作为随机数(平方取中法)。结果看起来修似乎是随机的，但是很多人对此质疑。实际上这并不是好的随机方法，尤其是针对一些短循环序列。

计算机科学家发现了随机性与计算难度之间的显著联系（即确定没有高效算法的自然问题）。

在标准的、被广泛相信的计算假设下，每一种概率多项式时间算法都可以有效地去随机化（即完全确定）。

换句话说，随机性并不是高效计算的必要条件。这一系列著作彻底改变了我们对随机性在计算中的作用的理解，也改变了我们对随机性的思考方式。

这些影响深远的论文包括以下三篇：

1）“Hardness vs. Randomness”（与 Noam Nisan 合著）。除其他发现外，这篇论文还介绍了一种新型伪随机发生器，并证明了在比以前已知的假设更弱的条件下，随机算法的高效确定性模拟是可能的。

论文链接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

2）“BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs”（与 László Babai、Lance Fortnow 和 Noam Nisan 合著）这篇论文利用“hardness amplification”证明，在较弱的假设条件下，有界错误概率多项式时间（BPP）可以在亚指数时间内模拟无限多的输入长度。

论文链接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

3）“P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma”（与 Russell Impagliazzo 合著）这篇论文介绍了一种更强的伪随机发生器，它在硬度与随机性之间实现了基本最优的权衡。

论文链接：https://dl.acm.org/doi/pdf/10.1145/258533.258590

重要的是，这三篇论文的影响远远超出了随机性和反随机化领域。这些论文中的观点后来被应用于理论计算机科学的许多领域，并推动了该领域多位领军人物发表具有影响力的论文。后来，Wigderson 与 Omer Reingold、Salil Vadhan 和 Michael Capalbo 合作，仍然在计算随机性的广泛领域开展工作，在另一篇论文中首次提出了扩展图的高效组合构造，扩展图是一种稀疏图，具有很强的连通性。它们在数学和理论计算机科学领域都有许多重要应用。

论文链接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf

除了在随机性方面的研究之外，Wigderson 还是多验证器交互式证明、密码学和电路复杂性等理论计算机科学内多几个领域的领袖。

“伪”随机数生成器（PRNG）

具有任何编程经验的人都知道计算机是确定性机器。如果你提供相同的输入，则将始终获得相同的输出。这就是为什么让计算机偶然生成随机数比看起来复杂的多。

随机数应用在密码学到博彩，视频游戏等很多行业。但是，计算机天生就不能随机。相反，程序员依靠伪随机数生成器（PRNG），从称为种子/seed的给定起始值以编程方式生成新的随机数。

这些算法有其自身的局限性。由于随机数是通过程序生成的，因此，如果有人能够识别出使用的种子值和PRNG算法，他们将能够预测序列中的下一个随机数。这将使攻击者可以解密，预测序列中的下一张纸牌，在视频游戏中作弊等。

但是PRNG在涉及建模和仿真的情况下仍然非常有用，因为它允许通过使用相同的种子初始化随机数生成器来“重播”一系列随机事件。

“真”随机数生成器（TRNG）

在随机性第一的场景下，我们使用“真”随机数生成器（TRNG）。与具有任意种子值的PRNG不同，TRNG从其环境/外部数据中选择一个种子值。

以下是一些潜在的选择：

鼠标动作
风扇噪音
气压
自上一整秒以来的微秒数

只需要选择攻击者无法预测的种子即可。然后，该种子值将被传递到类似于PRNG的算法中，该算法将生成一个随机数。

两种方法之间的实际差异

PRNG比TRNG更快，PRNG的确定性在你要重播一系列“随机”事件的情况下非常有用。

此外，某些PRNG算出的随机数，本质上是周期性的，有一定的确定概率，但是使用好的初始化参数的现代PRNG，这个周期可以足够长。

相反，TRNG比PRNG慢，没有确定性，并且不是周期性的。

线性同余生成器

实现一个简单的PRNG。一个称为线性同余生成器（LCG）算法的变体。LCG以前是最常用和研究最多的PRNG之一。

这是LCG(linear congruential generator)的迭代算法：

由以下参数组成：

参数	m	a	c	X
性质	模数	乘数	加数	随机数
作用	取模	移位	偏移	作为结果

记录了一些常用的模数m，乘数a和增量值c。关于最佳值的建议尚无统一看法，因此各个实现之间存在不同的值。

LCG算法是如下的一个递推公式，每下一个随机数是当前随机数向左移动 log2 a 位，加上一个 c，最后对 m 取余，使随机数限制在 0 ~ m-1 内。

我们必须注意这些参数的取值。

X是随机数序列
m，0<m，模
a，0<a<m，乘子
c，0≤c<m，增量，也叫做偏移量
X0 , 0≤X0<m，开始值，通常叫做“种子”seed

选择错误的值可能会导致创建一个过短的周期，从而使我们的随机数生成器无用。

当c=0时候，LCG就变换成了乘法同余发生器，multiplicative congruential generator (MCG)， c≠0时叫做混合同余发生器，mixed congruential generator，MCG。

从该式可以看出，该算法由于构成简单，具有以下优点：

计算速度快
易于实现
易于写入硬件

上面的线性同余方程，选定a、X、c和m四个魔数，可以生成线性同余序列，线性同余序列在一个周期内存是随机的，独立的，一个周期完成之后，循环进行。
当m=9,a=2,c=0,seed=1时，得：
X 0 = s e e d = 1

X 2 = ( a ∗ X 1 + c ) m o d m = ( 2 × 1 + 0 ) % 9 = 2

X 3 = ( a ∗ X 2 + c ) m o d m = ( 2 × 2 + 0 ) % 9 = 4

X 4 = ( a ∗ X 3 + c ) m o d m = ( 2 × 4 + 0 ) % 9 = 8

X 5 = ( a ∗ X 4 + c ) m o d m = ( 2 × 8 + 0 ) % 9 = 7

X 6 = ( a ∗ X 5 + c ) m o d m = ( 2 × 7 + 0 ) % 9 = 5

X 7 = ( a ∗ X 6 + c ) m o d m = ( 2 × 5 + 0 ) % 9 = 1
在下图中，可以看到对参数的微小更改会极大地影响周期长度，m、a、c取值不同，其循环的周期长度是不同的，并且随机的效果也是不同的。

可以看出，针对不同的参数，lcg产生的效果差别很大。

m、a、c取值不同，其循环的周期长度是不同的。为了使得线性同余序列的周期长度达到最大m，需要满足以下3个条件：

m and c are relatively prime（互为质数，即两个数没有除1之外的公约数）
a-1 is divisible by all prime factors of m（m的质因数（可以整除m的所有质数），都能整除a-1，也即a-1是m的所有质因数的倍数）
a-1 is divisible by 4 if m is divisible by 4 (如果m被4整除，a-1也被4整除，即m是4的倍数，a-1也要是4的倍数）。

以下是针对不同环境下的参数选择：

//是质数
bool prime(int N)
{
	if (N < 2)
		return false;
	if (N == 2)
		return true;

	for (int i = 2; i < std::sqrt(N*1.0); i++)
	{
		if (N%i == 0) //i能被j整除，N不是质数
		{
			return false;
		}
	}

	return true;
}
//互质
bool isrp(int a, int b)
{
	if(a <=0 || b<=0 || a==b)
	{ // 互质整数不能小于或等于0
		return false;
	}
	else if(a==1 || b==1)
	{ // 两个正整数中，只有其中一个数值为1，两个正整数为互质数
		return true;
	}
	else
	{
		// 求出两个正整数的最大公约数
		while(1)
		{
			int t = a%b;
			if(t == 0)
			{
				break;
			}
			else
			{
				a = b;
				b = t;
			}
		}
		if( b > 1){ // 如果最大公约数大于1，表示两个正整数不互质
			return false;
		}else{ // 如果最大公约数等于1,表示两个正整数互质
			return true;
		}
	}
}
// 所有质因数
class QualityFactor
{
public:
	vector<int> m_vInt;
public:
	void QFContract(long a) //用短除法对合数进行分解
	{
		while(a>1)
		{
			for(int i=2;i<=a;i++)
			{
				if(a%i==0) //短除法
				{
					a = a/i;
					if (std::find(m_vInt.begin(), m_vInt.end(), i) == m_vInt.end())
						m_vInt.push_back(i);
					break;
				}
			}
		}
	}
}
// 所有质因数整除
int MaxCommondMultiple(const vector<int>& _vInt, BOOL _bFour, int _nSrc)
{
	int nCommonMultiple = 1;
	while (nCommonMultiple < _nSrc)
	{
		for (auto it = _vInt.begin(); it != _vInt.end(); ++it)
		{
			nCommonMultiple*= *it;

			if (_bFour && (nCommonMultiple%4 != 0))
			{
				continue;
			}

			BOOL bFind = TRUE;
			for (auto it = _vInt.begin(); it != _vInt.end(); ++it)
			{
				if (nCommonMultiple % *it != 0)
				{
					bFind = FALSE;
					break;
				}
			}

			if (bFind)
			{
				return nCommonMultiple;
			}
		}
	}

	return 0;
}
// 随机数函数
static int seed = 0;
int random(int a, int b, int m)
{
	seed = (seed * a + b) % m;
	return seed;
}

//输入最大周期长度m，即可以根据上述函数生成相应的a和c。

代码实现

使用早期C语言标准（C90 / C99 / ANSI C和C11）中记录的值去实现。

随机数在概率算法设计中是必须的。在计算机上无法产生真正的随机数，一般使用伪随机数发生器产生的伪随机数。
伪随机数发生器是一个算法，产生的数列元素之间近似相互独立，多数力图产生的样本同分布。
常用的伪随机数发生器：线性同余发生器、滞后Fibonacci发生器、线性反馈移位发生器、广义反馈移位发生器等。

m、a、c、X是一级相关数，选定m之后，同样会有很多组对应的a、c、X。不同的数据，对应的随机数分布是不一样的。随机效果也是大大不同。理论上m选择的范围越方，其效果越好。而VS实现的std::rand()即是采用线性同余方程实现的。其周期较小，所以随机效果不是特别好。另外其中的几个常数，是经常大量实验选择的，是随机效果相对较好的一组数。
线性同余发生器：线性同余法产生的随机序列 a1,a2,……，an，满足
1、a0=d; 其中d称为种子。
2、an=(b*a(n-1)+c) mod m，n=1,2,……，b ≥ \geq≥ 0, c ≥ \geq≥ 0, d ≥ \geq≥ m 。

用此方程生成的一组序列，随机效果不错。线性同余方程生成的序列，被称为线性同余序列。线性同余序列在一个周期内重复出现。并且方程中有四个魔数(常数)，但是这四个魔数，对随机的效果影响巨大。线性同余发生器(Linear congruential generator,LCG)用于生成随机序列。
线性同余发生器一直是随机数生成的主要方式，但是其随机效果不是特别好。C++11引入了梅森旋转演算法的随机数引擎，是目前效果最好的随机算法。std::default_random_engine默认即使用梅森旋转演算法。也可以直接使用梅森旋转演算法引擎std::mt19937。

a = 1103515245

m = 2³¹

c = 12345

无论选择哪种PRNG算法，都应导致随机数的均匀分布和足够长的时间。

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

const unsigned long maxshort = 65536L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;

class RandomNumber
{
private:
    unsigned long randSeed;

public:
    RandomNumber(unsigned long s = 0);             //构造函数
    unsigned short randomInteger(unsigned long n); //产生0--n-1之间的随机整数
    double randomFloat(void);                      //产生[0,1)之间的随机实数
};

RandomNumber::RandomNumber(unsigned long s)
{
    if (s == 0)
    {                            //用系统时间产生种子
        time_t tm = time(NULL);  //获取系统时间
        srand((unsigned int)tm); //用来设置rand()产生随机数时的随机种子
        randSeed = rand();       //产生一个随机数值
    }
    else
    { //由用户定义随机数值
        randSeed = s;
    }
}
/*
    产生0--n-1之间的随机整数，用线性同余计算的新种子高16位随机性好，将其右移16位
*/
unsigned short RandomNumber::randomInteger(unsigned long n)
{
    randSeed = multiplier * randSeed + adder;
    return (unsigned short)((randSeed >> 16) % n);
}
/*
    产生[0,1)之间的随机实数
*/
double RandomNumber::randomFloat(void)
{
    return randomInteger(maxshort) / double(maxshort);
}

int main()
{
    printf("请输入一个种子：");
    unsigned long rs;
    scanf("%ld", &rs);
    RandomNumber rn(rs);

    printf("\n请输入一个整数(确定随机数的范围)：");
    int n;
    scanf("%d", &n);

    printf("\n产生0--%d之间的随机整数：%u \n", n - 1, rn.randomInteger(n));
    printf("\n产生[0,1)之间的随机实数为：%lf\n\n\n\n", rn.randomFloat());

    return 0;
}