利用歐氏互除法算出以下三題(15點)

Question

拜託請詳解!!真的非常感謝。


(1)設C=38P+45(mod61), 求P=xC+y(mod61)中之x,y。
其中x,yε{0,1,2,.......,60}
(ε<--這好像是集合的符號，但我找不到那符號，就找相似的一"一)

(2)利用E-F定理，若28的2006次方= x(mod143), 求x之值。
惟xε{0,1,2,.......142}

(3)設C=P的23次方(mod143), 求P=C的x次方(mod143)成立時之xε{0,1,2.....119}。
其中P,C為正整數並與143互質。

Answer 1

(1)設C=38P+45(mod61), 求P=xC+y(mod61)中之x,y。
其中x,yε{0,1,2,.......,60}
----------------
C=38P+45(mod61)式中有一乘數38,因此先求出38對模61的反原數為53(可以用歐基里得輾轉相除法求出38*53=1(mod61))
C=38P+45(mod61)
C-45=38P(mod61)
兩邊同加61
C-45+61=38P+61(mod61)------38P+61=38P(mod61)
C+16=38P(mod61)
兩邊同乘38對61模的反原數53
(C+16)*53=(38*53)*P(mod61)
53C+16*53=1*P(mod61)------16*53=55(mod61)
P=53C+55(mod61)-------X=53,Y=55
--------------------
(2)利用E-F定理，若28的2006次方= x(mod143), 求x之值
----------------------
這一題出的很強人所難,運算很累人
先因數分解得143=11*13
則143的尤拉函數=(11-1)*(13-1)=120
任何與143互質的數的120次方均等於1(mod143)
2006=86((mod143)
所以28的2006次方=28的86次方(mod143)
86=2*43------就是這裡出問題必須計算28的平方mod143再算他的43次方
說真的我也用小算盤算的28的86次方=82(mod143)
其實尤拉函數的1/2----本題為60----也有相同結果----幾乎所有數都成立喔看你敢不敢用---嚇你的
2006=26(mod60)---26=2*13----較好算,但用筆算一樣累人---可以分解成2*(4*3+1)
2的26次方=82(mod143)
-----------------------------------------------------
3)設C=P的23次方(mod143), 求P=C的x次方(mod143)成立時之xε{0,1,2.....119}。
其中P,C為正整數並與143互質。
----------------
這是認證公鑰系統RSA的基本形
同上題143的尤拉函數=120
則任一數N的120次方=1(mod143)----N與143互質
求出兩數互為模120反原數-----T*U=1(mod120)----T*U=120*V+1(mod120)
則N的T*U次方=N的120*V次方再乘以N=1*N(mod143)
23*47=1(mod120)
所以
C=P的23次方(mod143)
P=C的x次方(mod143)成立------X=47

Answer 2

到下面的網址看看吧

▶▶http://*****

Answer 3

到下面的網址看看吧

▶▶http://*****

Answer 4

1.先利用輾轉相除法的進階運用，找出61×5-38×8=1，38×6-61×3=45。
從而38P≡C-45≡(61×5-38×8)C-(38×6-61×3)≡-38×8×C-38×6(mod61)，故得
P≡-8C-6≡53C+55(mod61)

2006-11-10 10:48:31 補充：
2.143=11×13。當(t,11)=1時，t^10≡1(mod 11)；當(t,13)=1時，t^12≡1(mod 13)。
解法(一)
故當(t,143)=1時，t^60≡1(mod143)。
28^2006≡28^26≡69^13≡69×42^6≡69×48^3≡(69×48)×(48×48)≡23×16≡82(mod 143)

2006-11-10 10:48:59 補充：
解法(二)
而28^2006≡6^6≡3^3≡5(mod 11)；
28^2006≡2^2≡4(mod 13)
因為13×6≡2×6≡1(mod 11)；
11×6≡(-2)×6≡-12≡1(mod 13)，
故28^2006≡13×6×5+11×6×4≡82(mod 143)。

2006-11-10 10:54:12 補充：
3.由前述，當(t,143)=1時，t^60≡1(mod 143)。
再由輾轉相除法進階運用得出60×5-23×13=1，進而23×47-60×18=1
由C≡P^23(mod 143)得到
C^47≡P^(23×47)≡P(mod 143)

Answer 5

通常歐氏是指歐幾里得，好像很少把歐拉大師稱作歐氏的ㄝ

2006-11-10 01:52:47 補充：
E-F定理想必是Euler-Fermat定理囉！？
好像沒有人這樣簡稱的.....
感覺像是問作業的....
可是這作業又太深了點.....
第2題答案82，
第3題答案47，
第一題有點怪怪的，正在想....