Числа и ввод · 35 из 43
Обратное по модулю
Лабораторная по дискретной математике — та, после которой на лекции про RSA перестают кивать вслепую. Борис Аркадьевич: «Обратное к a по модулю m — такое x, что a·x даёт остаток 1 при делении на m. Ищут его расширенным алгоритмом Евклида: тот же Евклид, только по дороге ведём ещё и коэффициенты». Встроенный pow(a, -1, m) на этой лабораторной не принимается — он делает ровно то, что надо написать.
Что сделать
Найдите обратное к a по модулю m расширенным алгоритмом Евклида; если обратного нет, так и скажите.
Что приходит
a— число, к которому ищем обратное; бывает отрицательным и большеmm— модуль, натуральное число
Что вернуть
Число x от 0 до m − 1, при котором a · x даёт остаток 1 при делении на m; если у a и m есть общий делитель больше 1 — None.
Допишите функцию obratnyy в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
Ограничение
Без
pow— и своё имя так назвать нельзя
Обходные пути — тоже нарушение: eval, exec, getattr, имена с двойным подчёркиванием, импорт os, subprocess и им подобных.
a = 3, m = 11: 3 · 4 = 12 = 11 + 1, остаток 1 — обратное равно 4.
obratnyy(3, 11)
4
Обратное существует, только если наибольший общий делитель a и m равен 1. Тогда оно одно среди чисел от 0 до m − 1.
Расширенный алгоритм Евклида ведёт пары: остаток и коэффициент при a, так что всегда остаток = коэффициент · a (по модулю m). Начало — пары (a mod m, 1) и (m, 0). Шаг: q — целая часть от деления старого остатка на новый, и обе величины меняются одинаково: «следующее = старое − q · текущее». Когда новый остаток стал нулём, старый — это НОД.
При m = 1 любое число даёт остаток 0, и ответ — 0.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.