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

一、課程簡介

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

二、詳解

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

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

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

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

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

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

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

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

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

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

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 的某個(gè)選擇使得 am+bn<0 ，那么就用 -m 和 -n 替換 m 和 n)，井式排序原則斷言 S 有一個(gè)最小的成員，例如 d=as+bt。我們斷言 d=gcd(a,b)。為了驗(yàn)證這一說法，使用除法運(yùn)算法則寫出 a=dq+r，其中 0<=r0，那么 r=a-dq=a-(as+bt)q=a-asq-btq=a(1-sq)+b(-tq) 它在 S 中，這與 d 是 S 的最小成員這一事實(shí)相矛盾?，F(xiàn)在假設(shè) d' 是 a 和 b 的另一個(gè)公因子，并寫成 a=d'h 和 b=d'k。那么 d=as+bt=(d'h)s+(d'k)t=d'(hs+kt) 所以 d' 是 d 的除數(shù)。

歐幾里得定理：如果 p 是一個(gè)能整除 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 除以這個(gè)等式的右邊，所以 p 也除以 b。

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

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