Как сделать Pow и мод гигантских чисел

Question

Я бы хотел добавить число к некоторой степени, затем умножить его на другое число и, наконец, изменить его.

Функция Python pow, которая принимает 3 параметра, не может быть использована в моем сценарии использования, поэтому я пытаюсь найти быструю альтернативу.

Примеры:

Я знаю, что могу сделать

9^10%2

в качестве * * +1010

pow(9, 10, 2)

но я не могу сделать

(8*9^10)%2

с той же функцией

Я уже пытался использовать (цифры только для справки, реальные цифры намного больше)

pow(9, 10)*8 % 2 # tooks too long
pow(9, 10, 2)*8  # returns wrong answer

Я бы хотел, чтобы мои числа вычислялись очень быстро, даже если они до 10 ^ 18. Мое требование времени - 2 с для 20 из этих чисел.

Ни одно из вышеперечисленных решений на самом деле не работало для меня, либо они были слишком медленными, либо не давали правильного ответа.

Answer 1

Ваше второе решение содержит неверное предположение, что верно следующее.Интуитивно, это не может быть правдой, потому что первое выражение может быть размером до c*(n-1), но второе должно быть строго меньше, чем n

((a^b)%n)*c == (c*a^b))%n

Правильная идентификация из Википедия :

ab mod n = [(a mod n)(b mod n)] mod n.

Мы можем обобщить это по индукции (доказательство оставлено в качестве упражнения для читателя):

ИтакВаше выражение должно быть:

(pow(9, 10, 2) * (8 % 2)) % 2
# OR
(pow(9, 10, 2) * 8) % 2