Как определить d в этом примере алгоритма RSA?

Question

Как часть моего курса колледжа, мне задали вопрос, который нужно решить. Речь идет об алгоритме RSA.

я был дан р = 29, Q = 17 и е = 5.

я должен определить, д.

Так что я знаю, п = 29 х 17 => 493 и фи (п) = 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