[數論] 國安局兩題考題

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