Читать онлайн «Математические методы в теории защиты информации»

В. А. Горбунов МАТЕМАТИЧЕСКИЕ МЕТОДЫ В ТЕОРИИ ЗАЩИТЫ ИНФОРМАЦИИ -ИИ МОСКВА ИЗДАТЕЛЬСТВО МОСКОВСКОГО ГОСУДАРСТВЕННОГО ГОРНОГО УНИВЕРСИТЕТА 2004 УДК 519. 48 ББК 22. 1 Г 67 Горбунов В. А. Математические методы в теории защиты информации. — М. : Издательство Московского государственного горного университета, 2004. — 82 с : ил. ISBN 5-7418-0339-3 УДК 519. 48 ББК 22. 1 ISBN 5-7418-0339-3 © В. А. Горбунов, 2004 © Издательство МГГУ, 2004 © Дизайн книги. Издательство МГГУ, 2004 ПРЕДИСЛОВИЕ В настоящее время простые числа используются в при­ кладных науках теории чисел, таких как криптография и за­ щита информации. Широко известная система кодирования RSA использует простые числа с количеством знаков более 100. Суть системы проста: если два таких числа перемножить, то полученное число разложить на множители практически невозможно за обозримое количество лет. Если п = p q, где pwq простые чис­ ла с большим количеством знаков, то сообщение «и» переда­ ется открытым ключом, а числа р и q секретные (их знает только получатель). Для того, чтобы выяснить является ли число с большим количеством знаков простым или составным, существуют раз­ личные тесты, которые, в основном, используют арифметику остатков. Практическая польза гипотезы Гольдбаха (которой по­ священа глава 2) состоит в том, что по малым простым числам можно находить сколь угодно большие простые числа. В главе 3 рассматриваются праймориальные последова­ тельности чисел, то есть чисел вида 2п = т • р * , где pi = 2-3-5-р к — произведение первых к простых чисел, а т-1, 2,... , р -1. к+1 Эти последовательности являются перио­ дическими (с периодом pi) и с ними связаны некоторые осо­ бенности распределения простых чисел. В частности, эти чет­ ные числа имеют наибольшее число разбиений в сумму двух простых чисел по сравнению с ближайшими четными числа­ ми. Каждая последовательность вида р\, 2 • р\, 3 • р\, . . . , [рк+] - 1 ) - pi имеет в среднем около 20 простых чисел вида т-р\-\ или т- pi + 1 , где т = l,2,3,... ,p t+1 -1. 3  Простые числа в окрестности праймориальных членов по­ следовательностей могут быть записаны в виде п- р* — p , где к t p i — простое число, принадлежащее интервалу (0; р\), < Рк Pi < Рк • Используя такое представление простых чисел, доказывается теорема о близнецах, следствием которой явля­ ется вывод: если множество пар простых чисел — близнецов ( р ; р , + 2 ) ограничено, то гипотеза Гольдбаха неверна и, на­ ( оборот, если гипотеза Гольдбаха справедлива, то множество пар простых чисел — близнецов неограниченно.