作者preed (Freedom)
看板Math
标题[数论]国安局两题考题
时间Tue May 12 16:27:58 2020
https://imgur.com/a/wezsZ3B
实在太久没摸数论了 大一又被当掉重修
在此请教版上网友 谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 218.173.50.88 (台湾)
※ 文章网址: https://webptt.com/cn.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