math - 13* D = 1 mod 60 の場合、D = 37 はどのように?

Question

私は問題の例を解いています 。RSAアルゴリズム
では、2 つの素数 7 と 11 が与えられました。p=7q=11
de

まずn=p*q、 を意味する計算を行いましたn=77。

を計算するためにe=13、式、 whereなどを使用したとします。
dd*e = 1 mod fifi=(p-1)(q-1)fi=60

最終的な方程式は次のようになります。13*d = 1 mod fi

いくつかの解決済みの例によると d、37 と計算されますが、この結果はどのように得られますか?

どんな助けでも大歓迎です。

Answer 1

私はこれがあなたが探しているものだと思います

答えを検証するのは簡単ですが、最初にそれを見つけることは、もう少し手間がかかります。

検証：

13 * 37 = 481 
481 = 8 * 60 + 1

したがって、13 * 37 を 60 で割ると余りは 1 になります。

別の答え:

(37 + 60 k) の形式の任意の整数 (k は任意の整数) も解です。(97、-23 など)

解を見つけるには、次のように進めます
。

13 d = 1 + 60 k 
mod 13:
0 = 1 + 8k (mod 13) 
8k = -1 (mod 13) 
Add 13's until a multiple of 8 is found: 
8k = 12 or 25 or 38 or 51 or 64 .... aha a multiple of 8! 
k = 64 / 8 = 8 
Substitute k = 8 back into 13 d = 1 + 60 k 
13 d = 1 + 8 * 60 = 481 
481 /13 = 37 

それが答えです。

Answer 2

拡張ユークリッド アルゴリズムを使用して、整数 x と y を次のように計算します。

13*x+60*y=1

x は探している答えで、mod 60 です。