Хэш-функция MASH-2
Мы взяли хэш-функцию MASH-2 в курсе колледжа, и на экзамене мы сталкиваемся с вопросами, чтобы вычислить что-то вроде этого ((62500)^257)) мод (238194151), используя только научный калькулятор. теперь я знаю некоторые теории с a^b (mod n), но проблему, которую я представляю выше, даже трудно вычислить вручную. Я думаю, что это займет около 15 минут, чтобы решить эту проблему. Я хотел бы знать, есть ли более быстрый способ сделать это. или даже если есть какой-то способ сделать это в двоичном формате (преобразовать число в двоичное и затем выполнить некоторые манипуляции). Мне нужно сделать это вручную с помощью научного калькулятора.
1 ответ
В этом частном случае основной фактор разложения a = 62500 = 2² ⋅ 5⁶ очень просто
Вы можете использовать это для расчета (2²)²⁵⁷ а также (5⁶)²⁵⁷ сначала и посчитаем потом произведение.
Но проблема, которую я вижу, заключается в том, что для n = 238194151 мой научный калькулятор не умеет рассчитывать n² правильно. Если ваш калькулятор может сделать это, это не должно быть проблемой.
поскольку gcd(a, b) = 1 Вы также можете использовать ЭЛТ, но я не уверен, что вы можете найти основные факторы n = 13 ⋅ 59 ⋅ 310553 только с научным калькулятором. Если так, это сделает это намного легче. Вы просто рассчитываете a²⁵⁷ mod (13⋅59) а также a²⁵⁷ mod 310553 и положить результаты вместе с ЭЛТ.
Вы также можете использовать только Возведение в квадрат, возводя в квадрат, поэтому вам нужно только вычислить 8 квадратов.