2011-gre-cs-practice-book.pdf/Q69

Вопрос: Q69-08c765

Предположим, что в RSA-шифровании открытым ключом шифрования является пара , а закрытым ключом дешифрования - пара , где - положительные целые числа. Каково значение ?

Ответы

Правильный ответ: 27
13
37
39
54

Объяснение

Исходники — вопрос 69 на 48 странице книги «2011-gre-cs-practice-book.pdf»

Чтобы найти значение в RSA-шифровании, где открытый ключ и выполним следующие действия:

Найдём простые множители для :
Вычислим общую функцию Эйлера:
Выбираем значение (в нашем случае )
Находим , которое является обратным к по модулю (то есть остаток от деления и должен быть равен 1)

Найти его можно с помощью расширенного алгоритма Евклида по формуле: , где - меньший из результатов расширенного алгоритма Евклида. В нашем случае . А следовательно