RSA暗号の計算についての質問ですp=5q=11e=23とするとき①dはいくつか？②M=3に対する暗号文Cは？途中の計算のやり... - Yahoo!知恵袋

※登場する文字は、RSA暗号の説明で一般的に使われるものであるため、 ※意味の記述は略します。 (1) n=pq=5*11=55, φ(n)=φ(p)*φ(q)=(p-1)*(q-1)=40 ed=23d≡1 (mod φ(n)=40)のとき 23d*7≡7 (mod 40) ⇔ 161d≡d≡7 (mod 40)より d=7 ＜別解＞ ユークリッドの互助法を用いて 40=23*1+17 23=17*1+6 17=6*2+5 6=5*1+1 これを逆にたどると 1=6-5 =6-(17-6*2)=6*3-17 =(23-17)*3-17=23*3-17*4 =23*3-(40-23)*4 =23*7-40*4 このことから 23*7≡1 (mod 40) よって、d=7 (2) C=M^e=3^23 (mod n=55)であり、 3^5=243≡23 (mod 55) 3^10=(3^5)