TAAZE 讀冊生活
博客來
金石堂
蝦皮商城
樂天書城
iRead灰熊愛讀書
誠品網路書店專欄 擴張版輾轉相除法
輾轉相除法為導出2個自然數的最大公因數的演算法。它比質因數分解可以更有效率地計算。如果想在輾轉相除法中，找尋2個自然數 的最大公因數，則可利用以下步驟。
設 除以 ，餘數為 。
若 ，則最大公因數即為 ，計算即完成。
若 ，則 的組合置換為 和 ，然後再回到最初的步驟。
只要重覆 到 的步驟，餘數為0時，除數即為最大公因數。換句話說，得到餘數為0前的一個步驟中所得到的餘數即為最大公因數。
舉個實例，請以輾轉相除法求出1365和77的最大公因數。
1365＝17×77＋56 （← 依1365÷77＝17餘56的計算可知）
77＝1×56＋21 （← 依77÷56＝1餘21的計算可知）
56＝2×21＋14 （← 依56÷21＝2餘14的計算可知）
21＝1×14＋ （← 依21÷14＝1餘7的計算可知）
14＝2× ＋0 （← 依14÷7＝2餘0的計算可知）
因此，最大公因數為7。只要依步驟計算便可確實得到結果，因此可讓人感到輾轉相除法的實用性。
一次不定方程式*的解之計算
接下來，對互質的20和17，請以輾轉相除法求最大公因數。
20＝1×17＋3（1）
17＝5×3＋2（2）
3＝1×2＋1（3）
2＝2×1＋0
由於直接可看出最大公因數為1，似乎並不需要使用輾轉相除法。
然而，為求出結果的算式卻具有相當大的利用價值喔！
*不定方程式：Diophantine equation。
首先，將式（1）、（2）、（3）移項，得到下列的3個式子。
（4）
＝ （5）
＝1（6）
接下來，將式（5）代入式（6）的 中，請注意3和17。
× ＝ 3 （7）
接著，將式（4）代入式（7）的 3 中，請注意20和17。
6× 3
然後，將此一連串的步驟所得的結果改寫如下。
將上式改寫為 ，而符合 的數皆為整數。這種形式的方程式就稱為一次不定方程式，可求出整數解的 和 。
也就是說，利用輾轉相除法的計算過程，、 時，可得一次不定方程式的整數解。此方法即為擴張版輾轉相除法，是非常具有利用價值的運算法。
一般而言，若設 和 為非0的整數，且 和 的最大公因數為 ，則一次不定方程式
有整數解，而且可利用擴張版輾轉相除法求出一組解。然而，一次不定方程式的解並不僅有1組。方程式的所有的整數解皆可利用任意的整數 表示如下。
（8）
以模數運算計算倒數
若利用式（8）中所表示的解的公式，則一次不定方程式 的所有整數解可表示如右。
（6＋17（9）
時，解為。
將此代入一次不定方程式 。
移項並整理式子。
（10）
若仔細看式（10），就可得知實際上它和下式意義相同。
17×13＝1mod 20（11）
在第168頁中，mod 的情況下，說明了「模數 中，解密金鑰 為加密金鑰 的乘法逆運算數」。意即，關於式（11）的模數20中，13為17的乘法逆運算數。
也就是說，若使用擴張版輾轉相除法，則可高效率地導出模數運算中的倒數。由於在公開金鑰密碼中，為了產生祕密金鑰（解密金鑰），算出倒數是必須的，因此密碼的世界中，也會讓擴張版輾轉相除法大大發揮。
雖可求出17mod 20的倒數 ，然而又該如何求出16mod 20的倒數為 呢？由於16和20的最大公因數為4，因此可用前述方法求出 。但是，為了求出倒數的一次不定方程式 時，則由於左式勢必為4的倍數，因此不存在整數解。換句話說，若在2個數非為互質的情況下，則無法求出倒數。藉由擴張版輾轉相除法導出倒數的方法，只能在2數為互質的情況下才成立。
最後，以輾轉相除法列出實際求出模數1001中，73的倒數 的計算過程。首先，以輾轉相除法，求出73和1001的最大公因數。
1001＝13×73＋52
73＝1×52＋21
52＝2×21＋10
21＝2×10＋1
10＝10×1＋0
因此可知，73和1001的最大公因數為1，也就表示73和1001互質。接下來，將這些式子改寫為求餘數的式子。
（12）
（13）
（14）
（15）
將式（14）代入式（15）取代10。
（16）
將式（16）改寫為52和21的組合。
（17）
將式（13）代入式（17）取代21。
（18）
將式（18）改寫為73和52的組合。
（19）
將式（12）代入式（19）取代52。
（20）
將式（20）改寫為1001和73的組合。
（21）
將式（21）移項。
由於此和96×73＝1mod 1001意義相同，因此模數1001中的73的倒數 為96。
| FindBook |
有 9 項符合
世界第一簡單密碼學（修訂版）的圖書 |
| 圖書選購 |
| 圖書館借閱 |
| 國家圖書館 | 全國圖書書目資訊網 | 國立公共資訊圖書館 | 電子書服務平台 | MetaCat 跨館整合查詢 |
| 臺北市立圖書館 | 新北市立圖書館 | 基隆市公共圖書館 | 桃園市立圖書館 | 新竹縣公共圖書館 |
| 苗栗縣立圖書館 | 臺中市立圖書館 | 彰化縣公共圖書館 | 南投縣文化局 | 雲林縣公共圖書館 |
| 嘉義縣圖書館 | 臺南市立圖書館 | 高雄市立圖書館 | 屏東縣公共圖書館 | 宜蘭縣公共圖書館 |
| 花蓮縣文化局 | 臺東縣文化處 |
|
|
圖書介紹 - 資料來源：TAAZE 讀冊生活 評分：
圖書名稱：世界第一簡單密碼學（修訂版）
網路為現代人帶來無限便利，
「密碼」已然成為守護安全的利器。
但是關於密碼，我們了解多少？
本書將從密碼基礎知識至實際應用方法，
層層剝開密碼的神秘面紗！
有絕對安全的密碼嗎？
如何防止密碼被盜用？
數學系、工程師必讀！
密碼學基礎知識，搭配本書一看就懂！
密碼無所不在，一點就通！
現代人深度依賴網路，
上網購物、彈指間買賣股票、使用手機轉帳、網路銀行交易……
網路的普及使我們的生活更便利，
但你是否想過如何保護網路上的重要資訊呢？
密碼的技術大幅發展，這不僅是資訊安全相關專家的研究領域，
對生活於網路時代的我們而言，了解密碼也是必要知識。
本書用生動漫畫，解說密碼技術的構造與功能，也期望藉此讓讀者輕鬆理解密碼技術上不可或缺的複雜數學。
第１章 密碼學的基礎
第２章 共通金鑰（對稱金鑰）加密系統
第３章 公開金鑰加密系統
第４章 實際的密碼應用
作者簡介：
三谷 政昭 (Mitani Masaaki)
工學博士。
生於日本廣島縣尾導市（舊豐田都）) 瀨戶田町。1974年畢業於東京工業大學工學部電子工學科。
曾任東京工業大學工學部助手，現為東京電機大學工學部資訊通訊工學科教授。
專業領域為數位訊號處理工學、通訊工學、教育工學。
<主要著作>
《數位訊號處理入門》(OHM社)
「以Scliab學習數位訊號處理」(CQ出版)
「理解電子迴路入門的入門(I) 兩極真空管、電晶體篇」(MICRONET)
「重新學習訊號數學」(CQ出版)
「從今天起可以使用的傅立葉變換」(講談社)
等等。
佐藤 伸一 (Satou Shinichi)
出生於日本福島縣伊達市。1990年修畢東京電機大學研究所電氣工學碩士課程。
於民間企業從事映像相關機器的設計，曾任生物工學相關的研究之私立大學醫學部助手，現為東京電機大學工學部資訊通訊工學科助手。
專門領域為數位訊號處理工學、教育工學。
製作：Verte
漫畫編輯：遠藤 嗣實
DTP：新井 聰史
譯者簡介：
林羿妏
2006年畢業於台灣大學國際企業學系，目前為兼職口筆譯者。譯有：《圖解燃料電池》、《世界第一簡單 統計學》、《世界第一簡單 微積分》（以上皆為世茂出版）。
章節試閱
專欄 擴張版輾轉相除法
輾轉相除法為導出2個自然數的最大公因數的演算法。它比質因數分解可以更有效率地計算。如果想在輾轉相除法中，找尋2個自然數 的最大公因數，則可利用以下步驟。
設 除以 ，餘數為 。
若 ，則最大公因數即為 ，計算即完成。
若 ，則 的組合置換為 和 ，然後再回到最初的步驟。
只要重覆 到 的步驟，餘數為0時，除數即為最大公因數。換句話說，得到餘數為0前的一個步驟中所得到的餘數即為最大公因數。
舉個實例，請以輾轉相除法求出1365和77的最大公因數。
1365＝17×77＋56 （← 依1365÷7...
輾轉相除法為導出2個自然數的最大公因數的演算法。它比質因數分解可以更有效率地計算。如果想在輾轉相除法中，找尋2個自然數 的最大公因數，則可利用以下步驟。
設 除以 ，餘數為 。
若 ，則最大公因數即為 ，計算即完成。
若 ，則 的組合置換為 和 ，然後再回到最初的步驟。
只要重覆 到 的步驟，餘數為0時，除數即為最大公因數。換句話說，得到餘數為0前的一個步驟中所得到的餘數即為最大公因數。
舉個實例，請以輾轉相除法求出1365和77的最大公因數。
1365＝17×77＋56 （← 依1365÷7...
顯示全部內容
作者序
目前以網際網路為中心且被網絡化的資訊社會中，除了活用網路上的公開資訊及電子郵件的往來外，也多虧網路商店及網路銀行的普及，使我們的生活變得更便利。
然而，在享受網路時代的恩惠之外，
「安心安全、資訊安全、保護個人資料……，以及密碼」
這類令人感到些許不安的詞彙，每天都在生活中不斷出現。這到底是怎麼一回事呢？為什麼呢？
利用網際網路處理許多資訊時，其中總包含讓別人知道就糟糕的事，不希望別人知道、想要保密的資訊。例如，信用卡號、銀行帳號、病歷、貸款金額、電子郵件地址等，為了不輕易洩露給他人知道，保護資...
然而，在享受網路時代的恩惠之外，
「安心安全、資訊安全、保護個人資料……，以及密碼」
這類令人感到些許不安的詞彙，每天都在生活中不斷出現。這到底是怎麼一回事呢？為什麼呢？
利用網際網路處理許多資訊時，其中總包含讓別人知道就糟糕的事，不希望別人知道、想要保密的資訊。例如，信用卡號、銀行帳號、病歷、貸款金額、電子郵件地址等，為了不輕易洩露給他人知道，保護資...
顯示全部內容
目錄
前言
序章1
第1章 密碼學的基礎15
1-1 密碼學相關用語16
密碼學的基本用語20
加密金鑰 和解密金鑰 的關係21
1-2 古典加密系統24
凱撒密碼24
替代密碼 25
多字母密碼26
置換密碼 27
1-3 密碼的安全性 28
替代密碼的金鑰數 31
多字母密碼的金鑰數 32
置換密碼的金鑰數 32
可解讀的條件 35
絕對安全的密碼 35
安全密碼 37
第2章 共通金鑰（對稱金鑰）加密系統45
2-1 二進位數和XOR運算46
2-2 共通金鑰密碼是什麼？57
共通金鑰密碼的特徵 62
2-3 串流密碼的構造 63
2-4 區塊密碼的...
序章1
第1章 密碼學的基礎15
1-1 密碼學相關用語16
密碼學的基本用語20
加密金鑰 和解密金鑰 的關係21
1-2 古典加密系統24
凱撒密碼24
替代密碼 25
多字母密碼26
置換密碼 27
1-3 密碼的安全性 28
替代密碼的金鑰數 31
多字母密碼的金鑰數 32
置換密碼的金鑰數 32
可解讀的條件 35
絕對安全的密碼 35
安全密碼 37
第2章 共通金鑰（對稱金鑰）加密系統45
2-1 二進位數和XOR運算46
2-2 共通金鑰密碼是什麼？57
共通金鑰密碼的特徵 62
2-3 串流密碼的構造 63
2-4 區塊密碼的...
顯示全部內容
|
