《数论算法》 第五章 原根与离散对数

＝{0, 1, 2, …,m?1}上关于模素数p的加法和乘法运算，有限域概念见§9.4）。其基本思想是： （1） 选一整数d?n，设

xx?qd?r，0?r＜d，q??n

d故只要求得q和r，就等于求出了x。

（2） 令i＝0, 1, …,d?1，计算?i?ai?modp?，并构造一个

指数函数表??i,i?。为了便于检索，按?i值的增序排列。

xqd?ry?a?a（3） 由于假定，所以

?a?d?qy?a?qdaqd?r?ar

q?a??dy??an?d?qy

（4） 令q＝0, 1, 2, …，逐个计算uq?a等于表中某个?i（?i?ai?n?d?qy，直到uq?modp?）为止。那么，

必有x?qd?i，输出x。

Shank法可以归纳如下，其中已知素数p、底数a、真数y和a的乘法周期n，且所有运算都在GF?p?上进行： S1. 选择d?n；i←0；?←1 S2. 将??,i?的值填入指数函数表A S3. 若r＝d?1，则 { 对表格A数据按?的值增序排列；转S4 } 否则 {??a?；i?i?1；转S2 } //完成建表 S4. 计算：b?an?d；u?y；q←0 //赋初值 S5. 若表A中存在一对数??,r?，满足?=u，则 {令x?qd?r；输出x；算法结束} 否则{u?bu；q?q?1；转S5} //迭代求解 【例6.4.2】在GF（23）上求x?dlog53。

（解）5的乘法周期为22，故5是23的原根。 对于很小的p＝23，可以穷举求解，即计算：50≡1，51≡

37/58

《数论算法》 第五章 原根与离散对数

5，52≡2，…，515≡19，516≡3。所以x?16?mod23?。

现在用Shank法求解：选d=5?22，针对i＝0, 1, …, d－1即i＝0, 1, 2, 3, 4计算??ai?modp??5i?mod23?，建立指数函数表（见表6.4.4），其中按?的增序排列。

表6.4.4 5r(mod 23)的指数函数表

??ar 1 2 4 5 10 0 2 4 1 3 r

计算b?an?d?522?5?517?15?mod23?，u?y＝3，q＝0

检查：因表中无?＝3，故继续计算：

u≡15×3≡22，q＝1（即计算的是bu≡517+16≡533≡511≡22）

检查：表中无?＝22，继续计算：

u≡15×22≡8，q＝2（即计算bu≡517+11≡56≡8） 检查：表中无?＝8，继续计算：

u≡15×8≡5，q＝3（即bu≡517+6≡523≡5） 检查：表中存在?＝5，对应的r＝1，故有

x?qd?r＝3×5＋1＝16

∴ dlog53=16?mod22? 或 3?516?mod23?

另外，若a的乘法周期n可以分解，则该方法还可化简。思路如下：

a2?an设n?n1n2（an?1?modp?），则a1?an的乘法周期为n1，

的乘法周期为n2。

21若 y?a（0?x?n）

则 x=x2n1?x1，0?x1?n1，0?x2?n2 令 y1?y由于 ∴ 即

n2x?an2x?ax2n1n2?x1n2

an1n2?an?1 y1?an2x1?a1x1 x1?dloga1y1

n1x2?x1x2a?x1?an1x2?a2

?x1n?x1y?ya?ya令 2＝a38/58

《数论算法》 第五章 原根与离散对数

则 x2?dlogay2

2由此得n?n1n2时，求x?dlogay的算法如下： S1. a1?an；y1?yn S2. 求x1?dlogay1 221S3. a2?an；y2?an?x S4 . 求x2?dlogay2 S5. 输出 x=x2n1?x1 112

5.5 二项同余方程n次剩余

二项同余方程：xn≡a（mod m）， ?a,m?＝1 【定义5.5.1】设m＞1，(a, m)＝1，若n次同余方程

xn≡a（mod m） （1）

有解，则a叫做对模m的n次剩余；否则，叫做对模m的n次非剩余。

5【例】求5次同余方程x≡9（mod 41）的解。 （解）查模数为41，底数为6的离散对数表，可得dlog6(9)＝30，即6≡9（mod 41）。 再令 x≡6（mod 41） 原方程变为 65yy30≡6（mod 41）

30因6是原根，故由定理5.3.1

5y≡30（mod 40＝?(41)） （2）

（（5, 40）＝5，且5│30，故此方程有5个解） 即 y≡6（mod 8）

故（2）的解为 y≡6，14，22，30，38（mod 40）

39/58

《数论算法》 第五章 原根与离散对数

∴ x≡6＝6，6，6，6，6

≡39，21，5，9，8（mod 41）

故9是模41的5次剩余。

【例】求7次同余方程x7≡9（mod 41）的解。 （解）因为dlog6(9)＝30，即6≡9（mod 41）。 再令 x≡6（mod 41） 原方程变为 67y≡6（mod 41） 6是原根，故有 7y≡30（mod 40＝?(41)） 解之，得 y≡10（mod 40）

故原方程有唯一解 x≡610≡32（mod 41）

【例】求8次同余方程x8≡9（mod 41）的解。 （解）因为dlog6(9)＝30，即6≡9（mod 41）。 再令 x≡6（mod 41） 原方程变为 68y≡6（mod 41） 6是原根，故有 8y≡30（mod 40＝?(41)） 此方程无解，故原方程无解。

【定理5.5.1】设m＞1，g是模m的一个原根，(a, m)＝1，则同余方程

30y3030y30y614223038xn≡a（mod m） （3）

有解??n,??m??dlogga。且在有解的情况下，解数为

?n,??m??。

（证）若方程（3）有解x?x0（mod m）

40/58