《数论算法》 第五章 原根与离散对数
对于方法PMMLCGs，由于不能选2b为模，因而不能运用溢出的机理去影响除法的模m。针对此情况，Payne、Rabung和Bogyo等人提出了一种避免明显除法，运用溢出原理的方法——模拟除法。 由
Xn?aXn?1?mod2b?知
?aXn?1?k??2b?Xn?aXn?1?k2b，??
??令 若 若
yn?Xn?kq?a?n?2bk1X?
qXn?kq?2b?，则q
yn?aXn?1?modb2?q?
Xn?kq?2b?，则令q
yn?Xn?kq?k?2b?q??aXn?1??k?1??2b?q??aXn?1?mod2b?q?
byn??m?2?q时的随机序列，并且遵从原则 数列提供了
b??Xn?kq,若Xn?kq?2?qyn??bb??Xn?kq?q?2,若Xn?kq?2?q
式中Xn可由移模减数而得。
PMMLCGs的实际用例：b＝35，小于235的最大素数为
m?235?31＝34359738337，且a?55时＝3125，生成的随机数
31具有较好的特性；对于b＝35，小于231的最大素数为m?2?1a1?7＝2147483647，且两种得到广泛应用的关于的a选择为：
＝16807和a2＝630360016。
5（3）Fibonacci法
此方法是建立在Fibonacci（斐波那契）数列的基础上，其递归公式为
Xn+1?Xn+Xn?1?modm?， n＝1, 2, …
Fibonacci法需要两个初值X0和X1。其得到的周期有可能大于m，但它所生成的序列的随机性较差，故不能提供满意的结果。
（4）二次同余法
49/58
《数论算法》 第五章 原根与离散对数
由Coveyon提出的二次同余法近似相当于双精度的中间平方法，但却比后者有较长的周期。其递归公式为
2Xn?aXn?1+?Xn?1?c??modm?， n＝1, 2, …
5. 6. 4 一种快速傅里叶变换算法
?F0??x0??????F1??x1??T?【定义6.6.1】离散傅里叶变换（DFT）：? ?????????F??x??N?1??N?1??W0?0W0?1?W1?1?W1?02?1Fourier变换矩阵T??W2?0W??????N?1??0?N?1??1WW??????W0??N?1)???1??N?1?W? W2??N?1??????N?1???N?1??W?11?1?W2?1W＝?1W2W4??????1WN?1W2?N?1??W?e?2?iN???????N?1W?W2?N?1??，
????N?1?2?W?，i12?2??cos?isinNN??1
另法表示：
N?1Fk??N?1?knkk2kxW?x?xW?xW???xW ?nN01N2NN?1Nn?022运算量：N次复数乘法和N次复数加法 【定义6.6.2】设
50/58
《数论算法》 第五章 原根与离散对数
a0,a1,?,aN?1,?和b0,b1,?,bN?1,?
是两个周期为N的序列，其互相关函数定义为
B?k???aibi?ki?0N?1，k＝0, 1, 2, …, N?1
【定理6.6.2】设N?p是一个奇素数，则式（5.6.1）可化为两个周期为p?1的序列的互相关函数，和2?p?1?次加法来计算。
（证）设N?p
nkFk???xnWNn?1p?1，k＝1, 2, …, p?1 （5.6.2）
则有
F0??xnn?0p?1，Fk?x0?Fk?，k＝1, 2, …, p?1 （5.6.3）
s又设g是p的一个原根，则1, 2, …, p?1可表为?g化为
qF???xstWp??g?g?p?（s＝0,
psp?2g1, …, ），即除以p的最小非负余数，于是式（5.6.2）
p?2t?0s?tp，s＝0, 1, …, p?2 （5.6.4）
由于g是原根，所以式（5.6.4）是两个周期为p?1的序列
au?x?gu?p（
u＝0, 1, …）和av?W（v＝0, 1, …）的互相
。
?qvp关函数，再由式（5.6.3）的2?p?1?次加法给出全部
F0,F1,?，Fp?1?p同理，对于N?p和2（p是一个奇素数），也有类
似的结果。
5. 6. 5 同余方程的求解
【例6.6.3】解同余方程16x≡9（mod 41）。
51/58
《数论算法》 第五章 原根与离散对数
（解）此处利用离散对数求解。已知6是41的原根，故对方程两边取以6为底的对数，有
dlog41,616x?dlog41,69?mod??41??40? 再由定理6.3.2，方程可表为
dlog41,616?dlog41,6x?dlog41,69?mod40?
查离散对数函数表6.3.4有dlog41,616?24?mod40?，
dlog41,69?30?mod40?，代入上式得
24＋dlog41,6x?30?mod40? ∴ dlog41,6x?6?mod40?
再查指数函数表6.3.3得x≡39（mod 41）。所以原方程的解为
x≡39（mod 41）
利用离散对数还可以解幂同余方程
ax?b?modm?，?b,m?＝1 （6.6.5）
其中m有原根g。
【定理6.6.3】设整数m＞1，其原根为g。那么，幂同余方程（6.6.5）有解的充分必要条件是
???m?,dlogm,ga?dlogm,gb （6.6.6）
记d????m?,dlogm,ga?，如果方程有解，则其解数为
T?ax?b;m??d
其通解为
x?x0???m?dt?mod??m??，t?0,1，?,d?1
（证）由于m有原根g，故等式（6.6.5）两边针对模数m取以g为底的对数，有
xdlogm,ga?dlogm,gb?mod??m?? （6.6.7） 显然幂同余方程（6.6.5）与一次同余方程（6.6.7）同时有解或无解，且解数也相同。
而方程（6.6.7）为一次同余方程，故由定理4.4.2可推导出本定理的所有结论。
【例6.6.4】判断幂同余方程10x≡2（mod 17）是否有解，
52/58