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

[antropod]

Здравствуйте.
подскажите, почему
$x^{a+m} \mod m = x^m \mod m$ если $x \perp m$
то есть, x и m - взаимно простые.

Есть ли какая-нибудь теорема, или что-то подобное по этой теме?

[gris]

$2^{5+3}=256=1 \mod 3$
$2^3=8=2 \mod 3$
-----
А, пардон, у Вас там просто описка. Надо читать
$x^{a+m} \mod m = x^a \mod m$ если $x \perp m$

[antropod]

Есть конкретный пример, который я пытаюсь разобрать и понять почему так:
$2^{11} \mod 24 = 8$
$2^{35} \mod 24 = 8$
$2^{59} \mod 24 = 8$

Если еще более подробно, я пытаюсь разобраться как работает алгоритм RSA:
беру 2 простых числа
$p=3$
$q=13$
нахожу $n=pq$
нахожу $\varphi(n) = (p-1)(q-1) = 24 $
затем выбираю открытую экспоненту $e = 11 $
и потом нахожу секретную экспонетну $d$, такую, что $ed = 1 \mod n$
(числа 11, 35, 59, ...) удовлетворяют этому условию.
теперь если я шифрую сообщение [0..38] по формуле $c=m^{11} \mod 39$, то
получаются такие же числа как если бы я брал в качестве показателя степени число 35 или 59.
Точно такая же ситуация, при n = 39.

[Sonic86]

antropod в сообщении #795448 писал(а):

и потом нахожу секретную экспонетну $d$, такую, что $ed = 1 \mod n$

Нет, $d$ определяется соотношением $ed\equiv 1\pmod{\varphi(n)}$.

antropod в сообщении #795417 писал(а):

почему
$x^{a+m} \mod m = x^m \mod m$ если $x \perp m$
то есть, x и m - взаимно простые.

Это неверно, причем, просто ужас как неверно, настолько неверно, что предлагаю Вам контрпример самому найти.

gris в сообщении #795419 писал(а):

Надо читать
$x^{a+m} \mod m = x^a \mod m$ если $x \perp m$

тоже неверно и даже на описку не тянет.

[antropod]

Я наверное неправильно задал вопрос, давайте я задам его по-другому:
Почему
$x^{11} \mod 24 = y$
$x^{11+24} \mod 24 = y$
$x^{11+48} \mod 24 = y$
при любых целых $x \in [0;23]$

это дало мне повод полагать, что
$x^{z+am} \mod m = x^z \mod m$

это равенство выполняется
- при m=24, 36, 40, 42, 54, 60, 72, 84, 100, 108, 120, 126, 156, 168, 180, 200, 216, 220 ...
- при $z \in [2;m)$
- при $a \in [0; 10000]$

1) Почему это равенство выполняется
2) Какое услови должно быть для m, z, a, x

-- 03.12.2013, 05:48 --

Sonic86 Замечания верные

[Cash]

Теорема Эйлера. Вам лучше почитать про азы теории чисел. Например, Виноградов "Основы теории чисел".

[antropod]

Спасибо!