信息安全數學基礎(第3版)

"陳恭亮，教授/博士生導師。上海交通大學電子信息與電氣工程學院(網絡空間安全學院)。從教30多年，北京大學數學系獲學士學位，中科院應用數學所獲碩士學位，法國聖艾蒂安大學獲博士學位,獲1997年國家教委優秀年輕教師基金。2017年上海交通大學“教書育人”三等獎。2009年上海交通大學優秀教師特等獎。2007年上海市育才獎。2007年上海交通大學優秀教師一等獎。巴黎電信大學(Telecom Paris Tech)網絡與計算機系高級訪問學者，巴黎第六大學(Universite de ParisVI)數學系高級訪問學者。科技部國際合作重大項目評審專家，科技部創新人才評審專家，科技部和上海市創新基金評審專家，教育部優秀博士論文評審專家，國家自然科學基金評審專家，2014年上海市經濟和信息化委員會專項資金評審專家(第一批)，上海市科學技術專家、武漢市科學技術專家、江蘇省科學技術專家、浙江省科學技術專家、山東省科學技術專家、重慶市科學技術專家等，EMVCO(國際支付卡組織)3DS2。0技術規範評估專家。中國密碼學會教育工作委員會第二屆委員、中國密碼學會安全協議專業委員會第三屆成員。上海市精品課程“信息安全數學基礎”負責人。主編《信息安全數學基礎》(第2版)(清華大學出版社，2014年10月第2版，累計印刷9次，總印數32000冊)，2016年獲評國家級網絡安全優秀教材獎(中央互聯網發展專項基金網絡安全專項基金)，主講中國大學MOOC課程《信息安全數學基礎》，2023年獲評國家級一流本科課程(線上課程)。主編《信息安全數學基礎》(清華大學出版社，2004年6月，累計印刷10次，總印數28500冊，普通高等教育“十一五”國家級規劃教材)，2007年上海市優秀教材一等獎，2005年上海交通大學優秀教材特等獎，2004-2005年度*****研究生教學用書。主持和參加北京電子技術研究所、“十一五”國家密碼理論發展基金、國家自然科學基金、國家重點研發計劃、中法聯合基金、國家973項目、國家863項目、上海市科委重大項目20余項。在法國《科學學報》、《密碼學報》、Designs, Codes and Cryptography、IEEE Communications Letters等學術期刊上發表文章80多篇。研究方向:網絡安全、區塊鏈、信息安全、輕量級密碼技術及應用、物聯網安全、身份認證及身份管理、安全與信任、未來互聯網等。"

目錄

第1 章整數的可除性............................................................................. 1

1.1 整除的概念、歐幾裏得除法........................................................... 1

1.1.1 整除的概念...................................................................... 1

1.1.2 Eratosthenes 篩法.............................................................. 4

1.1.3 歐幾裏得除法——最小非負余數............................................ 6

1.1.4 素數的平凡判別................................................................ 7

1.1.5 歐幾裏得除法——一般余數.................................................. 7

1.2 整數的表示................................................................................ 8

1.2.1 b 進制............................................................................. 8

1.2.2 計算復雜性...................................................................... 15

1.3 最大公因數與廣義歐幾裏得除法..................................................... 19

1.3.1 最大公因數...................................................................... 19

1.3.2 廣義歐幾裏得除法及計算最大公因數...................................... 21

1.3.3 Bézout 等式..................................................................... 23

1.3.4 Bézout 等式的證明............................................................ 26

1.3.5 最大公因數的進一步性質..................................................... 31

1.3.6 多個整數的最大公因數及計算............................................... 34

1.3.7 形為2a ?? 1 的整數及其最大公因數......................................... 35

1.4 整除的進一步性質及最小公倍數..................................................... 35

1.4.1 整除的進一步性質............................................................. 35

1.4.2 最小公倍數...................................................................... 36

1.4.3 最小公倍數與最大公因數..................................................... 37

1.4.4 多個整數的最小公倍數........................................................ 38

1.5 整數分解................................................................................... 39

1.6 素數的算術基本定理.................................................................... 40

1.6.1 算術基本定理................................................................... 40

信息安全數學基礎（第3 版）

1.6.2 算術基本定理的應用........................................................... 41

1.7 素數定理................................................................................... 45

1.8 習題........................................................................................ 46

第2 章同余........................................................................................ 47

2.1 同余的概念及基本性質................................................................. 47

2.1.1 同余的概念...................................................................... 47

2.1.2 同余的判斷...................................................................... 48

2.1.3 同余的性質...................................................................... 52

2.2 剩余類及完全剩余系.................................................................... 55

2.2.1 剩余類與剩余................................................................... 55

2.2.2 完全剩余系...................................................................... 57

2.2.3 兩個模的完全剩余系........................................................... 58

2.2.4 多個模的完全剩余系........................................................... 60

2.3 簡化剩余系與歐拉函數................................................................. 61

2.3.1 歐拉函數......................................................................... 61

2.3.2 簡化剩余類與簡化剩余系..................................................... 61

2.3.3 兩個模的簡化剩余系........................................................... 65

2.3.4 歐拉函數的性質................................................................ 65

2.4 歐拉定理、費馬小定理和Wilson 定理............................................... 68

2.4.1 歐拉定理......................................................................... 68

2.4.2 費馬小定理...................................................................... 70

2.4.3 Wilson 定理...................................................................... 71

2.5 模重復平方計算法....................................................................... 72

2.6 習題........................................................................................ 80

第3 章同余式..................................................................................... 81

3.1 基本概念及一次同余式................................................................. 81

3.1.1 同余式的基本概念............................................................. 81

3.1.2 一次同余式...................................................................... 82

3.2 中國剩余定理............................................................................. 85

3.2.1 中國剩余定理: “物不知數”與韓信點兵................................. 85

3.2.2 兩個方程的中國剩余定理..................................................... 88

3.2.3 中國剩余定理之構造證明..................................................... 89

3.2.4 中國剩余定理之遞歸證明..................................................... 90

3.2.5 中國剩余定理之應用——算法優化......................................... 93

VIII

目錄

3.3 高次同余式的解數及解法.............................................................. 98

3.3.1 高次同余式的解數............................................................. 98

3.3.2 高次同余式的提升............................................................. 100

3.3.3 高次同余式的提升——具體應用............................................ 102

3.4 素數模的同余式.......................................................................... 104

3.4.1 素數模的多項式歐幾裏得除法............................................... 104

3.4.2 素數模的同余式的簡化........................................................ 105

3.4.3 素數模的同余式的因式分解.................................................. 106

3.4.4 素數模的同余式的解數估計.................................................. 107

3.5 習題........................................................................................ 109

第4 章二次同余式與平方剩余................................................................. 110

4.1 一般二次同余式.......................................................................... 110

4.2 模為奇素數的平方剩余與平方非剩余............................................... 114

4.3 勒讓德符號................................................................................ 116

4.3.1 勒讓德符號之運算性質........................................................ 116

4.3.2 高斯引理......................................................................... 118

4.4 二次互反律................................................................................ 121

4.5 雅可比符號................................................................................ 127

4.6 模平方根................................................................................... 130

4.6.1 模p = 4k + 3 平方根........................................................... 130

4.6.2 模p 平方根....................................................................... 133

4.6.3 模m平方根...................................................................... 138

4.7 x2 + y2 = p ................................................................................ 142

4.8 習題........................................................................................ 145

第5 章原根與指標................................................................................ 146

5.1 指數及其基本性質....................................................................... 146

5.1.1 指數............................................................................... 146

5.1.2 指數的基本性質................................................................ 148

5.1.3 大指數的構造................................................................... 152

5.2 原根........................................................................................ 157

5.2.1 模p 原根.......................................................................... 157

5.2.2 模pα 原根........................................................................ 160

5.2.3 模2α 指數........................................................................ 162

5.2.4 模m原根......................................................................... 164

IX

信息安全數學基礎（第3 版）

5.3 指標及n次同余式....................................................................... 169

5.3.1 指標............................................................................... 169

5.3.2 n次同余式....................................................................... 171

5.4 習題........................................................................................ 174

第6 章素性檢驗................................................................................... 175

6.1 偽素數...................................................................................... 175

6.1.1 偽素數Fermat 素性檢驗...................................................... 175

6.1.2 無窮多偽素數................................................................... 178

6.1.3 平方因子的判別................................................................ 179

6.1.4 Carmichael 數................................................................... 180

6.2 Euler 偽素數.............................................................................. 181

6.2.1 Euler 偽素數、Solovay-Stassen 素性檢驗.................................. 181

6.2.2 無窮多Euler 偽素數............................................................ 184

6.3 強偽素數................................................................................... 185

6.3.1 強偽素數、Miller-Rabin 素性檢驗.......................................... 185

6.3.2 無窮多強偽素數................................................................ 186

6.4 習題........................................................................................ 187

第7 章連分數..................................................................................... 188

7.1 簡單連分數................................................................................ 188

7.1.1 簡單連分數構造................................................................ 188

7.1.2 簡單連分數的漸近分數........................................................ 190

7.1.3 重要常數e、π、γ 的簡單連分數............................................ 192

7.2 連分數簡介................................................................................ 194

7.2.1 基本概念及性質................................................................ 194

7.2.2 連分數的漸近分數............................................................. 197

7.3 簡單連分數的進一步性質.............................................................. 199

7.4 最佳逼近................................................................................... 200

7.5 循環連分數................................................................................ 202

7.6

p

n與因數分解........................................................................... 203

7.7 習題........................................................................................ 205

第8 章群........................................................................................... 206

8.1 群簡介...................................................................................... 206

8.1.1 基本定義......................................................................... 206

8.1.2 子群............................................................................... 214

X

目錄

8.2 正規子群和商群.......................................................................... 216

8.2.1 陪集的拉格朗日定理........................................................... 216

8.2.2 陪集的進一步性質............................................................. 219

8.2.3 正規子群和商群................................................................ 220

8.3 同態和同構................................................................................ 221

8.3.1 基本概念......................................................................... 221

8.3.2 同態分解定理................................................................... 223

8.3.3 同態分解定理的進一步性質.................................................. 224

8.4 習題........................................................................................ 226

第9 章群的結構................................................................................... 227

9.1 循環群...................................................................................... 227

9.2 有限生成交換群.......................................................................... 231

9.3 置換群...................................................................................... 232

9.4 習題........................................................................................ 237

第10 章環與理想.................................................................................. 238

10.1 環........................................................................................... 238

10.1.1 基本定義........................................................................ 238

10.1.2 零因子環........................................................................ 240

10.1.3 整環及域........................................................................ 241

10.1.4 交換環上的整除............................................................... 242

10.2 同態........................................................................................ 243

10.3 特征及素域................................................................................ 243

10.4 分式域..................................................................................... 244

10.5 理想和商環................................................................................ 246

10.5.1 理想.............................................................................. 246

10.5.2 商環.............................................................................. 251

10.5.3 環同態分解定理............................................................... 252

10.6 素理想..................................................................................... 253

10.7 習題........................................................................................ 255

第11 章多項式環.................................................................................. 256

11.1 多項式整環................................................................................ 256

11.2 多項式整除與不可約多項式........................................................... 257

11.3 多項式歐幾裏得除法.................................................................... 259

11.4 多項式同余................................................................................ 264

XI

信息安全數學基礎（第3 版）

11.5 本原多項式................................................................................ 268

11.6 多項式理想................................................................................ 271

11.7 多項式結式與判別式.................................................................... 271

11.8 習題........................................................................................ 275

第12 章域和Galois 理論........................................................................ 276

12.1 域的擴張................................................................................... 276

12.1.1 域的有限擴張.................................................................. 276

12.1.2 域的代數擴張.................................................................. 279

12.2 Galois 基本定理.......................................................................... 282

12.2.1 K-同構.......................................................................... 282

12.2.2 Galois 基本定理概述......................................................... 285

12.2.3 基本定理之證明............................................................... 289

12.3 可分域、代數閉包....................................................................... 290

12.3.1 可分域........................................................................... 290

12.3.2 代數閉包........................................................................ 291

12.4 習題........................................................................................ 291

第13 章域的結構.................................................................................. 292

13.1 超越基..................................................................................... 292

13.2 有限域的構造............................................................................. 292

13.3 有限域的Galois 群....................................................................... 295

13.3.1 有限域的Frobenius 映射..................................................... 295

13.3.2 有限域的Galois 群概述...................................................... 299

13.4 正規基..................................................................................... 299

13.5 習題........................................................................................ 303

第14 章橢圓曲線.................................................................................. 304

14.1 橢圓曲線簡介............................................................................. 304

14.2 加法原理................................................................................... 307

14.2.1 實數域R 上的橢圓曲線...................................................... 308

14.2.2 素域Fp(p > 3) 上的橢圓曲線E ............................................ 310

14.2.3 域F2n(n ? 1) 上的橢圓曲線E, j(E) 6= 0 ................................ 318

14.3 有限域上的橢圓曲線的階.............................................................. 321

14.4 重復倍加算法............................................................................. 321

14.5 習題........................................................................................ 323

XII

目錄

第15 章AKS 素性檢驗........................................................................... 324

附錄A 三個數學難題............................................................................ 326

附錄B 周期序列.................................................................................. 327

附錄C 前1280 個素數及其原根表............................................................ 328

附錄D F359 ......................................................................................... 329

附錄E F28 = F2[x]/(x8 + x4 + x3 + x2 + 1) ................................................ 330

附錄F F28 = F2[x]/(x8 + x4 + x3 + x + 1) ................................................. 331

參考文獻............................................................................................... 332