新書推薦：
《
便宜货：廉价商品与美国消费社会的形成
》
售價：HK$
77.3
《
读书是一辈子的事（2024年新版）
》
售價：HK$
77.3
《
乐道文库·什么是秦汉史
》
售價：HK$
80.6
《
汉娜·阿伦特与以赛亚·伯林 ： 自由、政治与人性
》
售價：HK$
109.8
《
女性与疯狂（女性主义里程碑式著作，全球售出300万册）
》
售價：HK$
109.8
《
药食同源中药鉴别图典
》
售價：HK$
67.0
《
设计中的比例密码：建筑与室内设计
》
售價：HK$
87.4
《
冯友兰和青年谈心系列：看似平淡的坚持
》
售價：HK$
55.8
|
| 編輯推薦： |
|
《算法数论（第二版）》的部分内容曾多次在中国科学院研究生院信息安全国家重点实验室和广州大学作为硕士研究生教材使用《算法数论（第二版）》可作为信息安全、数论等专业的研究生教材，以及相关专业的研究人员、高等学校的教师和高年级学生的参考书。
|
| 內容簡介： |
|
《算法数论（第二版）》论述了算法数论的基本内容，其中涉及同余式、二次剩余、特征、连分数、代数数域、椭圆曲线、素性检验、大整数因子分解算法、椭圆曲线上的离散对象、超椭圆曲线、格理论等分支，也介绍了这些知识在密码学中的一些应用目《算法数论（第二版）》的特点是内容涉及面广，在有限的篇幅内，包含了必要的预备知识和数学证明，尽可能形成一个比较完整的体系。
|
| 目錄：
|
目录
《现代数学基础丛书》序
第二版前言
**版前言
第1章整数的因子分解1
I.1**分解定理1
1.2辗转相除法（欧氏除法）3
1.3 Mersenne素数和Fermat素数6
1.4整系数多项式8
1.5环z[i]和z[M]11
习题12
第2章同余式14
2.1孙子定理14
2.2剩余类环16
2.3Euler函数φm18
2.4同余方程20
2.5原根25
2.6缩系的构造28
习题31
第3章二次剩余33
3.1定义及Euler判别条件33
3.2 Legendre符号34
3.3Jacobi符号39
3.4二次剩余假设 41
习题47
第4章特征 48
4.1剩余系的表示 48
4.2特征49
4.3原特征 53
4.4特征和 55
4.5Gauss和58
习题60
第5章连分数61
5.1简单连分数61
5.2用连分数表实数63
5.3**渐近分数65
5.4 Legendre判别条件66
习题68
第6章代数数域69
6.1代数整数69
6.2Dedekind整环75
6.3阶的一些性质84
习题89
第7章椭圆曲线92
7.1椭圆曲线的群结构92
7.1.1Weierstrass方程92
7.1.2椭圆曲线上的加法93
7.1.3同构与j不变量96
7.2除子类群98
7.3同种映射100
7.4Tate模和Weil对105
7.5有限域上的椭圆曲线110
习题113
第8章密码学中的一些应用114
8.1 RSA公钥密码114
8.2DiffieHellman体制116
8.3 EIGamal算法117
8.4基于背包问题的公钥密码118
8.5概率公钥密码119
8.6秘密英享122
第9章素性检验124
9.1 Fermat小定理及伪素数124
9.2强伪素数及MillerRabin检验125
9.3利用n1的因子分解的素性检验128
9.4利用n+1的因子分解的素性检验129
9.5分圆环素性检验132
9.6基于椭圆曲线的素性检验136
第10章大整数因子分解算法138
10.1连分数因子分解算法138
10.2二次筛法140
10.3Pollard的pl因子分解算法141
10.4椭圆曲线因子分解算法141
10.5数域筛法143
习题157
第11章椭圆曲线上的离散对数158
II.I椭圆曲线公钥密码158
11.2小步大步法161
11.3家袋鼠和野袋鼠162
11.4 MOV约化163
11.5FR约化168
11.6 SSSA约化172
11.7有限域上离散对数的计算175
第12章超椭圆曲线184
12.1超椭圆曲线的Jacobian184
12.2虚二次代数函数域187
12.3基于超椭圆曲线的公钥密码189
第13章格190
13.1基本概念190
13.2 111算法195
13.3 111算法在密码分析中的应用202
13.3.1背包问题求解202
13.3.2针对RSA密码算法的小解密指数攻击203
13.4基于格的密码体制设计206
13.4.1NTRU体制207
13.4.2基于LWE问题的全同态加密体制208
习题213
附录一些常用算法214
A1不可约多项式的判别214
A2有限域中平方根的求解 215
A3有限域上的分解216
A4Hensel引理218
A5 Z[x]中多项式的分解 219
参考文献221
名词索引225
《现代数学基础丛书》已出版书目229
|
| 內容試閱：
|
第 1 章 整数的因子分解
1.1**分解定理
数论是研究自然数 1； 2； 3； 性质的一门数学分支。 自然数是人们日常生活中 用得*多的一类数。历史上， 人们很早就开始研究数论， 它已成为内容十分丰富的 一个分支。数论在信息安全、计算机科学、数字信号处理等现代科技领域有重要的 应用， 所以， 数论至今仍是一门充满活力、蓬勃发展的分支。
通常， 用 Z 表示整数集合， 整数即为 0； §1； §2； : 自然数就是正整数。
定理 1.1 设 a 和 b 为整数， b 0， 则存在整数 q 和 r， 使 a = qb + r； 0≤r b； r 称为 b 除 a 所得的*小正剩余。
证明 以 ab 表示不超过分数 ab 的**整数， 则 0≤ a-hab ib b； 取 q = hab i； r = a . hab ib， 即证得定理. 当 b 除 a 的*小正剩余 r 为零时， 称 b 为 a 的因子， a 为 b 的倍数， 记为 b|a. 若 b 为 a 的因子， b 6= 1； b 6= a， 这时称 b 为 a 的真因子， 显然有 0 |b| |a| ， 这里 |a| 为 a 的**值. 若 b 6= 0； c 6= 0， 显然有：
1 若 b|a； c|b， 则 c|a；
2 若 b|a， 则 bc|ac；
3 若 c|d； c|e， 则对任意 m； n 有 c|dm + en.
自然数 p 6= 1， 若仅以 1 和自身 p 为其因子， 称 p 为素数. 非素数的自然数 n 6= 1 称为复合数.整数的因子分解 设 M 为整数的一个子集合， 如果它对加、减法封闭， 即若 m； n 2 M， 则 m§n 2 M， 这时称 M 为模. a 为任一整数， a 的所有的倍数就组成一个模. 相反的结论也 成立， 即如下定理.
定理 1.2 任一非零模， 必为一正整数的诸倍数组成的集合.
证明 设 d 为该模中*小正整数， 则模中其他数必为 d 之倍数. 若不然， 设 n 为模中 d 之非倍数， 由定理 1.1， 存在整数 q 及 r， 使 n = qd + r； 0 r d: 由于 r = n . qd 也属于此模， 这与 d 为该模中*小正整数的假设相矛盾， 故模中其 他各数都为 d 的倍数. 因为 d 在模中， 所以 d 的任一倍数也在模中. 定理即证. 命 a； b 为二整数， 集合 fma + nb | m； n 2 Zg 即为一模， 此模中*小正整数 d 称为 a； b 的**公因子， 记为 d = a； b. 由定理 1.2 的证明， 不难证得下述定理.
定理 1.3 a； b 具有下述性质：
1 有整数 x； y， 使 a； b = ax + by；
2 对任二整数 x； y， 必有 a； b|ax + by；
3 若 c|a； c|b， 则 c|a； b. 由于 3， 也称 a； b 为 a； b 的**公因子.
定理 1.4 设 p 为素数且 p|ab， 则 p|a 或 p|b.
证明 若 p - a， 则 a； p = 1， 由定理 1.3 知有二整数 x； y， 使 ax + py = 1； 所以 abx + pyb = b: 由 p|ab 可知 p|b， 证毕.
定理 1.5**分解定理 任一自然数 n 皆可**地表为素数之积 n = pa1 1 pa2 2 pak k : 1:1 这里， p1 p2 pk 为素数， a1； a2； ； ak 为自然数. 证明 首先证明 n 可以表为素数之积， 然后再证明上述表法**. 若 n 为素数， 定理显然成立. 当 n 不是素数时， 设 p1 是 n 的*小的真因子， 则 p1 一定是素数， 因 p1 的真因子也是 n 的真因子， 所以 p1 不能有真因子. 设n = p1n1 1 n1 n， 对 n1 重复上述推理， 得 n = p1p2n2， p2 为素数， 1 n2 n1， 继续执行此法， 得 n n1 n2 1， 此做法*多不能超过 n 次， *后必得 n = p1p2 pl； 也可排为式 1.1 中的形式. 今设 n = pa1 1 pa2 2 pak k = qb1 1 qb2 2 qbl l 为 n 的两个分解式， 其中 p1 p2 pk； q1 q2 ql 都为素数， 利用定 理 1.4， 任一 pi 必为某一 q| ， 任一 qi 也必为某一 p| ， 故 k = l； pi = qi 1 6 i 6 k， 又 若 a1 b1， 则 pa1.b1 1 pa2 2 pak k = pb2 2 pbk k ； 左边为 p1 的倍数， 右边不是 p1 的倍数， 这是不可能的， 同样 a1 b1 也不可能， 故 a1 = b1. 类似地， 可证得 ai = bi i = 1； 2； ； k， **性得证. 给定一自然数 n， 当它很大时， 例如， 一百多位的十进制数， 要将它因子分解， 实非易事. 在第 10 章将讨论一些大整数因子分解的算法， 随之而来的一个问题是 如何判断一个数是否是素数， 在第 9 章将讨论几个素性判断的方法.
1.2辗转相除法 欧氏除法
若 a； b 为二自然数， a b， 以 a； b 表示 a 和 b 的**公因子. 由定理 1.3 知， 有二整数 x； y， 使 a； b = ax + by: 如何计算 a； b， 又如何找到上述 x 和 y， 定理 1.1 实际上已经给出了所要的算法. 首先用 b 除 a 得到商 q0， 余数 r0， 即 a = q0b + r0； 0 6 r0 b: 1:2 如果 r0 = 0， 那么 b 是 a 的因子， a； b 的**公因子就是 b. 如果 r0 6= 0 ， 用 r0 除 b 得到商 q1， 余数 r1， 即 b = q1r0 + r1； 0 6 r1 r0: 1:3 如果 r1 = 0， 那么 r0 除尽 b， 由式 1.2 知， r0 也除尽 a， r0 是 a； b 的公因子. 反之， 任何一个除尽 a； b 的数， 由式 1.2 知， 也除尽 r0， 因此 r0 是 a； b 的**公因子. 如 果 r1 6= 0， 则用 r1 除 r0 得到商 q2， 余数 r2，即 r0 = q2r1 + r2； 0 6 r2 r1: 1:4 整数的因子分解 如果 r2 = 0， 那么由式 1.3 可知， r1 是 r0； b 的公因子， 由式 1.2 知， r1 也是 a； b 的公因子. 反之， 如果一整数除得尽 a； b， 那么由式 1.2 知， 它一定除得尽 r0 ， 由 式 1.3 知， 它一定除得尽 r1， 所以 r1 是 a； b 的**公因子. 若 r2 6= 0， 再用 r2 除 r1， 重复上述过程， 依次得到 b r0 r1 r2 ， 逐 步小下来， 而又都非负. 经过有限步后， 一定会有某个 r 为零. 若设 rn 是**个出 现的零， 则 rn.1 就是 a； b 的**公因子. 所得到的一串算式为 a = q0b + r0； b = q1r0 + r1； r0 = q2r1 + r2； r1 = q3r2 + r3； rn.3 = qn.1rn.2 + rn.1； rn.2 = qnrn.1: 由**式可得 r0 = a . q0b； 由第二式可得 r1 = b . q1r0 = .q1a + 1 + q0q1b； 一般地， 对任一 ri 0 6 i 6 n . 1， 都有二整数 xi； yi， 使 ri = xia + yib: 由于 ri = ri.2 . qiri.1 = xi.2a + yi.2b . qixi.1a + yi.1b = xi.2 . qixi.1a + yi.2 . qiyi.1b；
所以有递推公式x0 = 1； x1 = .q1； xi = xi.2 . qixi.1； y0 = .q0； y1 = 1 + q0q1； yi = yi.2 . qiyi.1: 这样， 可以找到二整数 x； y， 使 a； b = ax + by: 看一个例子：求 4862 和 2156 的**公因子， 则有 4682 = 2 ￡ 2156 + 550； 2156 = 3 ￡ 550 + 506； 550 = 506 + 44； 506 = 11 ￡ 44 + 22； 44 = 2 ￡ 22:
可见 4862； 2156 = 22， 利用上述算式可得 550 = 4862 . 2 ￡ 2156； 506 = .3 ￡ 4862 + 7 ￡ 2156； 44 = 4 ￡ 4862 . 9 ￡ 2156； 22 = .47 ￡ 4862 + 106 ￡ 2156: 称上述求 a； b 的**公因子的算法为辗转相除法， 或欧几里得除法. 考虑辗转相除法所需的比特计算量. 仍设 a b， 若 a 和 b 用二进制表示的长 度分别为 k 和 l， 则 k 6 log2 a + 1； l 6 log2 b + 1. 用 b 除 a 得到商和余数， 这个带 余除法所需的比特计算量为 Okl这里 Okl 表示一个 6 c ￠ kl 的量， 其中 c 为一 个不依赖 k 和 l 的常数， 也可表为 Olg2 a. 还需要知道带余除法要做多少次. 我们有 r|+2 12r| . 首先来证明这个论断. 若 r|+1 6 12r| ， 则 r|+2 r|+1 6 12r| ， 即证. 若 r|+1 12r| ， 则 r| = r|+1 + r|+2 ， 同样有 r|+2 12r| . 以上论断表示， 做两次带余除法可将余数缩小一半. 要得到 a； b， 所要做的带 余除法的次数不会超过 2[log2 a] = Olg a， 因而辗转相除法所需的比特计算量为 Olg2 a ￡ Olg a = Olg3 a: 给定自然数 a； b， 若已知它们的因子分解 a = p.1 1 p.2 2 p.s s ； .i 0 1 6 i 6 s； b = pˉ1 1 pˉ2 2 pˉs s ； ˉi 0 1 6 i 6 s； 则 a； b = pmin.1；ˉ1 1 pmin.2；ˉ2 2 pmin.s；ˉs s : 若以 [a； b] 表示 a； b 的*小公倍数 即 [a； b] 是 a 和 b 的倍数， 且任一 a 和 b 的公倍 数都是 [a； b] 的倍数， 则 [a； b] = pmax.1；ˉ1 1 pmax.2；ˉ2 2 pmax.s；ˉs s : 易见 a； b[a； b] = a ￠ b: 对于多个自然数 a1； a2； ； ak， 也可以定义它们的**公因子和*小公倍数.
1.3Mersenne 素数和 Fermat 素数
n 为一自然数， 以 .n 表示 n 的所有因子之和. 定理 1.6 若 n = pa1 1 pas s ， 则 .n = pa1+1 1 . 1 p1
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
