Как вычислить (a ^ b) mod c, где b большое, а c не простое?

#math

#математика

Вопрос:

a ^ b mod c Я знаю, как решить, является ли c простым, каким будет подход, если c не является простым. Любой математический подход.

1. речь идет о символическом решении математической задачи или это запрос программы на C / C , которая численно вычисляет ответ?

2. Программа на C / C — есть ли какой-либо подход?

3. Измените категорию на C , и вы получите много посетителей C вместо людей, которые с нетерпением ждут математической задачи, а затем раздражаются и голосуют за ваш вопрос: D

4. Или, скорее, математика И c

5. Я голосую за то, чтобы закрыть этот вопрос как не относящийся к теме, потому что он касается математики

Ответ №1:

Предполагая, что факторизация c известна, вы можете вычислить итоговое значение Эйлера phi(c) и знать, что с этим числом, но только если a и c не имеют общих делителей,

 a^b == a^( b mod phi(c) )  mod c

Таким образом, если b , как в вашем исходном редактировании, какое-то очень-очень большое число Фибоначчи, вы должны вычислить это число с помощью выбранного вами алгоритма со всеми арифметическими операциями mod phi(c) . В то же время это гарантирует, что показатель степени остается в том же числовом формате, который используется для c , и что сложность возведения в степень уменьшается.

1. Придирка: ваша формула может быть недействительной, если a и c не являются относительно простыми.

2. @MarkDickinson: Вы правы, и WP четко заявляет об этом. Теперь вставлено.