Разложение на множители при шифровании

[Mikle1990]

$C=3^{53}\pmod{77}$ - раньше я думал, что это возможно сделать только с помощью инженерного калькулятора, а потом понял, что можно ведь так:
$3^{17}\pmod{77}=75$
$C=75\cdot75\cdot75\cdot9\pmod{77}=3796875\pmod{77}=5$

Всё верно?

[nnosipov]

Mikle1990 в сообщении #631245 писал(а):

$3^{17}\pmod{77}=75$

А это откуда взялось?

[Mikle1990]

nnosipov, я разложил
$3^{57}=3^{17}\cdot3^{17}\cdot3^{17}\cdot3^{2}$

[nnosipov]

Прелестно, а как получили сравнение $3^{17} \equiv 75 \pmod{77}$? Я именно об этом и спросил.

[Mikle1990]

У меня дана схема на которой $C=M^{e}\pmod{n}$
$M=3$, $n=77$ - по условию.
$e=53$ - вычислено (см. на этом форуме мои темы...)

Вы мне главное скажите, правильно ли я раскладываю на множители?

[nnosipov]

Mikle1990 в сообщении #631260 писал(а):

Вы мне главное скажите

Вот-вот, уже гораздо лучше. Не следует забывать о приличиях. Теперь по существу: из Вашего первого сообщения никак не следует, что значение $3^{17} \bmod{77}$ известно, и его не нужно вычислять (читать Ваши предыдущие сообщения никто, как Вы понимаете, не обязан). Если Вы хотите получить адекватную помощь, точно формулируйте свою проблему: это дано, это нужно получить, это мои попытки сделать это. Я, к примеру, подумал, что Вас затрудняет именно вычисление большой степени тройки по модулю. Для этого существует хорошо известный алгоритм, в свете которого Ваши действия выглядят довольно странно и нуждаются в пояснениях. Вот я и попросил пояснить.

[Shadow]

Мне кажется, что компютер Mikle1990 $3^{17}$ может вычислить без проблем, а $3^{53}$ уже нет. И поэтому придумал такую хитрость.

[Mikle1990]

nnosipov, давайте так
$C=3^{53}\pmod{77}$
$C$ - это зашифрованное сообщение, которое я должен получить.

Я могу взять калькулятор и посчитать $3^{53}=19383245667680019896796723$
, а далее подставить в исходную формулу и получить $C$.

Вопрос: Как мне избежать вычисления таких больших значений?

Ведь за партой у меня нет компьютера, а лишь калькулятор, который не справится с данным вычислением.

Поэтому я подумал, что я могу разложить $3^{57}=3^{17}\cdot3^{17}\cdot3^{17}\cdot3^{2}$ и получить $C$ таким образом:$C=3^{17}\pmod{77}\cdot3^{17}\pmod{77}\cdot3^{17}\pmod{77}\cdot9\pmod{77}=75\cdot75\cdot75\cdot9\pmod{77}=3796875\pmod{77}=5$
Правильно ли я сделал?

[nnosipov]

Mikle1990 в сообщении #631279 писал(а):

Вопрос: Как мне избежать вычисления таких больших значений?

А здесь есть стандартный алгоритм. Даже если Вам нужно будет вычислить $3^{1000} \bmod{77}$, он довольно быстро даст ответ. А Вашим способом Вы будете считать долго. Поэтому рекомендую познакомиться с этим алгоритмом. Иначе придётся изобретать велосипед.

Mikle1990 в сообщении #631279 писал(а):

Правильно ли я сделал?

Правильно, но бесперспективно.

[Mikle1990]

nnosipov, ну расскажите же про этот алгоритм, пожалуйста

[nnosipov]

Называется "бинарный алгоритм возведения в степень по модулю". Он известен с давних времён, несложен, литературы хватает, поищите, найдите и прочитайте. И не забудьте поэкспериментировать с ним, это имеет смысл. В частности, вычислите при помощи обычного калькулятора $3^{1000} \bmod{77}$.

[Батороев]

Mikle1990
Все верно, т.к. $3^{53}=3^{(17+17+17+2)}=3^{17}\cdot 3^{17}\cdot 3^{17}\cdot {3^2}$

-- 15 окт 2012 21:32 --

nnosipov в сообщении #631288 писал(а):

Называется "бинарный алгоритм возведения в степень по модулю". Он известен с давних времён, несложен, литературы хватает, поищите, найдите и прочитайте. И не забудьте поэкспериментировать с ним, это имеет смысл. В частности, вычислите при помощи обычного калькулятора $3^{1000} \bmod{77}$.

Бинарный алгоритм необходим при сложных основаниях или при неизвестных множителях основания и т.д. При простых основаниях легче применять алгоритм, согласно которому рассматривается эквивалентная степень, равная остатку от деления рассматриваемой степени на НОК степеней $p_i-1$.
Например $\text{НОК}(7-1;11-1)=30$
$1000\equiv {10}\pmod {30}$
$3^{1000}\equiv 3^{10}\equiv {67}\pmod {77}$.

[Mikle1990]

Батороев, что-то я запутался
Вот смотрите, у меня есть вот это
$C=3^{53}\pmod{77}$

Как сделать вычисления, используя приведённый Вами алгоритм?

[Батороев]

Mikle1990 в сообщении #631307 писал(а):

Батороев, что-то я запутался
Вот смотрите, у меня есть вот это
$C=3^{53}\pmod{77}$

Как сделать вычисления, используя приведённый Вами алгоритм?

$53\equiv 23\pmod {30}$
$3^{53}\equiv 3^{23}\pmod{77}$
А уж дальше "включайте" свой алгоритм, например:
$23=7+7+7+2$
$3^{23}=(3^7)^3\cdot 3^2 $

-- 15 окт 2012 21:59 --

nnosipov
Извиняюсь, не обратил внимание на название темы, в которой присутствует слово "шифрование". В этом случае, конечно же, лучше бинарный алгоритм.

[Mikle1990]

Спасибо, друзья!
В курсовой сделаю так, как я изначально писал, но и бинарный алгоритм, тоже щас попытаюсь понять