加拿大PRNG专家批评当局使用古老的Excel算法绘制签证

家庭团聚计划（家庭团聚计划）是加拿大三个主要的移民援助计划之一。 它使新近到来的移民和历史悠久的加拿大人都能与家人团聚。 根据《移民和难民保护条例》，居住在国外的家庭将获得经济援助，就像居住在加拿大的移民亲戚一样。 配偶，子女，父母，孙子女，领养子女等可以依靠经济援助。

问题是加拿大不能立即向所有移民的所有亲属授予公民身份。 以前，它们已经排在队列中，并且必须考虑使用该应用程序多年。 为了加快这一进程，自由主义者提议开奖。 因此，自2017年以来，像美国绿卡这样的彩票在加拿大开始发行。 在大约100,000份申请中，有10,000份是随机选择的，这要归功于官方对《信息公开法》要求的回应，加拿大出版物The Globe an Mail揭示了彩票操作的一些技术细节 。

事实证明，联邦政府使用Microsoft Excel选择获奖者。 这就是整个过程的详细外观。

• 第一步 移民，难民和公民事务局（加拿大移民，难民和公民事务局，IRCC）使用Microsoft Excel为每个申请分配有序编号。
• 第二步 使用Microsoft Excel中的RANDOMBETWEEN函数，为每个带有序列号的应用程序分配一个从100,000到9,999,999的随机数。
• 第三步 Excel电子表格按列从低到高的顺序进行排序-前10,000个条目被选为彩票赢家。

该方案遭到了一些专家的批评。 蒙特利尔大学最著名的随机数生成专家Pierre L'Ecuyer教授是RNG的许多科学著作的作者，他称这种方法非常糟糕：“这是一种非常古老的发生器，实际上不能称之为现代发生器。”他是。 L'Ecuille教授的一项研究表明，Excel伪随机数生成器未通过某些统计检验。 尽管对于此应用程序来说已经足够了，但是没有什么可以阻止IRCC仅仅采用和使用常规的现代PRNG。

Excel使用具有确定结果的数学算法作为PRNG，这取决于单个种子。 对于Excel，此初始值由应用程序自动创建。 如果您在第一步中知道一个数字，则可以计算序列中的所有其他数字。 加拿大一家报纸写道，以前发生过类似的事情。 1994年，IT顾问Daniel Corriveau在基诺（Keno）发现了这种模式，并在一晚在蒙特利尔蒙特利尔赌场（Montreal Casino deMontréal）赢得了60万加元。 他连续三次猜出20个获奖号码中的19个 。

调查显示，赌场使用与Excel中相同的古代PRNG。 在每天的开始，选择一个随机值，并且在这一天中，其他数字就是该可预测序列中的数字。

然后在1994年，L'Ecouillet教授提出了确定性PRNG 的结构 $$$（\ mathcal {S}，\ mu，f，\ mathcal {U}，g）$在哪里 $$$\数学{S}$是一组有限的状态， $$$\亩$-状态空间中的概率分布 $$$\数学{S}$用于选择初始状态 $$$\ mathcal {s_ {0}}$（种子） $$$f：\ mathcal {S} \ rightarrow \ mathcal {S}$-过渡功能， $$$\数学{U}$-输出值的空间， $$$g：\ mathcal {S} \ rightarrow \ mathcal {U}$。

通常 $$$\数学{U} =（0,1）$，并且生成器的状态由递归公式给出 $$$s_ {i} = f \（s_ {i-1}）$为 $$$我\ geq 1$。 发电机输出值 $$$u_ {i} = g \（s_ {i}）\ in \ mathcal {U}$; $$$u_ {0}，\ u_ {1}，\ u_ {2} \ ...$-伪随机数序列。 这是一个周期性序列，“周期”称为最小正数 $$$j$。

在PRNG中，最常见的是线性一致方法，带延迟的Fibonacci方法，具有线性反馈的移位寄存器，具有广义反馈的移位寄存器。 在现代的PRNG中，由Matsumoto和Nishimura在1997年提出的Mersenna涡流也得到了广泛使用。 它的优点是一个巨大的周期（2 ¹⁹⁹³⁷ -1）和623个维度上的均匀分布（线性一致方法在最多五个维度上或多或少地提供了均匀分布），以及快速生成随机数。

L'Ecuille教授认为，当局使用Excel中的PRNG非常愚蠢，因为可靠的加密PRNG易于访问且不花费任何费用：“加密生成器是免费的。 他们在互联网上，”教授说。 “只选一个。” 这一点都不困难。”

但是，IRCC政府委员会似乎对使用Excel感到满意。 女发言人Shannon Ker在一封电子邮件声明中写道：“我们支持这种随机选择过程，将其作为任何平等的机会工具，供任何希望表达其对父母和祖父母的资助兴趣的人使用。”