Модульное возведение в степень — как уменьшить огромный модуль?
Типичное уравнение для модульного возведения в степень: (a + b) MOD n = ((a MOD n) + (b MOD n)) MOD n. это здорово, если а и б очень большие.
однако меня попросили сделать это возведение в степень с очень большим n (2 ^ 31 -1), a и b не проблема.
Мне просто нужен способ уменьшить n.
Решение
«(a + b) MOD n = ((MOD n) + (b MOD n)) MOD n» не экспонента, это дополнение.
«(2 ^ 31 -1)» — это не «огромный n», это 31 бит, установленный в 1.
Поскольку эти базовые предположения просто неверны, а вопрос, по-видимому, является домашним заданием, трудно дать какой-либо более конкретный совет, возможно, не оказав ФП плохую услугу. То, что уже сказано, должно быть достаточно намека на то, что задание может быть решено. Или можно начать задание и опубликовать новый вопрос SO.
Другие решения
Других решений пока нет …