百道网
 您现在的位置:Fun书 > 算法数论(第二版)
算法数论(第二版)


算法数论(第二版)

作  者:裴定一,祝跃飞 编著

出 版 社:科学出版社

丛 书:现代数学基础丛书

出版时间:2015年09月

定  价:78.00

I S B N :9787030453327

所属分类: 教育学习  >  教材  >  研究生/本科/专科教材    

标  签:数学  数学理论  自然科学  

[查看微博评论]

分享到:

TOP好评推荐   [展开]

TOP内容简介

《算法数论(第二版)》论述了算法数论的基本内容,其中涉及同余式、二次剩余、特征、连分数、代数数域、椭圆曲线、素性检验、大整数因子分解算法、椭圆曲线上的离散对象、超椭圆曲线、格理论等分支,也介绍了这些知识在密码学中的一些应用目《算法数论(第二版)》的特点是内容涉及面广,在有限的篇幅内,包含了必要的预备知识和数学证明,尽可能形成一个比较完整的体系。

TOP作者简介

裴定一,祝跃飞 编著

TOP目录

《现代数学基础丛书》序 

第二版前言 

第一版前言 

第1章整数的因子分解 

1.1唯 一分解定理 

1.2辗转相除法(欧氏除法) 

1.3Mersenne素数和Fermat素数 

1.4整系数多项式 

1.5环Z(i)和Z(w) 

习题 

第2章同余式 

2.1孙子定理 

2.2剩余类环 

2.3Euler函数ψ(m) 

2.4同余方程 

2.5原根 

2.6缩系的构造 

习题 

第3章二次剩余 

3.1定义及Euler判别条件 

3.2Legendre符号 

3.3Jacobi符号 

3.4二次剩余假设 

习题 

第4章特征 

4.1剩余系的表示 

4.2特征 

4.3原特征 

4.4特征和 

4.5Gauss和 

习题 

第5章连分数 

5.1简单连分数 

5.2用连分数表实数 

5.3最 佳渐近分数 

5.4Legendre判别条件 

习题 

第6章代数数域 

6.1代数整数 

6.2Dedekind整环 

6.3阶的一些性质 

习题 

第7章椭圆曲线 

7.1椭圆曲线的群结构 

7.1.1Weierstrass方程 

7.1.2椭圆曲线上的加法 

7.1.3同构与j不变量 

7.2除子类群 

7.3同种映射 

7.4Tate模和Weil对 

7.5有限域上的椭圆曲线 

习题 

第8章密码学中的一些应用 

8.1RSA公钥密码 

8.2Diffie—Hellman体制 

8.3ElGamal算法 

8.4基于背包问题的公钥密码 

8.5概率公钥密码 

8.6秘密共享 

第9章素性检验 

9.1Fermat小定理及伪素数 

9.2强伪素数及Miller—Rabin检验 

9.3利用n—1的因子分解的素性检验 

9.4利用n+1的因子分解的索性检验 

9.5分圆环素性检验 

9.6基于椭圆曲线的素性检验 

第10章大整数因子分解算法 

10.1连分数因子分解算法 

10.2二次筛法 

10.3Pollard的p—1因子分解算法 

10.4椭圆曲线因子分解算法 

10.5数域筛法 

习题 

第11章椭圆曲线上的离散对数 

11.1椭圆曲线公钥密码 

11.2小步—大步法 

11.3家袋鼠和野袋鼠 

11.4MOV约化 

11.5FR约化 

11.6SSSA约化 

11.7有限域上离散对数的计算 

第12章超椭圆曲线 

12.1超椭圆曲线的Jacobian 

12.2虚二次代数函数域 

12.3基于超椭圆曲线的公钥密码 

第13章格 

13.1基本概念 

13.2LLL算法 

13.3LLL算法在密码分析中的应用 

13.3.1背包问题求解 

13.3.2针对RSA密码算法的小解密指数攻击 

13.4基于格的密码体制设计 

13.4.1NTRU体制 

13.4.2基于LWE问题的全同态加密体制 

习题 

附录一些常用算法 

A.1不可约多项式的判别 

A.2有限域中平方根的求解 

A.3有限域上的分解 

A.4Hensel引理 

A.5Z(x)中多项式的分解 

参考文献 

名词索引 

《现代数学基础丛书》已出版书目

TOP书摘

第 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 所得的*小正剩余。
  证明 以 a/b 表示不超过分数 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 + q0q1)b; 一般地, 对任一 ri (0 6 i 6 n . 1), 都有二整数 xi; yi, 使 ri = xia + yib: 由于 ri = ri.2 . qiri.1 = (xi.2a + yi.2b) . qi(xi.1a + yi.1b) = (xi.2 . qixi.1)a + (yi.2 . qiyi.1)b;
  所以有递推公式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 的**公因子的算法为辗转相除法, 或欧几里

TOP 其它信息

装  帧:平装

页  数:248

开  本:16开

纸  张:胶版纸

加载页面用时:46.8641