Проведена работа от простых рассуждений (принцип Дирихле) до более сложных (теоремы теории чисел). Показано практическое применение теории чисел на алгоритме шифрования RSA.


Аннотация на работу:

«Принцип Дирихле и алгоритм шифрования RSA»

Нестерова Степана и Лындиной Ксении, учеников 7 “А” класса,

МАОУ Лицей № 128.

В результате работы изучена литература по принципу Дирихле; составлена подборка задач на этот принцип; составлена подборка задач и теорем на теорию чисел, показана важная роль принципа в становлении теории чисел; напечатаны на 3D принтере кролики и клетки; проведена работа от простых рассуждений (принцип Дирихле) до более сложных (теоремы теории чисел),

показано практическое применение теории чисел на алгоритме шифрования RSA;

выполнена работа по составлению открытого и закрытого ключа алгоритма шифрования RSA.

Гипотеза о рациональности применения принципа Дирихле подтвердилась.

ВВЕДЕНИЕ

Несмотря на совершенную очевидность принципа Дирихле, его применение является весьма эффективным методом решения некоторых задач, дающим наиболее простое и изящное решение.
Гипотеза: применение принципа Дирихле при решении определённых задач – наиболее рациональный подход.
Цель: изучить принцип Дирихле.
Задачи: изучить литературу по принципу Дирихле;
составить подборку задач на этот принцип;
классифицировать их по содержанию;
рассмотреть применение принципа Дирихле в теории чисел;
напечатать на 3D принтере "кроликов" и "клетки" для наглядной иллюстрации данного принципа. Объектом исследования является принцип Дирихле.
Предметом исследования является применение принципа Дирихле при решении задач и в теории чисел.

ИТОРИЧЕСКИЕ СВЕДЕНИЯ

Дирихле Петер Густав Лежен (13.2.1805-5.5. 1859) - немецкий математик. Родился в Дюрене.
В 1822-1827гг. был домашним учителем в Париже. Входил в кружок молодых ученых, которые группировались вокруг Ж. Фурье.
В 1827 занял место доцента в Бреславе; с 1829 работал в Берлине.
В 1831-1855гг.- профессор Берлинского университета, после смерти К.Гаусса (1855г.) - Гёттингенского университета.
С именем Дирихле связаны задача, интеграл (ввел интеграл с ядром Дирихле), принцип, характер, ряды. Лекции Дирихле имели огромное влияние на выдающихся математиков более позднего времени, в том числе на Г.Римана, Ф. Эйзенштейна, Л.Кронекера, Ю.Дедекинда.


ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Рассмотрим одну из его форм — принцип Дирихле.
Этот принцип утверждает, что, если множество из N элементов разбито на п непересекающихся частей, не имеющих общих элементов, где N>n то, по крайней мере, в одной части будет более одного элемента.
Этот принцип часто является хорошим средством при доказательстве важнейших теорем в теории чисел, алгебре, геометрии.
В литературе этот принцип также встречается под названиями: "принцип ящиков и объектов", "принцип коробок и предметов", "принцип кроликов и клеток".
В общей форме этот принцип выглядит так:
Если (n+1) "кролик" помещен в n "клетках", то имеется "клетка", в которой находятся не менее двух "кроликов".
Несмотря на совершенную очевидность этого принципа, его применение является весьма эффективным методом решения задач, дающим во многих случаях наиболее простое и изящное решение. Однако во всех этих задачах часто нелегко догадаться, что считать "кроликом", что - "клеткой", и как использовать наличие двух "кроликов", попавших в одну "клетку". С помощью принципа Дирихле обычно доказывается существование некоторого объекта, не указывая, вообще говоря, алгоритм его нахождения или построения. Это даёт так называемое неконструктивное доказательство - мы не можем сказать, в какой именно клетке сидят два "кролика", а знаем только, что такая "клетка" есть.
Приводимые ниже теоремы и задачи показывают, что природа "кроликов" и "клеток" в различных задачах может сильно отличаться друг от друга.

ПРАКТИЧЕСКАЯ ЧАСТЬ
Геометрические задачи
Задача. Внутри равностороннего треугольника со стороной 1 расположено 5 точек. Доказать, что расстояние между некоторыми двумя из них меньше 0,5.
Решение.
Средние линии правильного треугольника со стороной 1 разбивают его на четыре правильных треугольничка со стороной 0,5. Назовём их "клетками", а точки будем считать "кроликами". По принципу Дирихле из пяти точек хотя бы две окажутся в одном из четырёх треугольничков. Расстояние между этими точками меньше 0,5, поскольку точки не лежат в вершинах треугольничков. (Здесь использована известная лемма о том, что длина отрезка, расположенного внутри треугольника, меньше длины его наибольшей стороны.)
Задача. Внутри равнобедренной трапеции со стороной 2 расположено 4 точек. Доказать, что расстояние между некоторыми двумя из них меньше 1.
Решение.
Разобьем трапецию со стороной 2 на три треугольника со стороной 1. Назовем их "клетками", а точки – "кроликами". По принципу Дирихле из четырех точек хотя бы две окажутся в одном из трех треугольников. Расстояние между этими точками меньше 1, поскольку точки не лежат в вершинах треугольников.
Задачи на пары
Задача. В классе мальчиков больше чем девочек. Доказать, что хотя бы за одной партой сидят два мальчика, если число учащихся в классе чётное и за каждой партой сидит два ученика.
Решение. Число занятых парт равно половине числа учащихся, будем считать, что число "кроликов" равно числу мальчиков, число клеток равно числу парт, "кроликов" больше чем "клеток", значит, есть "клетка", в которой сидит не менее двух "кроликов". Значит, есть парта, за которой сидят два мальчика.
Задача. На планете Земля океан занимает больше половины площади поверхности. Докажите, что в мировом океане можно указать две диаметрально противоположные точки.
Решение. Будем считать "кроликами" точки океана, а "клетками" - пары диаметрально противоположных точек планеты. Количество "кроликов" в данном случае - это площадь океана, а количество "клеток" - половина площади планеты. Поскольку площадь океана больше половины площади планеты, то "кроликов" больше, чем "клеток". Тогда есть "клетка", в которой сидит не менее двух "кроликов", т.е. пара противоположных точек, обе из которых - океан.

Задачи на даты рождения
Задача. В доме живут 40 учеников. Существует ли такой месяц в году, когда хотя бы 2 ученика празднуют свой день рождения.
Решение. Пусть "клетками" будут месяцы, а "кроликами" - ученики. Распределяем, "кроликов" по "клеткам" в зависимости от месяца рождения. Так как число месяцев, то есть, "клеток", равно 12, а число учеников, то есть, "кроликов" 40 , согласно принципу Дирихле существует "клетка" (месяц) с по крайней мере 2 "кролика" (ученика).
Задача. В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года.
Решение. Всего в году 365 дней. Назовём дни "клетками", а учеников "кроликами", тогда в некоторой коробке сидят не меньше двух "кроликов". Значит хотя бы два ученика родились в один день.
"кроликов" больше чем клеток, значит, есть "клетка", в которой сидит не менее двух "кроликов". Значит, существуют хотя бы две ели с одинаковым числом иголок.
Задачи на комбинаторику
Задача. В мешке лежат шарики 2-х разных цветов. Какое наименьшее количество шариков надо на ощупь вынуть из мешка, чтобы среди них заведомо оказались два одного цвета.
Решение: 3 шарика. Это - просто применение принципа Дирихле: "кроликами" будут взятые шарики, а "клетками" - черный и белый цвета. Клеток две, поэтому если "кроликов" хотя бы три, то какие-то два попадут в одну "клетку" (будет 2 одноцветных шарика). С другой стороны, взять два
Задача. Укажите, какое наименьшее число карт надо наугад взять из колоды, чтобы среди них заведомо оказались две одной масти.
Решение. 5 карт. "Кроликами" будут взятые карты, а "клетками" - масти карт, их четыре. Клеток 4, поэтому если "кроликов" хотя бы 5, то какие-то две попадут в одну клетку (будет 2 карты одинаковой масти).
Задачи на теорию чисел
Задача. Доказать, что среди шести целых чисел найдутся два числа, разность которых делится на 5.
Решение. Поскольку чисел ("кроликов") больше, чем остатков ("клеток") согласно принципу Дирихле, существует одна "клетка", содержащая более одного предмета. То есть, существуют (по крайней мере) два числа, помещенные в одну и ту же "клетку". Следовательно, существуют два числа с одинаковым остатком от деления на 5. Тогда, разность этих чисел делится на 5. Пусть это будут A = 5a + r и B = 5b + r. Тогда их разность делится на 5. A - B = 5(a - b).
Задача . Дано n+1 различных натуральных чисел. Доказать, что из них можно выбрать два числа А и В, разность которых делится на n.
Решение. По крайней мере, два числа из n+1 чисел дают одинаковый остаток при делении на n (принцип Дирихле). Пусть это будут A = na + r и B = nb + r. Тогда их разность делится на n: A - B = n(a - b).
Задача. Докажите, что среди 20 различных натуральных чисел найдутся хотя бы два числа А и В такие что, число A2-B2 делится на 19.
Решение. По крайней мере, два числа из 20 чисел дают одинаковый остаток при делении на n (принцип Дирихле). Пусть это будут A = 19a + r и B =19b + r. Тогда их разность делится на 19: A - B = n(a - b), значит и A2-B2=(A-B)(A+B) делится на19.
Задача . Дано n+1 различных натуральных чисел. Доказать, что из них можно выбрать два числа А и В такие что, число A2-B2 делится на n.
Решение. По крайней мере, два числа из n+1 чисел дают одинаковый остаток при делении на n (принцип Дирихле). Пусть это будут A = na + r и B = nb + r. Тогда их разность делится на n: A - B = n(a - b), значит и A2-B2=(A-B)(A+B) делится на n.

Теорема. Любой многочлен с целыми коэффициентами (отличный от константы) при некотором натуральном значении аргумента принимает значение, представляющее собой составное число.
Доказательство. Пусть f(x) = a0xn + a1xn - 1 +. . . +an, где все ai - целые числа. Предположим, что при некотором k значение многочлена f(x) - простое число, т.е. f(k) = p, где p - простое. Многочлен степени n принимает одно и то же значение не более чем в n точках. (Действительно, если f(x) = y0 более чем в n точках x1, x2, . . ., xn + 1, то многочлен g(x) = f(x)-y0 имеет корни x1, x2, . . ., xn + 1, а, как известно, любой многочлен не может иметь более n действительных корней.) Покажем, что найдётся такое целое t, что f(k+pt) отлично от 0 и p. Нам поможет принцип Дирихле. Будем считать значение многочлена (в натуральных точках) "клетками", а натуральные числа вида k+pt "кроликами". Натуральное число N = k+pt будем помещать в "клетку", соответствующую значению многочлена f(N). Согласно высказанному выше утверждению, в "клетке" не может поместиться больше n "кроликов". Так как "кроликов" много, то это значит, что f(k + pt) не может принимать только значение 0 и p при различных целых t, т.е. найдётся "заяц" k+pt, который не попадёт ни в "клетку" 0, ни в "клетку" p. Итак, при некотором t имеем: f(k + pt) № 0 и f(k + pt) № p. Разлагая f(k + pt) по степеням pt (используя бином Ньютона), получим f(k+pt) = f(k) + c1pt + c2(pt)2 + . . . + cn(pt), где все ci - некоторые целые числа. Поскольку f(k) = p, из предыдущего равенства получаем, что f(k + pt) делится на p, причём f(k + pt)№0 и f(k + pt)№ p, так что f(k + pt) - составное число. Теорема доказана.
Следующая теорема, сформулированная П. Ферма, является одним из самых фундаментальных фактов в теории делимости целых чисел и находит широкое применение, как в теоретических исследованиях, так и в арифметических приложениях.
Малая теорема Ферма. Если p - простое число, a - целое число, не делящееся на p, то ap - 1 при делении на p даёт остаток 1, т. е. .
Доказательство. Каждое из p - 1 чисел a, 2a, . . ., (p-1)a ("кроликов") даёт при делении на p ненулевой остаток (ведь a не делится на p):
a = k1p + r1,
2a = k2p + r2
. . . . . . . . . . . . . . .
(p - 1)a = kp - 1p + rp - 1
Если число различных встречающихся здесь остатков ("клеток") меньше p - 1, то среди них найдутся по крайней мере два одинаковых ("в клетке по крайней мере два кролика"). Но это невозможно, так как при rn = rm число (n-m)a = (kn-km)p делится на p, что противоречиво, ибо |n-m|< p и a взаимно просто с p. Значит, все остатки r1, . . . , rp - 1 между собой различны и образуют перестановку чисел 1, 2, . . . , p - 1. Перемножая все предыдущие равенства, получаем
(p-1)! ap - 1 = Np+ r1r2. . .rp - 1 = Np + (p-1)!,
(p-1)! ap-1-(p-1)!=Np
(p-1)! (ap-1-1)=Np
где N - некоторое целое число. Следовательно, (p-1)!(ap-1-1) делится на p, а тогда и ap - 1 - 1 делится на p. Теорема доказана.
Следствие. Если p - простое число, то при любом целом a разность .
Малая теорема Ферма является следствием теоремы Эйлера.
Теорема Эйлера. Если взаимно просты, то , где -функция Эйлера равная количеству натуральных чисел меньших n и взаимно простых с ним. Принимается, что число 1 взаимно просто со всеми натуральными числами. Так (для числа 7 взаимно простые числа меньше его: 1.2.3.4.5.6). В приложении 3 представлены первые 99 значений функции Эйлера.
Если p простое число, то , тогда теорема Эйлера принимает вид: , а это малая теорема Ферма.
Свойство функции Эйлера: ,
Алгоритм шифрования RSA
Свойства функции Эйлера использовали в 1978 году Рональд Ривест, Ади Шамир и Леонард Адлеман для построения системы шифрования с открытым ключом, получившей название по первым буквам фамилий авторов- система RSA.
В криптосистеме с открытым ключом, в отличие от симметричной, используются два ключа: открытый и закрытый (закрытый хранится в секрете). Открытый ключ используется для шифрования сообщений, закрытый ключ –для расшифрования сообщений.
Генерация ключей RSA
Всё начинается с генерации ключевой пары (открытый, закрытый ключ). Генерация ключей в RSA осуществляется следующим образом:
1. Выбираются два простых числа p и q (такие что p неравно q), p=5 и q=11.
2. Вычисляется .
3. Вычисляется значение функции Эйлера
от n: .
Находим - открытый ключ, - закрытый ключ, такие, что
число e должно лежать в интервале: ,
. Пусть , найдём .
-обратный элемент элементу e, пусть ,
Тогда по теореме Эйлера

Закрытый ключ можно найти по расширенному алгоритму Евклида в программе Microsoft Excel .

Шифрование сообщения открытым ключом е:

Расшифровать сообщение может только обладатель секретного ключа d:


Введём таблицу символов, где каждому символу соответствует определённое число:

В приведённом выше примере работы алгоритма шифрования RSA зашифрована буква Н.
Зашифруем сообщение:
НПК “ЮНЫЕ ИНТЕЛЛЕКТУАЛЫ СРЕДНЕГО УРАЛА” 2017
C помощью таблицы переведём в набор чисел:
15 17 12 36 39 32 15 29 6 36 10 15 20 6 13 13 6 12 20 21 13 29 36 19 18 6 5 15 6 4 16 36 21 18 1 13 1 40 36 43 41 42 48
Применив открытый ключ, получим зашифрованную информацию:
5 8 23 31 19 43 5 39 41 31 10 5 15 41 7 7 41 23 15 21 7 39
31 24 17 41 25 5 41 49 36 31 21 17 1 7 1 50 31 32 46 48 27
Работа вручную –это длительный и трудоёмкий процесс, поэтому была использована программа Microsoft Excel, смотри приложение 4 и 5.
При работе с закрытым ключом в программе Microsoft Excel происходит сбой , так как 23 степень числа имеет больше десяти разрядов, поэтому работа выполнялась вручную с помощью свойств сравнений.
Простым перебором закрытого ключа произошёл взлом системы при , но это значение не удовлетворяет всем условиям алгоритма, почему это произошло?
Устойчивость зависит от разрядности ключей, чем больше их разрядность, тем меньше вероятность взлома, но тогда сложнее вычислять ключи.


ЗАКЛЮЧЕНИЕ

В результате работы изучена литература по принципу Дирихле;
составлена подборка задач на этот принцип;
составлена подборка задач и теорем на теорию чисел;
напечатаны на 3D принтере кролики и клетки;
показано практическое применение теории чисел на алгоритме шифрования RSA;
проведена работа от простых рассуждений (принцип Дирихле) до боллее сложных(теоремы теории чисел), выполнены эксперименты с криптографией.
Гипотеза о рациональности применения принципа Дирихле подтвердилась.
В дальнейшем планируется более глубокое изучение теории чисел и применение её в защите информации. Необходимо научиться писать программы для автоматизации вычислительных действий.

ЛИТЕРАТУРА
1. Андреев А.А., Горелов Г.Н., Люлев А.И., Савин А.И. "Принцип Дирихле", Самара "Пифагор", 1997г
2. И. Л. Бабинская. Задачи математических олимпиад. М.: Наука, 1975.
3. Д. X. Муштари. Подготовка к математическим олимпиадам: задачи, темы, методы. Казанский ун-т, 1990.
4. В. В. Прасолов. Задачи по планиметрии. Ч. 2. М.: Наука, 1991.
5. В. Г. Болтянский. Шесть зайцев в пяти клетках. // Ж-л «КВАНТ», 1977,No2.
6. А. А. Леман. Сборник задач московских математических олимпиад. Под ред. В.Г. Болтянского. М.: Просвещение, 1965.
7. Ю. Ф. Фоминых. Принцип Дирихле. // Ж-л «Математика в школе», 1996, No3.

0
Подписка на новости
Контакты

Адрес: г. Екатеринбург, ул. Мамина-Сибиряка 145, к. 1119 (на карте)

Тел.: +7 (343) 355-93-88

info@cosmoport.club