Жуан Гомес - Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография

Это и есть нужный нам результат.

2. Если НОД (m,n) 1 и n = р∙q, тот содержит или только множитель р, или только q, или оба одновременно.

Пусть m содержит только множитель р. Тогда, во-первых, m кратно р, то есть существует целое число r, такое, что m = rр. Поэтому mde  0 (mod р) или mde = m (mod р), другими словами, существует значение А, такое, что:

mde — m = Ар. (1)

Во-вторых, мы имеем:

(me)d = med = mk ф(n)+1 = m k ф(n)∙m = (mф(n))k∙m = (m(q-1))k(p-1)∙m.

Так как НОД (m, n) = р, НОД (m, q) = 1, то по теореме Ферма m(q-1)  1 (mod q).

Подставим это в предыдущее выражение.

(me)d = med = mk ф(n)+1 = m k ф(n)∙m = (mф(n))k∙m = (m(q-1))k(p-1)∙m  1k (р-1)∙m  m (mod q).

Откуда мы заключаем, что существует значение В, такое что:

mde — m = Вq. (2)

Из (1) и (2) следует, что разность (mde — m) делится на n = рq, поэтому

mde — m  0 (mod n).

Аналогично это доказывается для случая, когда m содержит только множитель q.

В случае, когда m кратно и р, и q одновременно, результат тривиален. Следовательно,

(mе)d  m (mod n).

Таким образом, мы продемонстрировали математическую основу алгоритма RSA.

Fernandez, S., Classical Cryptography. Sigma Review No. 24, April 2004.

Garfunkel, S., Mathematics in Daily Life, Madrid, COMAP, Addison-Wesley, UAM, 1998.

Gomez, J., From the Teaching to the Practice of Mathematics Barcelona, Paidos, 2002.

Kahn, D., The Codebreakers: The Story of Secret Writing, New York, Scribner, 1996.

Издание на русском языке: Кан Д. Взломщики кодов. — М.: Центрполиграф, 2000.

Singh, S., The Secret Codes, Madrid, Editorial Debate, 2000.

Tocci, R., Digital Systems: Principles and Applications, Prentice Hall, 2003.

Издание на русском языке: Тончи Р. Цифровые системы. Теория и практика. — М.: Вильямс, 2004.

Научно-популярное издание

Выходит в свет отдельными томами с 2014 года

Мир математики

Том 2

Жуан Гомес

Математики, шпионы и хакеры.

Кодирование и криптография.

РОССИЯ

Издатель, учредитель, редакция:

ООО «Де Агостини», Россия

Юридический адрес: Россия, 105066,

г. Москва, ул. Александра Лукьянова, д. 3, стр. 1

Письма читателей по данному адресу не принимаются.

Генеральный директор: Николаос Скилакис

Главный редактор: Анастасия Жаркова

Старший редактор: Дарья Клинг

Финансовый директор: Наталия Василенко

Коммерческий директор: Александр Якутов

Менеджер по маркетингу: Михаил Ткачук

Менеджер по продукту: Яна Чухиль

Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт www.deagostini.ru, по остальным вопросам обращайтесь по телефону бесплатной горячей линии в России:

© 8-800-200-02-01

Телефон горячей линии для читателей Москвы:

© 8-495-660-02-02

Адрес для писем читателей:

Россия, 170100, г. Тверь, Почтамт, а/я 245,

«Де Агостини», «Мир математики»

Пожалуйста, указывайте в письмах свои контактные данные для обратной связи (телефон или e-mail).

Распространение:

ООО «Бурда Дистрибьюшен Сервисиз»

УКРАИНА

Издатель и учредитель:

ООО «Де Агостини Паблишинг» Украина

Юридический адрес: 01032, Украина,

г. Киев, ул. Саксаганского, 119

Генеральный директор: Екатерина Клименко

Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт www.deagostini.ua, по остальным вопросам обращайтесь по телефону бесплатной горячей линии в Украине:

© 0-800-500-8-40

Адрес для писем читателей:

Украина, 01033, г. Киев, a/я «Де Агостiнi»,

«Мир математики»

Украïна, 01033, м. Кiев, а/с «Де Агостiнi»

БЕЛАРУСЬ

Импортер и дистрибьютор в РБ:

ООО «Росчерк», 220037, г. Минск,

ул. Авангардная, 48а, литер 8/к,

тел./факс: +375 17 331 94 27

Телефон «горячей линии» в РБ:

© + 375 17 279-87-87 (пн-пт, 9.00–21.00)

Адрес для писем читателей:

Республика Беларусь, 220040, г. Минск,

а/я 224, ООО «Росчерк», «Де Агостини»,

«Мир математики»

КАЗАХСТАН

Распространение:

ТОО «КГП «Бурда-Алатау Пресс»

Издатель оставляет за собой право увеличить рекомендуемую розничную цену книг. Издатель оставляет за собой право изменять последовательность заявленных тем томов издания и их содержание.

Отпечатано в соответствии с предоставленными материалами в типографии:

Grafica Veneta S.p.A Via Malcanton 2

35010 Trebaseleghe (PD) Italy

Подписано в печать: 31.07.2013

Дата поступления в продажу на территории России: 28.01.2014

Формат 70 х 100 / 16. Гарнитура «Academy».

Печать офсетная. Бумага офсетная. Печ. л. 4,5.

Уел. печ. л. 5,832.

Тираж: 200 000 экз.

© Joan Gomez, 2010 (текст)

© RBA Collecionables S.A., 2010

© ООО «Де Агостини», 2014

ISBN 978-5-9774-0682-6

ISBN 978-5-9774-0639-0 (т. 2)