作者spits (遥远的距离)
看板Grad-ProbAsk
标题Re: [问题] 96中山资工离散
时间Wed Mar 25 22:30:00 2009
※ 引述《MysterySW (饭团丸)》之铭言：
: 第8题
: p=61, q=127, n=pq=7747
: 求最小整数d使得
: (1237^17)^d mod n = 1234
: 抱歉我数论很弱@@
: 这题不知道该怎麽做
: 感谢大家
题目你打错了 是 (1234^17)^d mod n = 1234
1234^17d == 1234 (mod n) // "=="应该是要写成三横 打不出来
1234^(17d-1) == 1 (mod n)
1234^(17d-1) == 1 (mod p)
1234^(17d-1) == 1 (mod q)
根据费马小定理( gcd(m,p)=1 则 m^(p-1) == 1 (mod p) )
(1234 跟 61, 127 皆互质)
1234^60 == 1 (mod p) => 17d-1 = a*60
1234^126 == 1 (mod q) => 17d-1 = b*126
即 17d-1 = c*60*126 =c*7560 => 17d == 1 mod 7560 (d为最小正整数)
7560 = 17*444 + 12
17 = 12* 1 + 5
12 = 5*2 + 2
5 = 2*2 + 1
1 = 5 - 2*2
= 5 - 2*(12 - 5*2) = 5*5 -2*12
= 5*(17 -12) - 2*12 = 5*17 - 7*12
= 5*17 - 7*(7560 - 17*444) = -7*7560 + 3113*17
所以d=3113
应该没算错吧 很怕计算错误
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.170.243.188
1F：推 mathmanliu:17x≡1 (mod 7560) => x≡3113 (mod 7560)没错! 03/25 23:08
2F：推 MysterySW:喔喔 非常感谢^^ 03/26 00:42
3F：推 greedbo:可以请问一下为什麽7650可以消去吗? 书上写7650=(三杠) 03/26 04:11
4F：→ greedbo:0,不懂三杠等号的实质意思? 03/26 04:11
5F：→ s987692:就是余数的意思 (mod n ) ~之类 03/26 04:18
6F：→ loking:三横应该是等价的意思 03/26 18:32
7F：→ ssccg:≡ (mod n)代表只有在(mod n) (代数里面叫Zn)下是等价 03/26 23:51
8F：→ ssccg:这叫同余关系 03/26 23:51
9F：推 ieaan:楼上真令人感动!你会有好报的! 03/27 07:13
10F：推 greedbo:感谢你,原来答案不太对 我一直对自己的解法看好久 03/27 16:05
11F：→ greedbo:两个问题想请教,1.这题是哪里有用到费马小定理? 最後的d是 03/27 17:44
12F：→ greedbo:要在mod 後才是答案吧? 03/27 17:45