Условие проблеммы:

Показать, что сравнение $%{a^e} \equiv {a^{e \cdot \bmod \,(p - 1)(q - 1)}}\,(\,\bmod \,p \cdot q)$% выполняется для всех целых $%a$% и $%e$%, при условии, что $%p$% и $%q$% различные простые числа и $%e\not \equiv 0\,(\bmod \,(p - 1)(q - 1))$%.

Я пытался доказать так:

Положим, $%n = p \cdot q,\,\,\,\gcd (p,q) = 1$% и $%e' = e\,(\bmod \,\varphi (n))$%. Тогда $%e = m \cdot \varphi (n) + e',\,\,\,\,m \in {\Bbb Z}$%. Получаем $%{a^e} = {a^{m \cdot \varphi (n) + e'}} = {({a^{\varphi (n)}})^m} \cdot {a^{e'}} \equiv {a^{e'}}\,(\,\bmod \,n),$% где последний шаг выполняется через теорему Эйлера. Во время доказательства я выявил, что данное доказательство верно только при условии, что $%a$% и $%n$% взаимно просты. Как доказать для всех целых $%a$% и $%e$%?

задан 26 Сен '14 1:32

изменен 26 Сен '14 16:36

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
1

Сами по себе эти исключительные случаи большой роли не играют, если иметь в виду приложение к криптографии. Числа $%p$% и $%q$% обычно очень большие, а сообщение $%a$% можно выбирать таким, чтобы его значение было меньше $%\min(p,q)$%. Тем не менее, сам вопрос имеет смысл, потому что если исключение не имеет места, то его можно и не оговаривать.

Итак, мы знаем, что $%a^{(p-1)(q-1)}\equiv1\pmod{pq}$%, если $%a$% не делится ни на $%p$%, ни на $%q$%. Рассмотрим случай, когда $%a$% делится на $%p$%. Заключение теоремы Эйлера выполнено уже не будет. Но нам надо проверить не это, а исходное сравнение. Тогда, если $%a$% делится ещё и на $%q$%, то $%a$% будет сравнимо с нулём в любой натуральной степени. Так что пусть $%a$% не кратно $%q$%. В этом случае, согласно малой теореме Ферма, $%a^{q-1}\equiv1\pmod{q}$%. Следовательно, $%a^{(p-1)(q-1)}\equiv1\pmod{q}$%. Из этого вытекает, что $%a^e\equiv a^{e'}\pmod{q}$% в предположении, что $%e\equiv e'\pmod{\varphi(n)}$%. С другой стороны, $%a^e\equiv a^{e'}\pmod{p}$% для любых натуральных показателей, так как по модулю $%p$% получается $%0$%. Тем самым, разность степеней делится и на $%p$%, и на $%q$%, то есть и на $%pq$% тоже. Значит, степени по этому модулю сравнимы.

ссылка

отвечен 26 Сен '14 1:57

изменен 26 Сен '14 3:17

Спасибо, все понял)!

(26 Сен '14 2:40) void_pointer
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×590

задан
26 Сен '14 1:32

показан
262 раза

обновлен
26 Сен '14 3:17

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru