このRSAアルゴリズムの例でdを決定する方法は？

Question

私の大学のコースの一環として、解決するための質問がありました。これはRSAアルゴリズムのトピックです。

Iが与えられているP = 29、Q = 17、E = Iは、Dを決定する必要が5

。

は、だから私は知っているのn = 29×17 => 493とphi（N）= 448

は、だから私は、私はその後、ユークリッドのアルゴリズムに従っ

5 * d mod 448 = 1 

を知っているポイントに取り掛かります

448 = 89(5) + 3 

ここで3は残り（商）です。前の例では、商が1になったところでやったところで、dが何であったかを簡単に解くことができました。しかし、私は残りの部分が3であるこの例のためにそれを行う方法がわかりません。

誰でもこれを行う方法を知っていますか？ヘルプは非常に高く評価されます。

Answer 1

あなたは拡張ユークリッドアルゴリズムを完了していません。 （https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm）

あなたは(r_i, s_i, t_i)ている必要があります

(448,1,0) => 1*448 + 0*5 = 448 
(5, 0, 1) => 0*448 + 1*5 = 5 
(3, 1, -89) => 1*448 - 89*5 = 3 
(2, -1, 90) => -1*448 + 90*5 = 2 
(1, 2, -179) => 2*448 - 179*5 = 1 

は、あなたがそう2*448 - 179*5 = 1、-179 * 5 = 1 mod 448、または269*5 = 1 mod 448、そしてあなたの答えは事をだd = 269