作者preed (Freedom)
看板Math
標題[數論]國安局兩題考題
時間Tue May 12 16:27:58 2020
https://imgur.com/a/wezsZ3B
實在太久沒摸數論了 大一又被當掉重修
在此請教版上網友 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.173.50.88 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1589272080.A.ABE.html
※ 編輯: preed (218.173.50.88 臺灣), 05/12/2020 16:29:01
1F：推 chemmachine : denote"="為mod等價。二之一即證a^561=a mod561 05/12 17:38
2F：→ chemmachine : 即證11*3*17 |a^561-a 分別證11、3、17|a^561-a 05/12 17:40
3F：→ chemmachine : a^10=1 mod11，a^11=a mod11 a^2=1 mod3 a^3=a mod3 05/12 17:41
4F：→ chemmachine : a^16=1 mod17 a^17=a mod17 分別代入可證明二之一 05/12 17:42
6F：→ chemmachine : 他有if and only if兩個方向 05/12 17:44
9F：→ chemmachine : 從後到前都成立，故解決三之一，三之二 這要搞清楚 05/12 17:54
10F：→ chemmachine : 甚麼是乘法函數(數論) 05/12 17:56
11F：推 chemmachine : 國安局考英文、數論、線代、機統很簡單啊... 05/12 18:01
12F：→ chemmachine : 我自己看到題目二之二不會寫，其他都滿快的。 05/12 18:02
13F：推 chemmachine : 我的意思是二之二也許可以放棄，其他要把握，個人意 05/12 18:10
14F：→ chemmachine : 見 05/12 18:11
15F：推 TimcApple : 2-2 從 2-1 的證明就能看出端倪了吧 05/12 18:15
16F：→ TimcApple : 然後用個反證法 假設不是 n-1 除以 p-1 有餘數 r, 05/12 18:19
17F：→ TimcApple : 則 in mod p, a^r = 1 for all a prime to p 由於 05/12 18:19
18F：→ TimcApple : a^r = 1 最多只有 gcd(r, p-1) 個答案 矛盾 05/12 18:20
20F：→ coolbetter33: 上面是參考koshy跟burton的書 05/12 18:29
21F：推 chemmachine : 錄取兩個 ……還是都不要放棄好了。。 05/12 19:12
22F：→ saltlake : 其他科目看得出用途，但是國安局考數論的用處是? 05/12 20:42
23F：→ saltlake : 解密碼有關? 05/12 20:42
24F：推 chemmachine : rsa加密方法有代數+數論，這個大學數學會教。偽質 05/12 21:00
25F：→ chemmachine : 數也是。 05/12 21:00
26F：→ chemmachine : 這算很基礎的，可能至少知道原理近去 05/12 21:00
27F：→ chemmachine : 知道怎麼處理專案。 05/12 21:00
28F：→ chemmachine : 我知道中科院的航太本科還是找本科有比較靠譜。中 05/12 21:00
29F：→ chemmachine : 科院的飛彈系統找航太還是比啥環工還是工工好吧， 05/12 21:00
30F：→ chemmachine : 反之亦然。 05/12 21:00
31F：→ saltlake : 數論應該只有數學系在開吧? 難道資訊系也開嗎? 05/12 22:28
32F：推 doa2 : 我是有修過電機系開的密碼學，都在教數論 05/12 22:31
33F：推 chemmachine : 數學系有開，其他我不清楚。 05/12 22:33
34F：推 chemmachine : 我的三之二寫錯了，逆推不回去。 05/12 22:56
35F：→ chemmachine : 以樓上推文課本為準。 05/12 22:56
36F：推 chemmachine : 基本上我的課本3之2的hint是寫mobius inversion 和d 05/12 23:00
37F：→ chemmachine : 的因數拆解。 05/12 23:00
38F：推 TimcApple : 密碼學很多基本概念是數論來的 05/12 23:04
39F：→ TimcApple : 密碼之所以能成為密碼 就是因為有某些運算 05/12 23:04
40F：→ TimcApple : 直接算很容易 但反過來算(或逆向破解)難到爆 05/12 23:05
41F：→ TimcApple : 這些運算通常都只是單純數的性質 例如大質數相乘 05/12 23:05
42F：→ TimcApple : 除了RSA以外 也有人用例如橢圓曲線來加密 05/12 23:06
43F：推 chemmachine : 3-2以前會做，現在要看過才想起來@ 05/12 23:07
44F：→ TimcApple : 這東西只是 y^2=ax^3+... 但整數解難算的要死 05/12 23:07