实验8 - 简易伪随机数生成器

1. 实验概述和参数

使用C++语言，实现以下伪随机数生成器算法：

设\(p\)是一个64比特长的素数，\(g \in \mathbb{Z}_p^{*}\)是一个本原元。种子\(s_0\)是\(\mathbb{Z}_p^{*}\)中的一个元素。

对于\(0 \leq i \leq l - 1\)，定义

然后定义

其中

最终程序输出\(f(s_0) = (z_1,z_2,\dots,z_l)\)。

下面是算法过程的图示：

下面是实验的参数：

• \(p\)：13835075647472402443；十六进制为0xc00010000040000b

• \(g\)：12332102632472395673；十六进制为0xab246e01862d3f99

• 种子\(s_0\)为自己的学号

• 输出长度\(l\)：512

2. 实验要求

在本次实验中，我们需要使用C++编程实现该生成器，给出前512比特的随机数结果\(s_1s_2\dots s_{512}\)，统计结果中0和1出现的次数，并测量运行时间。

也就是说，程序需要输出以下三个信息：

• 前512比特的随机数结果（二进制表示法，即01字符串的形式）

• 程序运行时间，运行时间单位不作要求

• 统计随机数结果中0和1出现的次数

下面是程序的输出示意图，仅用于参考。

请注意： 本次实验不能使用大数库，须自行实现64位整型的模p乘法和模幂运算。建议使用uint64_t数据类型（或unsigned long long）进行实验，不允许使用__int128_t和__uint128_t等支持128bit长或更长的整型数据类型。

3. 作业提交方式

• 邮箱：jeza@qq.com

• 请将代码（将所有代码写在一个.c/.cpp文件上，提交单文件即可）和实验报告打包提交。邮件和附件命名为学号_姓名_实验8​。例：1111111_陈建彰_实验8​。

• 不用提交可执行程序。实验结束后助教会统一在一台机器上编译、运行同学们的代码。

• DDL：下课之前

请注意，代码只需提交一个.c/.cpp文件（务必保证所有代码都在一个文件里面），不要提交工程文件和可执行程序。

4. 实验评分

主要考虑三个方面：

• 实验结果（输出的随机比特串是否正确）

• 程序性能（程序运行时间，本次实验将使用同一台机器运行所有同学的代码，以运行时间作为评分的依据）

• 实验报告（给出实现过程、贴上实验结果截图以及一两句实验总结即可）

另外，本次实验将使用MOSS进行代码重复率检查，如果代码重复率较高则酌情扣分。

5. 实验结果正确性验证

下面给出一个接口，用于检验实验程序输出的结果是否正确。

6. 伪随机数生成器运行过程前64轮的中间变量

下面给出的接口用于显示该随机数生成器算法运行过程中，前64轮所产生的中间变量\(i\)、\(s_i\)以及\(z_i\)，方便同学们进行调试。

7. 一些参考资料

7.1 两个uint64_t整型相乘时，可能会发生溢出，如何处理？

可以使用两个uint64_t变量表示乘法结果的高64位和低64位，乘法结果的低64位比较容易获取，而高64位的获取方式可以参照StackOverflow的一个问题。

7.2 一种简单的取模运算

假定有一个128位的无符号整数A和一个64位的无符号整数B。有什么简单的方法计算A % B？

可以使用俄罗斯农民乘法的除法版本计算出A % B，算法过程可以参照StackOverflow，下面简单贴出该算法的伪代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
X = B;

while (X <= A/2)
{
    X <<= 1;
}

while (A >= B)
{
    if (A >= X)
        A -= X;
    X >>= 1;
}

return A;

该算法只涉及到左移、右移、减法和比较操作，因此比较适合于代码实现。大家只需实现128位无符号整数(用两个uint64_t变量维护高64位和低64位)的上述四个操作即可。