中圖網小程序
一鍵登錄
更方便
本類五星書更多>
-
>
宇宙、量子和人類心靈
-
>
氣候文明史
-
>
南極100天
-
>
考研數學專題練1200題
-
>
希格斯:“上帝粒子”的發明與發現
-
>
神農架疊層石:10多億年前遠古海洋微生物建造的大堡礁
-
>
聲音簡史
公鑰密碼學的數學基礎(第二版) 版權信息
- ISBN：9787030731111
- 條形碼：9787030731111 ; 978-7-03-073111-1
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
公鑰密碼學的數學基礎(第二版) 內容簡介
書中介紹了公鑰密碼學中涵蓋的數論代數基本知識與理論體系：第1章至第6章分別介紹了初等數論基礎知識，主要包括同余、剩余類、原根和連分數的基本理論以及在公鑰密碼中的應用等；第7章至第9章描述了群、環、域三個基本的代數結構及其性質；第10章介紹了與密碼學相關的計算復雜性理論及基本數學算法；第11章簡單介紹了格理論及格密碼分析的基本方法。
公鑰密碼學的數學基礎(第二版) 目錄
目錄
第二版前言
**版序
**版前言
第1章 整除 1
1.1 整除的概念 1
1.2 *大公因子與*小公倍數 5
1.3 Euclid算法 10
1.4 求解一次不定方程——Euclid算法應用之一 13
1.5 整數的素分解 14
1.6 使用SageMath進行整除相關的計算 20
習題1 21
第2章 同余 23
2.1 同余的基本概念和基本性質 23
2.2 剩余類與剩余系 26
2.3 Euler定理 31
2.4 Wilson定理 34
2.5 使用SageMath進行同余相關的計算 37
習題2 38
第3章 同余方程 40
3.1 一元高次同余方程的概念 40
3.2 一次同余方程 43
3.3 一次同余方程組與孫子定理 44
3.4 一般同余方程 47
3.5 二次剩余 49
3.6 Legendre符號與acobi符號 52
3.7 使用SageMath求解同余方程 59
習題3 59
第4章 指數與原根 61
4.1 指數及其性質 61
4.2 原根及其性質 64
4.3 指標、既約剩余系的構造 67
4.4 n次剩余 72
4.5 使用SageMath進行指數與原根相關的計算 75
習題4 76
第5章 素數分布的初等結果 78
5.1 素數的基本性質與分布的主要結果介紹 78
5.2 Euler恒等式的證明 81
5.3 弱形式素數定理的證明 83
5.4 素數定理的等價命題 90
5.5 使用SageMath進行素數分布相關的計算 93
習題5 94
第6章 簡單連分數 95
6.1 簡單連分數及其基本性質 95
6.2 實數的簡單連分數表示 98
6.3 連分數在密碼學中的應用——對RSA算法的低解密指數攻擊 103
6.4 使用SageMath進行簡單連分數相關的計算 104
習題6 105
第7章 近世代數基本概念 106
7.1 映射 106
7.2 代數運算 109
7.3 帶有運算集合之間的同態映射與同構映射 111
7.4 等價關系與分類 112
習題7 113
第8章 群論 114
8.1 群的定義 114
8.2 循環群 116
8.3 子群、子群的陪集 117
8.4 同態基本定理 121
8.5 有限群的實例 124
8.6 使用SageMath進行群論相關的計算 127
習題8 128
第9章 環與域 129
9.1 環的定義 129
9.2 整環、域、除環 131
9.3 子環、理想、環的同態 135
9.4 孫子定理的一般形式 140
9.5 歐氏環 142
9.6 有限域 144
9.7 商域 145
9.8 使用SageMath進行環與域相關的計算 148
習題9 151
第10章 公鑰密碼學中的數學問題 152
10.1 時間估計與算法復雜性 152
10.2 素檢測 158
10.3 分解因子問題 160
10.4 RSA問題與強RSA問題 161
10.5 二次剩余 162
10.6 離散對數問題 164
10.7 使用SageMath求解公鑰密碼學中的數學問題 166
習題10 167
第11章 格的基本知識 168
11.1 基本概念 168
11.2 格相關的計算問題 169
11.3 格基約化算法 171
11.4 LLL算法應用 173
11.5 使用SageMath進行格相關的計算 179
習題11 179
參考文獻 181
展開全部
公鑰密碼學的數學基礎(第二版) 節選
第1章整除 整除是數論中的基本概念.本章主要介紹與整除相關的一些基本概念及其性=質.這些基本概念如整除、因子、公因子、*小公倍數、分解因子等，早在中學時=期已被大家所熟悉.在這里我們將給出這些概念的嚴格的數學定義.通過掌握這=些概念的數學定義及相關性質，我們可以進一步解決許多初等數論里與整除相關=的問題.整除理論內容豐富，解決問題方法靈活.它不僅是數論、代數的基礎，而=且在密碼學中有很廣泛的應用，如整數的素分解、Euclid算法求*大公因子等問=題在密碼學中都有極其重要的應用. 1.1整除的概念 我們用集合Z表示全體整數組成的集合，N表示自然數的全體.下面給出整除的定義. 定義1.1設a，b∈Z，如果存在q∈Z，使得b=aq，那么，=就說b可被a整除，記作a|b，稱b是a的倍數，a是b的因子(也=可稱為約數、除數).否則就說b不能被a整除，或a不整除b，記作a.b. 由定義及乘法的運算規律，立即可得出整除的以下性質： 定理1.2設a，b，c∈Z，則 (1)a|b且; (2)a|b且對任意的有; (3)若m∈Z且，則; (4)a|b且; (5)若，則. 證明(1)由于a|b，根據整除的定義知存在q1，使.同樣存在q2使得，從而即(2)由知，存在r，s使得.對任意的x，y∈Z有，故.反之顯然. 性質(3)—(5)證明類似，讀者可以自己補出證明. 顯然±1，±b是b的因子，我們稱其為b的顯然因子，其他因子稱為b的非顯然因子，或真因子.由此我們可引出素元的定義. 定義1.3設整數.如果p除了顯然因子±1，±p外沒有其他的因子，那么p就稱為素元(常稱為素數)，若整數，且a除顯然因子外還含有真因子，則稱a為合數. 注一般情況下，素數我們只取正的. 下面我們介紹幾個關于素數的定理. 定理1.4若a為合數，則a的*小真因子為素數. 證明由a為合數知a>2.設d為a的*小真因子.若d不為素數，則=存在d的真因子d′，使d′|d，由性質(1)知，與d為*小真因子矛盾.定理=得證. 定理1.5素數有無窮多個. 證明假設只有有限個素數，設為p1，p2， ，pk.考慮a=p1p2 pk+1，由=定理1.4知，整除a的*小真因子一定為素數，記為p.由于p為素數，因而p必=等于某個pi，所以p|a，p|p1p2 pk同時成立，從而p|1，這與p是素數矛盾.因此=定理得證. 將素數從小到大排列，假設pn表示第n個素數，π(x)表示不超過x的素數=個數.雖然我們無法知道pn的確切位置，但是，我們可以得到pn的弱上界估計下面定理僅描述了pn的一個弱上界估計與π(x)的一個弱下界估計.而對于π(x)=更為精確的估計，超出本書的討論范圍，有興趣的讀者可參考文獻[23]. 定理1.6將全體素數按從小到大的順序排列，則第n個素數pn與π(x)分別有以下結論： (1); (2). 證明(1)我們用歸納法來證明定理的**部分成立.當n=1時，命題 顯然成立.假設對于時，命題成立.當n=k+1時，由定理1.4知，由歸納假設. 于是命題(1)得證. (2)對于任意的x.2，必存在唯一的整數n，使得，從而由**部分結論得定理得證. 初等數論還有一個*基本的結論：帶余除法定理，它是整除的一般情形，也是Euclid算法的基礎. 定理1.7設a，b是兩個給定的整數且.那么一定存在唯一的一對整數q與r，滿足，其中，r被稱為b被a除后的*小非負余數.此外a|b的充要條件是r=0. 證明唯一性：若還有整數q′與r′滿足. 則有及.由整除的性質立即可得，所以唯一性成立. 存在性：當a|b時，可取.當時，考慮集合，容易看出，集合T中必有正整數例如，取中必有一個*小正整數，記為. 我們來證明必有t0|a|，則. 顯見，這和t0的*小性矛盾.取就滿足要求.顯然，a|b的充要條件是r=0.定理得證. 下面利用帶余除法對整數進行分類.設a.2是給定的正整數，.對給定的j，被a除后余數等于j的全體整數是這些整數組成的集合記為Sa，j.集合滿足以下兩個性質： (1)中的任兩個Sa，j兩兩不相交，即. (2)中所有子集的并等于Z，即. 這樣按被a除后所得不同的*小非負余數，將全體整數分成了兩兩不相交的a個類.這種分類對于一些數學問題的處理會帶來很大的方便. 例1.8對于任意整數x，x3被9除后所得的*小非負余數是0，1，8. 證明對于任意的整數x，存在使得.因此只需檢驗0至8之間的數即可. 例題得證. 例1.9設是給定的正整數.那么，任一正整數n必可唯一表示為，其中整數.這就是正整數n的a進制表示. 證明對正整數n必有唯一的，使.由帶余除法知，必有唯一的q0，r0滿足. 若k=0，則必有，所以結論成立.假設時結論成立. 那么當k=m+1時，上式中的q0必滿足.由假設知，其中.因而有. 即結論對m+1也成立.定理得證. 例1.10將十進制整數27182寫成十二進制的形式. 解進行下面的算法 得 1.2*大公因子與*小公倍數 *大公因子與*小公倍數是整除理論中兩個*基本的概念. 本節主要討論*大公因子與*小公倍數的概念及其性質. 定義1.11設a1，a2是兩個整數.如果d|a1且，那么就=稱d是a1和a2的公因子.一般地，設a1，a2， ，ak是k個整=數.如果，那么就稱d是a1，a2， ，ak的公因子. 定義1.12設a1，a2是兩個不全為零的整數，d是a1和a2的一個正公因=子，若對任意的d′|a1，d′|a2都有d′|d成立，則稱d為a1和a2的*大公因子，記=作d=(a1，a2)或d=gcd(a1，a2).一般地，設a1，a2， ，ak是k個不全為零=的整數，d是a1，a2， ，ak的一個正公因子，若對任意的a1，a2， ，ak的公因=子d′，有d′|d，則稱d為a1，a2， ，ak的*大公因子，記作(a1，a2， ，ak)或. 從定義1.12知，*大公因子即是公因子中*大的一個，*大公因子存在性的證明可參看文獻[20].*大公因子有下面性質. 定理1.13 (1)對任意整數. (2)設m>0，則. (3)設a1，a2是兩個不全為零的整數，則更一般地，有. (4). (5). 定理的結論比較顯然，證明留給讀者補出.定理提供了一種求解*大公因子的很簡單、實用的方法. 例1.14對任意的整數m，有. 例1.15設a>2是奇數.證明 (1)一定存在正整數d.a.1，使得a|2d.1. (2)設d0是滿足a|2d.1的*小正整數，那么其中h∈N)的充要條件是. (3)必有正整數d使. 證明(1)考慮以下a個數. 由及帶余除法知，對每個，存在使得. 所以a個余數r0，r1， ，ra.1僅可能取個值.根據鴿巢原理知其中必有兩 個余數相等，不妨設且ri=rk，因而有. 由(a，2)=1，推出.取就滿足要求. (2)充分性是顯然的，需證必要性.同樣由帶余除法定理得
書友推薦
- >
羅曼·羅蘭讀書隨筆-精裝
- >
月亮虎
- >
唐代進士錄
- >
巴金－再思錄
- >
名家帶你讀魯迅:朝花夕拾
- >
姑媽的寶刀
- >
回憶愛瑪儂
- >
羅庸西南聯大授課錄
本類暢銷
