Chapter 2 密碼基礎數學I:模數算數、同餘 與矩陣.

Slides:



Advertisements
Similar presentations
2014 年浙江省数量资料 华图网校 刘有珍 数字推理 年份题量数字规律 三级等差 2. 和递推 3. 幂次修正 4. 倍数递推 5. 倍数递推 6. 特殊差级 7. 倍数递推 8. 倍数递推 9. 积递推 10. 分数数列
Advertisements

常用食物含水量表 食物单位原料重 g 含水量 ml 大米饭一碗 (170g) 大米粥一碗 (500g) 面条一碗 (170g) ( 汤另计 ) 蒸蛋糕一碗 (170g) 5025 藕粉 牛奶
加強輔導課程家長簡介會 時間: 9 月 30 日(二) 晚上 : 6:45 至 8 : 00 地點:禮堂.
题目:高血压病人的护理 系 别 :医学系 年级专业 : 06 护理 学生姓名 :陈恩琪 指导教师 : 林力敏老师 实习医院 :顺德中西医结合医院.
龙泉护嗓5班 优秀作业展.
九十五年國文科命題知能 研習分享.
2011年会计初级职称全国统考 初级会计实务 教案 主讲:高峰 2010年12月.
人力资源管理资格考证(四级) 总体情况说明.
2013届高考复习方案(第一轮) 专题课件.
人生格言: 天道酬勤 学院:自动化与电气工程学院 班级: 自师1201 姓名:刘 威.
专题二 文学类文本·小说阅读(选考) ——把握人事,洞察百态 补上一课 如何读懂小说 第1讲 情节 第2讲 人物 第3讲 环境 
第一部分 微专题强化练.
欧洲西部 要点·疑点·考点 欧洲西部 1. 自然环境 位置:欧洲西半部,北临北冰洋,西临大西洋,南临地中海
服务热线: 菏泽教师招聘考试统考Q群: 菏泽教师统考教育基础模拟题解析.
英 德 美 法 标志 1689年 《权利法案》 1871年 《德意志帝国宪法》 1787年宪法 1875年法兰西第三共和国宪法 政体 君主立宪制 民主共和制 行政权 内阁、首相 皇帝、宰相 总统 立法权 议会 国会 权力中心 皇帝 特点 君主虚位 议会至上 军事封建 皇帝权重 总统共和制 议会共和制.
工職數學 第三冊 第二章 不等式與線性規劃 ‧2-1 一元二次不等式 ‧2-2 絕對值不等式 ‧2-3 二元一次不等式的圖形
2011年广西高考政治质量分析 广西师范大学附属外国语学校 蒋 楠.
第一单元 生活与消费 目 录 课时1 神奇的货币  课时2 多变的价格 课时3 多彩的消费.
用问题激发学生的思维 \.
知识回顾 1、通过仔细观察酒精灯的火焰,你可以发现火焰可以分为 、 、 。 外焰 内焰 焰心 外焰 2、温度最高的是 。
2016届高三期初调研 分析 徐国民
限时综合强化训练 限时综合强化训练.
歌仔戲 與 歌舞伎 4a 張淇惠 4a11b025 許巧嬑 4a 倪曼凌 4a1c0004 楊長梵
洋流(大规模的海水运动).
连乘、乘加、乘减和把整数乘法运算定律推广到小数
岳阳市教学竞赛课件 勾股定理 授课者 赵真金.
会计学 第九章 财务会计报告.
第二讲 环境污染及其防治、环境管理.
请同学们思考下列问题:.
[聚會時, 請將傳呼機和手提電話關掉, 多謝合作]
1 实验目的 观察单缝夫琅和费衍射现象,加深对夫琅和费衍射理论的理解。
第一课 神奇的货币 第二框 信用工具和外汇 1-2 信用工具和外汇.
命题与四种命题 高二数学 选修2-1 第一章 常用逻辑用语.
面向海洋的开放地区——珠江三角洲 山东省高青县实验中学:郑宝田.
B F C D G E B E A 下图是沿20°经线所作的地形剖面示意图
第七章 财务报告 财务报告 第一节 财务报告概述 一、财务报告及其目标: 1、概念:财务报告是指企业对外提供的反映企业某一特定日期
[聚會時,請將傳呼機和手提電話關掉,多謝合作]
发展心理学 王 荣 山.
組員:蔡典龍4970E027 蕭積遠4970E026 王建智4970E050 李雅俐4970E025 賴品言4970E054
第1节 光的干涉 (第2课时).
CHAPTER 5 現值法 工程經濟學 Chapter 5 現值法. CHAPTER 5 現值法 工程經濟學 Chapter 5 現值法.
群組未知 水蜜桃每4個裝一盒,爸爸買了5盒,一共買了幾個水蜜桃? 爸爸想把20個水蜜桃平分給他的5個朋友,每個朋友可以得到幾個水蜜桃?
勾股定理 说课人:钱丹.
苏教版小学数学六年级(下册) 认识正比例的量 执教者:朱勤.
第 十一 课  寻觅社会的真谛.
[聚會時,請將傳呼機和手提電話關掉,多謝合作]
证券投资基金 投资121 06号余煜欢 09号陈秋婷 33号陈柔韵 08号潘晓峰 10号曾杰 34号谭锐权.
文化生活第三单元 中华文化和民族精神.
政治第二轮专题复习专题七 辩 证 法.
狂賀!妝品系同學美容乙級通過 妝品系三甲 學號 姓名 AB 陳柔諺 AB 陳思妤 AB 張蔡婷安
第七章 财务报告 主讲老师:王琼 上周知识回顾.
第 二 章 逻 辑 代 数 基 础.
人教版数学四年级(下) 乘法分配律 单击页面即可演示.
耆康會長者中央議會 <<長者與社會參與>>計劃培訓
第26讲 解直角三角形的应用 考点知识精讲 中考典例精析 举一反三 考点训练.
《2015考试说明》新增考点:“江苏省地级市名称”简析
乘法公式 (1) 乘法分配律 (2) 和的平方公式 (3) 差的平方公式 (4) 平方差公式.
变 阻 器 常州市北郊初级中学 陆 俊.
经济法基础习题课 主讲:赵钢.
第五章 相交线与平行线 三线八角.
Welcome 实验:筷子提米.
第一部分 数字电路 第4章 组合逻辑电路 主讲教师:喻红.
线段 射线 直线.
第一章 集合论 集合是最基本的数学概念,没有定义 集合是所有数学的基础 两种集合论 朴素集合论:直观描述集合的概念,有悖论
分配律 ~ 觀念 15 × 15 × + 15 × 乘法公式 蘇德宙 老師 台灣數位學習科技股份有限公司
坚持,努力,机会留给有准备的人 第一章 四大金融资产总结 主讲老师:陈嫣.
美丽的旋转.
序偶及直角坐標系統.
平面的基本性质 江苏省泰州中学 数学组 姜莹. 平面的基本性质 江苏省泰州中学 数学组 姜莹.
Presentation transcript:

Chapter 2 密碼基礎數學I:模數算數、同餘 與矩陣

學習目標 回顧整數算術,特別是整除性,並利用歐幾里德演算法來找出最大公因數。 學習利用歐幾里德延伸演算法來解線性 Diophantine 方程式、線性同餘方程式,以及找出乘法反元素。 著重在模數算術和模運算子的學習,因為它們在密碼學中被大量地使用。

學習目標 (續) 強調並回顧矩陣和餘數矩陣的運算,因為它們在密碼學中的應用非常廣泛。 學習利用餘數矩陣來解同餘方程組。

1.2 整數算數 在整數算術 (integer arithmetic) 中,我們使用一個集合和一些運算。或許你對這個集合和運算可能已經非常熟悉,但為了建立模數算術的背景知識,在此我們還是對整數算術做一個回顧。

1.2 整數算數 (續) 在本節討論的主題: 整數集合 二元運算 整數除法 整除性 線性Diophantine方程式

2.1.1 整數集合 整數集合,標記為 Z,是從負無窮大到正無窮大的所有整數形成的集合(圖 2.1) 圖 2.1 整數集合

2.1.2 二元運算 在密碼學中,我們對於三種作用於整數集合的二元運算 (binary operation) 感到興趣。二元運算可接受兩個輸入值,然後產生一個輸出值。

圖 2.2 三種作用在整數集合上的二元運算

範例2.1 下列的例子顯示出三種二元運算作用於兩個整數後所產生的結果。由於每個輸入值均可為正值或負值,因此對於每一種運算我們討論四種情形。

2.1.3 整數除法 在整數算術中,如果我們使用 n 來除 a,可以得到 q 和 r。這四個整數之間的關係可以表示為: 2.1.3 整數除法 在整數算術中,如果我們使用 n 來除 a,可以得到 q 和 r。這四個整數之間的關係可以表示為: a = q × n + r

範例2.2 假設 a = 255 且 n = 11。利用過去所學的除法算術,我們可以得到 q = 23 且 r = 2。(圖2.3)

圖 2.4 整數的除法演算法

範例2.3 當我們使用電腦或計算機計算除法時,若 a 為負數,則 r 和 q 也為負數。我們要如何根據限制讓 r 變為正數呢?很簡單,我們只要將 q 值減 1,並且將 r 值加 n ,就可以讓 r 變成正數。

圖 2.5 除法演算法的圖形

2.1.4 整除性 在一個除法關係中,如果 a 不為 0 且令 r = 0,則可以得到: a = q × n 若餘數為零,則 若餘數為零,則

範例2.4 整數 4 可以整除 32,因為 32 = 8 × 4。我們將此關係表示成 整數 4 可以整除 32,因為 32 = 8 × 4。我們將此關係表示成 整除 8 無法整除 42,因為 42 = 5 × 8 + 2,此方程式的餘數為2。我們將此關係表示成

範例2.5 我們可以得到 13|78, 7|98, -6|24, 4|44 以及 11|(-33)。 我們可以得到 以及 。

2.1.4 整除性 (續) 性質1:若 a|1,則 a = ±1。 性質2:若 a|b 且 b|a,則 a = ±b。 性質3:若 a|b 且 b|c,則 a|c。 性質4:若 a|b 且 a|c,則a|(m × b + n × c), 其中 m 和 n 為任意整數。

範例2.6 因為 3|15 且 15|45,根據性質3, 3|45。 因為 3|15 且 3|9,根據性質4, 3|(15 × 2 + 9 × 4 ) ,亦即 3|66。

2.1.4 整除性 (續) 事實1:整數 1 只有一個因數,就是它自己 注意 事實1:整數 1 只有一個因數,就是它自己 事實2:任何整數至少有2個因數,1 和 它自己 (但也可能有更多其他因數)

圖 2.6 兩個整數的公因數

2.1.4 整除性 (續) 兩個整數的最大公因數為所有能整除這兩個整數之最大整數。 事實 1: gcd (a, 0) = a。 注意 最大公因數 兩個整數的最大公因數為所有能整除這兩個整數之最大整數。 注意 歐幾里德演算法 事實 1: gcd (a, 0) = a。 事實 2: gcd (a, b) = gcd (b, r), 其中 r 是 a 除以 b 的餘數。

圖 2.7 歐幾里德演算法

2.1.4 整除性 (續) 注意 當 gcd (a, b) = 1 時,我們說 a 和 b 為互質。

範例2.7 試求 2740 和 1760 的最大公因數。 解法:我們得到 gcd (2740, 1760) = 20。

範例2.8 試求 25 和 60 的最大公因數。 解法:我們得到 gcd (25, 65) = 5。

歐幾里德延伸演算法 給定兩個整數 a 和 b,我們時常需要去找出另外兩個整數 s 和 t,使得 歐幾里德延伸演算法可以同時計算出 gcd (a, b) 以及 s 和 t 的值。

圖 2.8 歐幾里德延伸演算法

圖 2.8 歐幾里德延伸演算法 (續)

範例2.9 給定 a = 161 和 b = 28,求出 gcd (a, b) 以及 s 和 t 的值。 解法:我們得到 gcd (161, 28) = 7,s = −1 和 t = 6。

範例2.10 給定 a = 17和 b = 0,求出 gcd (a, b) 以及 s 和 t 的值。 解法:我們得到 gcd (17, 0) = 17,s = 1 和 t = 0。

範例2.11 給定 a = 0 和 b = 45,求出 gcd (a, b) 以及 s 和 t 的值。 解法:我們得到 gcd (0, 45) = 45,s = 0 和 t = 1。

2.1.5 線性Diophantine方程式 雙變數之線性Diophantine方程式是一種形態為 ax + by = c 的方程式。 注意 雙變數之線性Diophantine方程式是一種形態為 ax + by = c 的方程式。 注意 特解: x0 = (c/d)s 和 y0 = (c/d)t

2.1.5 線性Diophantine方程式(續) 通解: 注意 通解: x = x0 + k (b/d) 和 y = y0 − k(a/d) 其中 k 為整數

範例2.12 求出方程式 21x + 14y = 35 的特解和通解。 解法:

範例2.13 舉例來說,我們要把100美元的支票兌換成一些由20美元和5美元的鈔票。利用求解線性Diophantine方程式 20x + 5y = 10,可以找出許多不同的兌換方式。因為 d = gcd (20, 5) = 5,而且 5 | 100,此方程式有無限多解,但本例中,這些解中只有少數是合理的 ( x 值和 y 值必須同時為非負整數解)。這條方程式之非負整數的通解為 (0, 20), (1, 16), (2, 12), (3, 8), (4, 4), (5, 0)

2.2 模數算數 前一節所討論的除法關係 (a = q × n + r) 有兩個輸入值 (a 和 n) 以及兩個輸出值 (q 和 r)。在模數算術中,我們只對其中一個輸出值餘數 r 感興趣。

2.2 模數算數 (續) 本節所探討的主題包含: 模運算子 餘數集合:Zn 同餘 Zn下的運算 反元素 加法表和乘法表 加法和乘法的不同集合 另外兩種集合

2.2.1 模運算子 模運算子 (modulo operator),符號為 mod。第二個輸入值 (n) 稱為模數 (modulus) ,輸出值 r 則被稱為餘數 (residue)。

圖 2.9 除法關係與模運算子

範例2.14 求解下列運算式: a. 27 mod 5 b. 36 mod 12 c. −18 mod 14 d. −7 mod 10 解法 27 除以 5 可得 r = 2。 36 除以 12 可得 r = 0 。 -18 除以 14 可得 r = −4。−4 加上模數之後, r = 10 。 -7 除以 10 可得 r = −7。−7加上模數之後,r = 3 。

2.2.2 餘數集合:Zn 模數運算會產生一個集合,此集合在模數算數中被稱為模 n 之最小餘數集合 (set of least residues modulo n),或記為 Zn。 圖 2.10 一些 Zn 的集合

2.2.3 同餘 我們使用同餘運算子 ( ≡ )來表示兩個整數是同餘的。舉例來說,我們寫出:

圖 2.11 同餘的概念

剩餘類 剩餘類 (Residue class) [a] 或 [a]n,是一個在模 n 之下所有餘數為 a 的整數集合。

圖 2.12 利用圖形來比較 Z 和 Zn

範例2.15 日常生活都會用到模數算術,例如使用時鐘來測量時間。時鐘系統是模數為12的算術。然而在時鐘系統中,我們使用數字12來代替0,所以時鐘系統從0 (或12) 開始前進,直到11為止。因為一天是24小時,因此會沿著時鐘的圓形循環兩次,並且把第一次的循環記為A.M.,然後把第二次的循環記為P.M.。

2.2.4 Zn下的運算 我們之前討論集合 Z 中的三個運算 (加法、減法和乘法) 也可以在集合 Zn 中定義。這些運算的結果可能需要使用模運算子將其對應到 Zn中。

圖2.13 Zn中的二元運算

範例2.16 計算下列各運算式 (輸入值為 Zn 中的元素): a. 在 Z15 中計算 14 加 7。 b. 在 Z13 中計算 7 減 11。 c. 在 Z20 中計算 7 乘 11。 解法

範例2.17 計算下列各運算式 (輸入值為 Z或 Zn 中的元素): a. 在 Z14 中計算 17 加 27。 b. 在 Z13 中計算 12 減 43。 c. 在 Z19 中計算 123 乘 -10。 解法

2.2.4 Zn下的運算 (續) 性質

圖 2.14 模運算子的性質

範例2.18 下列運算式顯示出如何應用上述性質: a. (1,723,345 + 2,124,945) mod 11 = (8 + 9) mod 11 = 6 b. (1,723,345 − 2,124,945) mod 16 = (8 − 9) mod 11 = 10 c. (1,723,345 × 2,124,945) mod 16 = (8 × 9) mod 11 = 6

範例2.19 在算術中,我們經常需要計算10 的冪次方除以某個整數所得之餘數。

範例2.20 我們在過去被教導過,算術中一個整數除以3的餘數,和其每一位數之總和除以3的餘數是相同的。我們可以使用模運算子的性質來證明這個宣稱。我們先將整數改寫成每一個位數乘以10的冪次方之總和。