數(shù)論是一個廣闊而迷人的數(shù)學領域，有時也被稱為 "高等算術"，包括對整數(shù)性質(zhì)的研究。素數(shù)和素因式分解在數(shù)論中尤為重要，包括托天函數(shù)在內(nèi)的許多函數(shù)也是如此。如果大家在這門課程中并沒有取得自己想要的成績，可以了解一下數(shù)論與密碼學課程1V1輔導。

一、課程簡介

密碼學是數(shù)學的一個分支，它提供了通過可能不安全的渠道發(fā)送信息的保密交換技術。本單元介紹了理解最常用的現(xiàn)代公鑰密碼系統(tǒng)的基礎數(shù)學所需的初等數(shù)論工具。主題包括歐幾里得算法、費馬小定理、中文余數(shù)定理、莫比烏斯反演、RSA 密碼系統(tǒng)、Elgamal 密碼系統(tǒng)和 Diffie-Hellman 協(xié)議。此外，還討論了計算復雜性問題。

二、詳解

密碼學是安全傳輸信息的過程，它不會讓任何不想要的第三方理解信息。密碼學的應用已有數(shù)千年的歷史。數(shù)論和密碼學有著千絲萬縷的聯(lián)系，我們將在下面的課程中看到這一點。

首先，您需要熟悉密碼學第 2 課，其中包括質(zhì)數(shù)、最大公約數(shù)、模運算等概念。請參見密碼學第 2 課。

如何找到質(zhì)數(shù)?幾個世紀前，人們認為如果 n 是整數(shù)，那么 n2+n+41 總是質(zhì)數(shù)。這對 n=0,1,2,...38,39 恰好是正確的，但對 n=40 卻不正確，對 n=41 顯然也不正確(加法的每一部分都有一個 41 的因數(shù))。

費馬(1601-1665 年)猜想，對于所有大于或等于 0 的 n，數(shù) Fn=22n+1 都是素數(shù)。然而，他的猜想到此為止，因為 F5=4,294,967,297 。歐拉后來發(fā)現(xiàn) 641 除以 F5，因此它不是質(zhì)數(shù)。到目前為止，已知的費馬素數(shù)只有費馬自己最初發(fā)現(xiàn)的五個。欲了解更多信息，請參閱《費馬數(shù)》。

勒讓德和高斯分別猜想，素數(shù) <=n 的個數(shù)(記為 Π(n))約為

n/(1+1/2+1/3+...+1/n)

這一猜想現(xiàn)在被稱為質(zhì)數(shù)定理，由哈達瑪于 1896 年證明。有關這方面的更多確切信息，請參閱質(zhì)數(shù)定理。

問題集 1 考慮到為什么 n2+n+41 不能給出 n=41 的質(zhì)數(shù)，證明沒有一個多項式能給出每個整數(shù) n 的質(zhì)數(shù)。

證明 (1+1/2+1/3+...+1/n+...) 無窮大。假設質(zhì)數(shù)定理成立，那么當 n 變大時，質(zhì)數(shù)與整數(shù)之比會是多少?

整數(shù)的一個重要性質(zhì)是 "井序原則"，我們會發(fā)現(xiàn)它非常有用，它指出每個正整數(shù)集合都包含一個最小的成員。由于這一性質(zhì)無法從算術的一般性質(zhì)中得到證明，我們將把它作為一個公理。

GCD 是線性組合：對于任何非零整數(shù) a 和 b，都存在整數(shù) s 和 t，使得 gcd(a,b)=as+bt。此外，gcd(a,b)是形式為 as+bt 的最小正整數(shù)。

證明考慮集合 S={am+bn | m,n 為整數(shù)且 am+bn>0}.由于 S 顯然是非空的(如果 m 和 n 的某個選擇使得 am+bn<0 ，那么就用 -m 和 -n 替換 m 和 n)，井式排序原則斷言 S 有一個最小的成員，例如 d=as+bt。我們斷言 d=gcd(a,b)。為了驗證這一說法，使用除法運算法則寫出 a=dq+r，其中 0<=r0，那么 r=a-dq=a-(as+bt)q=a-asq-btq=a(1-sq)+b(-tq) 它在 S 中，這與 d 是 S 的最小成員這一事實相矛盾。現(xiàn)在假設 d' 是 a 和 b 的另一個公因子，并寫成 a=d'h 和 b=d'k。那么 d=as+bt=(d'h)s+(d'k)t=d'(hs+kt) 所以 d' 是 d 的除數(shù)。

歐幾里得定理：如果 p 是一個能整除 ab 的質(zhì)數(shù)，那么 p 能整除 a 或 p 能整除 b。

證明：由于 p 不除 a(并且 p 是質(zhì)數(shù))，a 和 p 是相對質(zhì)數(shù)，所以 gcd(a,p)=1，并且根據(jù)前述，存在整數(shù) s 和 t，使得 1=as+pt。那么 b=abs+ptb，由于 p 除以這個等式的右邊，所以 p 也除以 b。

最小公倍數(shù)：兩個非零整數(shù) a 和 b 的最小公倍數(shù)是同時是 a 和 b 的倍數(shù)的最小正整數(shù)。

海馬課堂專業(yè)課程輔導做出以下新改變啦：
?試聽課全面升級，不滿意退50%，
?課程輔導產(chǎn)品升級，贈送考前保障呦
?輔導不滿意可以隨心退！
海馬課堂，3500+嚴選碩博學霸師資，針對學生的薄弱科目和學校教學進度，匹配背景相符的導師，根據(jù)學生情況進行1V1專屬備課，上課時間靈活安排，中英雙語詳細講解課程中的考點、 難點問題，并提供多方位的課后輔導，輔助學生掌握全部課程知識，補足短板。