數論 數論是一個歷史悠久的數學分支，它是研究整數的性質及關係的一門學問。數學一直被認為是「科學之皇后」，而數論則更被尊為「數學之皇后」。

Presentation on theme: "數論 數論是一個歷史悠久的數學分支，它是研究整數的性質及關係的一門學問。數學一直被認為是「科學之皇后」，而數論則更被尊為「數學之皇后」。"— Presentation transcript:

1 數論 數論是一個歷史悠久的數學分支，它是研究整數的性質及關係的一門學問。數學一直被認為是「科學之皇后」，而數論則更被尊為「數學之皇后」。

2 數論是研究整數性質的一門很古老的數學分支， 其初等部分是以整數的整除性為中心的，包括整除性、不定方程、同餘式、連分數、素數（即質數）分佈 以及數論函數等內容，統稱初等數論（elementary number theory）。 

3 初等數論的大部份內容早在古希臘歐幾里德的《 幾何原本》中就已出現。歐幾里得證明了素數有無窮多個，他還給出求兩個自然數的最大公約數的方法， 即所謂歐幾里得算法。我國古代在數論方面亦有傑出之貢獻，現在一般數論書中的「中國剩餘定理」正是我國古代《孫子算經》中的下卷第26題，我國稱之為 「孫子定理」。 

4 近代初等數論的發展得益於費馬、歐拉、拉格朗 日、勒讓德和高斯等人的工作。1801年，高斯的《算術探究》是數論的劃時代傑作。高斯還提出：「數學 是科學之王，數論是數學之王」。可見高斯對數論的高度評價。 

5 由於自20世紀以來引進了抽象數學和高等分析的 巧妙工具，數論得到進一步的發展，從而開闊了新的研究領域，出現了代數數論、解析數論、幾何數論等 新分支。而且近年來初等數論在計算機科學、組合數學、密碼學、代數編碼、計算方法等領域內更得到了 廣泛的應用

6 數系的發展

7 在文字產生之前，人類就已形成數的概念。由小石子、竹片、貝殼、……到 現在使用的自然數、整數、有理數、實數、複數……，經過了漫長歲月的演化及 經驗的累積。

8 那麼，到底「數」是怎麼來的呢？古中國的傳說是皇帝命埭首作數， 而西方則有上帝造數的說法；其實，「數」是人們在長期的數「ㄕㄨ v 」的經驗中 產生的，所以說：「數從數中生。」

9 自然數 基於基數的自然數概念可溯源於原始人類用匹配方法計數。古希臘人用小石卵記畜群的頭數或部落的人數 。

10 事實上，英文calculate（計算）一詞是從希臘文calculus（石卵）演變來的。中國古藉《易．系辭》中說：「上古結繩而治，後世聖人易之以書契。」這些都是匹配計數法的反映。但直至1889年，皮亞諾才建立自然數序數理論。

11 1.基數(cardinal number)：可以用正整數來表示某一特定群體中各體的個數。例如：蘋果有五顆。
2.序數：正整數也可以用來標示個體在群體中的位置，或個體與群體中其他個體間的次序關係。例如：張小明賽跑得到第三名。

12 何謂整數？ 在整數系中，自然數為正整數，稱0為零，稱-1，-2，-3，…，-n，… 為負整數。正整數，零與負整數構成整數系。

13 正整數是從古代以來人類計數（counting）的工具。可以說，從「一頭牛，兩頭牛」或是「五個人，六個人」抽象化成正整數的過程是相當自然的。事實上，我們有時候把正整數叫做自然數（the natural numbers）。

14 零不僅表示「無」，更是表示空位的符號。中國古代用算籌計算數並進行運算時，空位不放算籌，雖無空 位記號，但仍能為位值記數與四則運算創造良好的條件。印度－阿拉伯命數法中的零（zero）來自印度的（sunya）字，其原意也是「空」或「空白」。

15 中國最早引進了負數。《九章算術．方程》中論述的「正負數」，就是整數的加減法。減法的需要也促進了負整數的引入。減法運算可看作求解方程a+x=b，如果a，b是自然數，則所給方程未必有自然數解。為了使它恆有解，就有必要把自然數系擴大為整數系。

16 正整數、零，和負整數合稱整數（the integers）。整數是人類能夠掌握的最基本的數學工具。十九世紀德國偉大數學家 Kronecker因此說：「只有整數是上帝創造的，其他的都是人類自己製造的。

17 凡能寫成整數比(分數)的數就稱為有理數。為什麼叫它「有理數」呢？原 來，希臘人稱整數比為“ratio-nal number”，意思是成比(ratio)的數，

18 但 “rational”這個詞本來有“有理”、“合理”的意思，所以“rational number” 這個詞在我國就被譯成「有理數」了。也就是說，有理數更明確的意義就是「能 寫成整數比的數」。

19 在數學史上，從有理數擴充到實數的過程中曾發生了一件冤案，就是當畢達 哥拉斯學派在希臘興盛之時，主張「宇宙萬物皆整數」，他們認為世上的一切都 具有整數或者整數比那樣的性質。

20 但是，學派中的一位學生希伯斯發現邊長為 1 的正方形的對角線長，無法用整數比表示出來，並且還加以證明，這是一個非同 小可的發現，它沉重地打擊了畢達哥拉斯學派的信條，為了消除異端，他們把希 伯斯投進了大海。

21 今日，我們都知道希伯斯發現的數就是無理數中的 2 ，它和其他類似的無 法表成整數比的數，組成了無理數，然後和有理數組成了實數。

22 2 個蘋果、 3 1 個橘子，我們都可以了解，但是  根號負5 個水梨是什麼意思呢？負 數的平方根(虛數)不易理解，也無法比較大小，但是卻可以按數學的法則做加減 乘除的運算，更重要的是，承認了虛數，任何次的代數方程式就都有解了

23 法國數學家笛卡兒把負數的平方根稱為「虛數」，意思是可以算作數，不過是虛 的，這種說法充分表達了當時數學家矛盾的心情。

24 後來經過大數學家尤拉對虛數的存在加以肯定，並規定了 根號負1 等於 i 為虛數單 位；以及大數學家高斯把虛數和實數合併成複數，並給出了複數的幾何表示，才 終於奠定了虛數在數學中的地位。

25 質數

26 人們一般把整數看作最基本的數，其他的數都由整數衍生出來。然而專門研究整數的人卻不是這樣看，他們認為質數才是最基本的數，因為任何大於 1 的正整數，若它不是質數，便是若干質數的積。中國古代的數學家把質數叫做「數根」，意思是數的根本。

27 一個專門研究整數的數學分支叫「數論」，在這個領域裏集中研究的問題正是與質數有關。

28 數學篩子 研究質數，首先得設法找出質數。大約在二千多年前，古代希臘數學家愛拉托散尼（Eratosthenes）把一張寫著自然數列的羊皮紙緊在一個框上，然後用刀子逐一挖掉 2 的倍數、3 的倍數、5 的倍數等等，從而列出了首幾個質數。。

29 由於挖去了合成數後，羊皮紙上留下了一個一個的洞眼，使整個羊皮紙猶如一個篩子，合成數好像都通過篩子篩掉了，而質數則保留了下來，因此後人就稱這種尋找質數的方法叫「愛拉托散尼篩法」

30 質數是無限的 在愛拉托散尼發明篩法不久，希臘數學界出現了一場關於質數是有限還是無限的辯論。

31 一天，亞歷山大里亞大學數學教授歐幾里得 (Euclid) 發現了一個質數有無限多個的証明，而且十分簡單。如果質數只有有限個，那麼我們就可以把它們一一寫出來，比如 P1、P1、……、Pn，

32 但看 P1P2. Pn + 1 這個數，它顯然不能被P1、P2、……、Pn 任何一個整除。如果 P1P2
但看 P1P2...Pn + 1 這個數，它顯然不能被P1、P2、……、Pn 任何一個整除。如果 P1P2...Pn + 1 是質數，那麼 P1P2...Pn + 1 是除 P1、P2、……、Pn 外的另一個更大的質數；

33 如果 P1P2...Pn + 1 是合成數，那麼它必定被另一個 質數整除，而這個質數卻不是在 P1、P2、……、Pn 之內。以上無論那個可能性，都是自相矛盾的。換句話說，質數有無限多個。

34 烏蘭現象 如果我們能把所有質數用一條公式表示出來，那是多麼美好的事！但顯然這不是容易的事，原因是質數的分佈太散漫，沒有規則。

35 1963 年，美國數學家烏蘭在參加一次學術會議時，因為對演講者的一篇冗長的論文不感興趣，思想開了小差。他無聊地在紙上縱棋劃線，畫出了一個個方格，他本想畫一個棋盤自己與自己對著的，但也許是數學家的癖好吧，他擺弄著擺弄著，忽而又想到數學中去了。

36 於是烏蘭劃出了 100 格子，正中間一格填上 1，以此為出發點按逆時針方自螺旋式地逐個填數。接著，又把是質數的格子圈出，他想看看如此這般地做了以後會有什麼奇特的現象。

37 突然，一個有趣的現象出現在眼前，質數似乎很喜歡擠在一條直線上。於是，他借助電子計算機打出了從 1 到 的螺旋圈，令人興奮的是這種現象仍然存在。後來人們就稱它為「烏蘭現象」。這發現有利於日後對質數的研究。

38

39 質數現象 1800 年，德國的兩位大數學家高斯（Gauss）和勒讓德爾（Legendre），分別從下面這種表的觀察中，得出一個重要的猜想。

40 表中 p(x) 表示不大於 x 的質數的個數， ln x 是 x 的自然對數。他們發現︰隨著 x 的增大，p(x) 也不斷增大；同時   這個比值隨著 x 不斷增大而不斷減少；p(x) 與   亦越來越接近。當 x 趨於無限大時，p(x) 與   的比趨於 1。這就是著名的「質數定理」。 表中 p(x) 表示不大於 x 的質數的個數， ln x 是 x 的自然對數。他們發現︰隨著 x 的增大，p(x) 也不斷增大；同時  這個比值隨著 x 不斷增大而不斷減少；p(x) 與  亦越來越接近。當 x 趨於無限大時，p(x) 與  的比趨於 1。這就是著名的「質數定理」。

41 由於當時高斯和勒讓德爾沒有給出定理的證明，所以只能稱它為「質數猜想」或「高斯 — 勒讓德爾猜想」。不過，它以如此簡明的形式，把質數的個數 p(x) 這樣一個離散的量用連續量  來表示，不能不說是一個出色的發現。

42 直到 1894 年，難題終於被法國數學家阿達瑪（Hadamard）攻克。接著，兩年後，普森（De la Vallée Poussin）又獨立地證明了質數猜想。從此，質數定理的名字才正式確立。

43

44 2008年的復活節是幾月幾日? 我們先找出一個方便記憶並且同時是星期一的日子。例如：我們知道 2001 年 1 月 1 日是星期一（這個日子的確非常容易記憶！）。然後數一數我們想要計算的日子離上述日期一共有多少天。將這個結果除以 7，如果餘數是 1，那麼就表示那天是星期一；如果餘數是 2，那麼那天便是星期二；如此類推。

45 例如：2001 年的 4 月 8 日（該年春分後的第一個月圓日），它離 1 月 1 日共 = 98 日，將 98 除以 7，剛好整除，沒有餘數，那麼我們就可以知道 4 月 8 日是星期日了。由於 4 月 8 日是星期日，那麼復活節就應該定在下一個星期日，即 7 日之後，亦即是 4 月 15 日。

46 例如：2002 年的 3 月 28 日，因為 365 + 31 + 28 + 28 = 452，452 除以 7 得餘數 4，所以那一天是星期四，該年的復活節應該在 3 日後，即 3 月 31 日。

47 上述的方法不單可以用來推算春分後月圓的日子是星期幾，它亦可以用來推算 2001 年 1 月 1 日以後任何一天是星期幾。不過很明顯，如果要推算的日期離 2001 年較遠，例如：2022 年的 2 月 2 日，那麼我們豈不是需要計算出一個很大的日數，然後才可以知道那天是星期幾嗎？

48 其實我們不必這樣做，我們祇要利用算術上一個很巧妙的方法，就可以完成這項任務了。方法就是利用加法和求餘數可以互調的性質。

49 先看看 2004 年 1 月 1 日是星期幾。2004 年的 1 月 1 日離 2001 年 1 月 1 日共 3 年零 1 日，即 = 1096 日。將這個數餘以 7，得餘數 4。留意如果我們先將 365 除以 7，我們會得到餘數是 1，而 亦等於 4。換句話說，我們可以將加法和求餘數的次序對調，所得的結果都是一樣的。

50 不過，對調後的計算量則會比前者少得多了。同時，我們亦發現，由於 365 除以 7 的餘數是 1，所以每年 1 月 1 日的星期數，都會比上年加多 1 日。當然，如果某一年是閏年，全年會再多一日，那麼到了下一年的 1 月 1 日，星期數就須加 2 了

51 回看上面的問題，由 2001 至 2021 年，一共經過了 21 年，當中有 5 個閏年，所以星期數會前移 = 26 日，接著將 = 79 除以 7，得餘數 2，因此得知 2022 年的 2 月 22 日將會是星期二。

52 再仔細看看上面的計算，我們會發現，按照加法和求餘可以互調的原理，我們其實亦可不必將 加得來，可以先求餘然後才加，即得 = 9，再餘以 7，亦可知餘數為 2。

53 應用以上原理，我們可以有一個更有效計算星期數的方法，就是預先計算每個月最後的 1 天比 1 月 1 日移前了多少天。

54 日期 離 1 月 1 日天數 除以 7 後的餘數  1 月 31 日 31 3  2 月 28(29) 日 (29) = 59(60) 3(4)  3 月 31 日 59(60) + 31 = 90(91) 6(0)  4 月 30 日 90(91) + 30 = 120(121) 1(2)  5 月 31 日 120(121) + 31 = 151(152) 4(5)

55 6 月 30 日 151(152) + 30 = 181(182) 6(0)  7 月 31 日 181(182) + 31 = 212(213) 2(3)  8 月 31 日 212(213) + 31 = 243(244) 5(6)  9 月 30 日 243(244) + 30 = 273(274) 0(1)  10 月 31 日 273(274) + 31 = 304(305) 3(4)  11 月 30 日 304(305) + 30 = 334(335) 5(6)

56 例如：想知道 2022 年 12 月 17 日是星期幾，那麼由年份可知星期數移前了 26 日，亦即 5 日，從表三知 11 月尾又再移 5 日，所以最後得 = 27，除以 7 得餘數 6，所以那天是星期六。

57 以上的計算其實是使用了一個數學家稱「同餘」的方法來進行

58 同餘理論：

59 若 m,n 為兩整數，且 m>0，則以 m 除 n 可得二整數 α 與 r，使得 
n=am+r 其中 α 稱為商，r 稱為餘數，且0 ≦r<m。若 r=0，則我們說 n 可被 m 所整除，m 為 n 之因子，n 為 m 之倍數，若一數除 1 與本身之外無其他因子，則此數稱為質數，例如 2,3,5,7,11 都是質數，4,6,9,12 卻不是質數。

60 我們定義 n 與 s 對 m 有同餘數：  n=s (mod m) 如果 n 與 s 被 m 除時有相同的餘數。例如  12=2 (mod 10) 9=2 (mod 7)

61 ，整數a與b對於模數m而言，屬於同一個剩餘類。
其具有下列性質：

62 1.同餘式經過下列運算，仍然保持同餘。 （1）兩端同乘一個整數。 （2）同餘式的兩端若取相同的正整數次方。 （3）有相同模數的兩個同餘式，兩端可以相加相減或相乘。 2.同餘式具有傳遞性。

63 數論，顧名思義，是一門研究數字性質的學問。一般所謂的數論，特指正整數(即自然數)的許多性質，像質數的分佈，方程式的正整數解，韓信點兵，及進位法都包括在數論裏面，

64 我們在小學時候學的分解因數，最大公約數也是數論的一部分，可惜因為數論在日常生活中沒有什麼直接的用處，在中學數學裏很少提到數論，一般被認為是一種「純數學」，深而無用。可是「無用之用，真乃大用」，

65 終於在一九七0年代後期，幾個電機工程師用數論的一些基本定理，製成了一種新的密碼。這種由數論所作成的密碼與以前人們所用的密碼，有著根本性質上的不同，可說是密碼史上一個空前的革新。

66 密碼通訊在軍事上的用途是大家都知道的，但由於交通的發達，在分秒必爭的工商業社會裏，商業上的情報也已成為商業盈利的主要依靠。

67 譬如說，有人早幾個小時知道什麼公司有了一種新的發明，或某兩個公司計劃合作，或某地區有物價的大波動，就可以在股票上上下其手， 轉瞬之間收進大筆的財富。因此公司本身內部及公司與公司之間的通訊都希望能對外嚴守機密。

68 但由於現在通訊無論是有線或無線都很容易被敵方竊聽，因此公司必須對情報加鎖，即所謂密碼通訊。

69 以往人們在軍事上所用的密碼其基本的形式在於「代換」與 「置換」。譬如說，我要發出下面一個消息給你，
「我有一個秘密對你說」 我就先把這幾個字換成數字，即一般電碼本上的代碼，

70 假定「我」字的代碼是3314,「有」字的代碼是1432，「一」字代碼是0001，等等，則上面那句話就成了
… 代換密碼是把 0,1,2,…,9 十個數字互換，譬如我們可以把 0 換成 2，1 換成 3，等等，若用群論的符號表示，上面的代換可寫成 

71 這個表示法是上行為 0，1，2，…，9，而下行是他們代換成的新數字，即0 2,1 3，2 5,…。因此剛才的電碼若用G法代換，則成了

72 這個表示法是上行為 0，1，2，…，9，而下行是他們代換成的新數字，即02,13，25,…。因此剛才的電碼若用G法代換，則成了 

73 這時一個不知道這個代換規則的人看到了上面的信號，他就不能從電碼本子裏找出它的原意了。置換法在於把密碼排成一種雙方都知道的形式，如下圖 

74 則發出的信號為755772433216623，同樣的，不知道這種特定圖案的人，很難解開原來的信息。

75 以代換法為例，像G這類的轉換可以有10!=3,628,800種不同的變化，假定我們可以在一分鍾內試一種代換，又假定我們的運氣中等，在試到一半時即10!/2=1,814,400時可以成功，則在不吃、不睡、不錯的情形下，我們要試3年零165天，等迷解出來的時候，仗早已打完了。

76 但這只是最基本的密碼而已，在生死關頭，更難解的密碼必然出籠，例如在代換法中，若兩位兩位的代換(即0079,0185,…)則其變化可達100
但這只是最基本的密碼而已，在生死關頭，更難解的密碼必然出籠，例如在代換法中，若兩位兩位的代換(即0079,0185,…)則其變化可達100!=9.32 x 1057種之多， 如果我們再用硬試的方法，則一百萬人同心協力也得用6 x 1048年才能試出謎底，可是地球的年齡不過只有5 x 109年而已。

77 重賞之下，天下尚沒有絕對解不開的密碼。二次大戰時， 美國密碼兼統計學家弗立得門(W. F
重賞之下，天下尚沒有絕對解不開的密碼。二次大戰時， 美國密碼兼統計學家弗立得門(W.F. Friedman)，在一年半的時間完全破獲了日軍的密碼。 在中途島一戰，美國海軍以劣勢的軍力，大勝日本皇家海軍 。另外英國也幾乎在同時解開了德軍的密碼，做到了知己知彼的優勢地位

78 過去這類密碼的特質(也可以說是缺點)在於它們是關閉式的製解法，即收發雙方都必須同時知道這種密碼的構造。因此如果在一通訊系統中有一個聯絡站被間諜滲入或被敵人佔領，則密碼的機密可能全盤暴露。

79 而現在用數論的密碼卻是公開式的 (Public-Key Cryptography)，即是只有收方知道密碼的解法， 發方只需要知道做法而已，而且這種製法可以公開。因此即使發方被捕，敵人仍榨不出解密碼的機密來，其程序是這樣的：

80 1.收方先告訴發方如何用把情報做成密碼(敵人也聽到了這個做法)
2.發方依法發出情報的密碼(敵人也聽到了這個信號) 3.收方解開此密碼為原信息(但敵人卻解不開此密碼)

81 當然把收發互換，就可以互通信息了。剛才說過這種方法最大的好處就是只有一方知道解碼的秘訣，比以前收發雙方都知道秘訣的保密性高多了，自從這類的密碼法發表之後，在美國軍事界、教育界、工商業界引起了一個蔚然大波。

82 對大多數的數論而言則是一則以喜，一則以懼。喜的是，皇天不負苦心人，一向不容易找到飯吃的數論家突然成為許多經費充裕的軍工商界所爭取的對象。費馬、尤拉以及那些一生窮困而已作古了的數論家可以含笑九泉了。

83 但懼的是，由於這些理論在軍事通訊上的價值，有關這方面的新發現已被視為國防機密而列為管制了。以往各國數論家無憂無慮發表論文自由交換意見的日子也許是一去不返了，前程固然似錦，往事卻是如煙，純數學最後一塊淨土也終於被實用所「污染」了。然而這次因密碼而推動大家對數論的研究，將在數學史上寫下了有趣的一頁。

84 凱撒密碼與數論 凱撒大帝是首先將訊息加密之軍事將領之一。其把原訊息（明碼）的字母，用不同字母來代替，其做法為有系統的將字母一一改成比它後三位的字母,例如將A改成D, 將B改成E,依此類推如下表，

85 因此若想將Hello轉成密碼，不想讓第三者知道,對照上表，將原字母移動三格轉為密碼，依此規則〝Hello〞就變成了〝khoor〞,除非知道編制密碼方式, 不然任何人看到〝khoor〞是沒有意義的。如此一來，即成功的將訊息加密而不為人知。

86 我們可利用0~25這26個數字來取代字母，如此一來，每個字母皆有一個數值替身如下
例如 A=0,B=1,C=2等等

87 引進數字0到25後， 原來的字母所對應的數字稱為為明碼，記成P, 移動三個字母後所得到的沒有明顯意義的字母, 其相對應的數字稱為密碼, 記成C。

88 移動三個字母，就可以寫成C=P+3( mod26), ，對照凱撒密碼之加密公式為C=（P+3）mod 26，而0~25為a,b,c…
移動三個字母，就可以寫成C=P+3( mod26), ，對照凱撒密碼之加密公式為C=（P+3）mod 26，而0~25為a,b,c….x,y,z之數值替身，其恰為某數整除26後之餘數所成之集合{0,1,2,3……25}，即為mod26之complete residue system。

89 其利用complete residue system對照字母，即可順利將訊息加密。當然，除了將字母向右推移三位外，我們可將數字向右推移任一位數而得下一公式：C=（P+S）mod 26；其中S為你所要推移之位數。

90 而上述移動3個字母的加密過程主要是在於+3 ，如果把它比喻成上鎖, 所以就說：加密鑰匙KE=3。

91 為了避免加密公式輕易被敵人所破解，而危及己方之安全，我們可將明碼P乘以某一整數m，而成了另一加密公式f(P)=m×P(mod26)，或是將明碼P乘以某一整數m後再向右推移s位數，成了另一個改良公式f(P)=mP+s (mod26)，但須注意的是，m數必須為ψ(26)，即m數必須為質數才可。而此處之加密鑰匙KE=<m,s>。

92 訊息經加密後，若想把密碼還原成明碼,簡易的方法亦可對照明碼與密碼互換表解密，亦即要從C得到P，利用數學方法表示為P=f-1(C)，即是求出C之反函數，則加密公式C=（P+3）mod 26，欲求出其反函數，可利用下列解密公式P=C-3 (mod26)。解密的步驟要把每一個密碼-3, 故解密鑰匙KD=-3。

93 利用反函數運算，C=5P(mod26)其解密公式P=21C(mod26)，解密鑰匙KE=5，KD=21。
而f(P)=mP+s (mod26)其解密公式為P=(m-1C-m-1s)(mod26)，解密鑰匙KD=<m-1,-m-1×s>。

94 例如: 加密計算公式是C=(5P+18) mod26 先利用歐幾里得演算法求得[5]-1=21 所以 21C=21×5×P+21×18 (mod 26) =105P+378 (mod 26) =P+14 (mod 26) 所以P =21×C-14 ( mod 26) =21C+12(mod 26) 因此P=21C+12 mod26 , KD=<21,12>。

95 if ψ(x1)= ψ(x2)，then x1=x2我們稱之為1-1函數，而單向函數即為一1-1函數，所謂單向函數簡單來說是指某函數f代入變數x時很容易計算出y=f(x), 但若已知函數值y,卻很難求得反函數x，幾乎是不可能用現有的資源，在合理的時間內去算出來的。  

96 單向函數的例子：若p、q分別是兩個很大的質數，將p×q得n倒還容易，但反過來將n因式分解卻很難。

97 而於日常生活中，亦常見到單向函數之例子，如我們利用網路下單，皆須先取得一組憑證，憑證經加密後，以加密後的形式貯存在電腦中，當您試圖下單時，電腦會先要求讀取憑證，當你指定憑證位置後，電腦即會利用單向函數計算後之資料加以比對，如相同，則完成下單。

98 而所謂單向陷門函數(one-way trap door function)：即設計單向函數的設計者，其握有 ”陷門資料”，就如同解密鑰匙一般，你想解開此一密碼，就必須擁有”陷門資料”，而擁有”陷門資料”，就可以很容易從中求得反函數。

99 有了上述單向函數及單向陷門函數概念後，我們可利用單向函數及單向陷門函數的特性，編制屬於每個個人的單向函數，而每個個人也擁有自己之解密鑰匙（陷門）。每個單向函數僅有其自己才擁有解密鑰匙（陷門），而不必擔心被別人破解。

100 如此一來，即可公佈每個使用者的加密鑰匙的密碼技術，這種公開登錄每個使用者鑰匙的密碼技術，稱為「公開密鑰密碼學」，根據這種結構設計出來的特定密碼系統，稱為「公開密鑰系統」

101 RSA密碼系統 RSA密碼系統這是公開密鑰系統中的一種，所謂RSA(R.Rivest、A.Shamir、L.Adleman)密碼系統概念如下：

102 1.開始 隨機選擇RSA密碼系統這是公開密鑰系統中的一種,兩個很大的質數p與q (譬如各有100位以上)。 計算n=p×q, 及ψ(n)=p×q-(p+q)-1 以隨機的方式產生一個e＜ψ(n), 且(e, ψ(n))=1 利用歐幾里得演算法計算e modψ(n)之乘法逆運算數d

103 2.公開：將加密鑰匙公開發表KE=<n,e>。
3.保密：藏起解密鑰匙，KD=<n,d>。 4.加密：加密函數是 C=f(P)=Pe (mod n), 5.解密：解密函數是 P=f -1(C)=Cd mod n

104 其中d就是我們的”陷門資訊”。利用單向陷門函數，我們就可以用以公開金鑰的方式，來傳送訊息，而不會被窺探出秘密。

105 數論一直到1970年代才逐漸成熟，尤其在公開密鑰系統方面，直至今日，美國政府仍在密碼研究上投注巨額經費，數論與密碼學之關係，就如同一首打油詩：「數論」這個公主，中了「無用」的魔咒而長眠，直到「密碼學」王子前來親吻，使公主醒來。可見密碼學與數論之密切關係。近代所興起之新興保密學科，皆以數論為主要基礎延伸。