IDEA и умножение
Здравствуйте. Возникла следующая проблема.
В алгоритме IDEA есть умножение. Подскажите, пожалуйста, каким образом оно осуществляется? Т.е., например, мы 5 * 6 mod 7 = 2, а теперь как получить исходные 5 или 6, при наличие результата умножения и одного начального числа(ключа; 5 или 6)?
спасибо.
комментариев: 2199 документов: 140 редакций: 308
Ну если 5 * 6 mod 7 = 2
то 5 = 2 * 6 -1 mod 7 и 6 = 2 * 5 -1 mod 7
Т.е. надо найти т.н. обратные множители (multiplicative inverse) по модулю простого числа (т.е. в мультипликативной группе или поле, если простое чилсо).
Т.е. 6 -1 * 6 = 1 mod 7 и 5 -1 * 5 = 1 mod 7
Самый простейший вариант – расширенный алгоритм Евклида, но есть много оптимизаций.
Публикуя комментарий, пожалуйста, придерживайтесь темы / содержания документа.
Прежде, чем добавить вопрос, не забывайте воспользоваться поиском.