Модулярная арифметика

[Rustam2]

Помогите пожалуйста понять как нашли значение C
C=688^79mod3337=1570

[Sonic86]

Для начала topic183.html

А вообще $79$ раскладывать в 2-ичной системе счисления и затем выделяют множители отдельно, каждый считают по модулю и перемножают по модулю.
Т.е. если Вам надо подсчитать $3^{2^4} \mod 13$, Вы в цикле возводите в квадрат (4 раза будет) и после каждого возведения считаете остаток от деления на $13$.

[Rustam2]

$((((((688^2)^2)^2)^2)^2)^2)+(((688^2)^2)^2)+((688^2)^2)+688^2$
правильно?
А дальше как?

[Sonic86]

Rustam2 в сообщении #481146 писал(а):

$((((((688^2)^2)^2)^2)^2)^2)+(((688^2)^2)^2)+((688^2)^2)+688^2$
правильно?

Нет. Правильно $x^{a+b} = x^a \cdot x^b$, а Вы сделали по неверному правилу $x^{a+b} = x^a + x^b$.

Rustam2 в сообщении #481146 писал(а):

А дальше как?

А дальше, как я написал: считаете сначала степени двойки по модулю:

Sonic86 в сообщении #481137 писал(а):

Вы в цикле возводите в квадрат (4 раза будет) и после каждого возведения считаете остаток от деления на $13$.

Подробнее: пусть надо посчитать $x^{2^n} \mod m$ для $n>0$. Берем $x^{2^n} \mod m = (x^2)^{2^{n-1}} \mod m $$= (x^2 \mod m )^{2^{n-1}} \mod m = x_1^{2^{n-1}} \mod m$, где $x_1 = x^2 \mod m$. Таким способом мы сводим вычисление $x^{2^n} \mod m$ к вычислению $x_1^{2^{n-1}} \mod m$ - делаем так $n$ раз - степени исчезают. Остается перемножить несколько чисел по модулю. Делаем это тоже постепенно: перемножаем 2 числа, берем остаток, перемножаем еще 2 числа, берем опять остаток и т.п. до конца.
Кстати, если Вам это запрограммировать надо - можно сделать немного полегче, но, возможно, менее понятно.

[Rustam2]

Большое спасибо за информацию!
Это нужно мне для расчета контрольной работы, Асимметричная криптосистема RSA.

[Sonic86]

Rustam2 в сообщении #481177 писал(а):

Это нужно мне для расчета контрольной работы, Асимметричная криптосистема RSA.

Угу, я так и думал. Тогда можете подумать о расчете так:
$n=2k \Rightarrow x^n \mod m = (x^2 \mod m)^k \mod m$
$n=2k+1 \Rightarrow x^n \mod m = x \cdot (x^2 \mod m)^k \mod m$
Вам тогда даже массивы не понадобятся.