2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Модульная арифметика.
Сообщение02.12.2013, 16:46 
Здравствуйте.
подскажите, почему
$x^{a+m} \mod m = x^m \mod m$ если $x \perp m$
то есть, x и m - взаимно простые.

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

 
 
 
 Re: Модульная арифметика.
Сообщение02.12.2013, 16:51 
Аватара пользователя
$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$
:?:

 
 
 
 Re: Модульная арифметика.
Сообщение02.12.2013, 17:49 
Есть конкретный пример, который я пытаюсь разобрать и понять почему так:
$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.

 
 
 
 Re: Модульная арифметика.
Сообщение02.12.2013, 19:24 
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$
:?:
тоже неверно :-( и даже на описку не тянет.

 
 
 
 Re: Модульная арифметика.
Сообщение03.12.2013, 04:47 
Я наверное неправильно задал вопрос, давайте я задам его по-другому:
Почему
$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 Замечания верные

 
 
 
 Re: Модульная арифметика.
Сообщение03.12.2013, 05:33 
Теорема Эйлера. Вам лучше почитать про азы теории чисел. Например, Виноградов "Основы теории чисел".

 
 
 
 Re: Модульная арифметика.
Сообщение03.12.2013, 13:53 
Спасибо!

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group