Файл: Программа работы.doc

Оглавление



Предисловие
Теория чисел, наряду с геометрией, является одной из древнейших областей математики. Значительный вклад в эту область знаний внесли виднейшие математики древности и нового времени: Евклид, Пифагор, П. Ферма, Эйлер и др. Однако до последнего времени теория чисел считалась одной из наиболее абстрактных областей математики, не имеющей практического применения.

Подобные взгляды господствовали в математике до становления теоретической криптологии в последней четверти XX в. Разработка криптографических систем с открытым ключом обусловила новые области применения теории чисел. Теория чисел из абстрактной научной дисциплины, занимающейся коллекционированием фактов о замечательных свойствах натуральных чисел, превратилась в инструмент синтеза и анализа криптографических систем, чрезвычайно востребованных на практике [7].

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

---

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

РАЗДЕЛ 1. МАТЕМАТИЧЕСКИЕ ОСНОВЫ КРИПТОГРАФИИ

1.1. ДЕЛИМОСТЬ И АЛГОРИТМ ЕВКЛИДА

1.1.1 Отношение делимости

Понятие делимости является одним из фундаментальных понятий теории чисел.

Определение 1. Для данных целых чисел и говорят, что делит (или иными словами, что делится на ), и обозначают если существует такое целое число , что :

, где множество целых чисел.

(1)

В этом случае число называют делителем числа . Очевидно, что любое целое число имеет, по крайней мере, два положительных делителя: 1 и .

Определение 2. Собственным делителем числа называют любой положительный делитель, не равный .

Определение 3.

---

Нетривиальным делителем числа называют любой положительный делитель, не равный 1 или .

Введенное понятие нетривиального делителя используем для определения понятия простого числа.

Определение 4. Простым (prime) называют целое число большее 1, не имеющее нетривиальных делителей.

Определение 5. Составным (complex) называют число, имеющее, по крайней мере, один нетривиальный делитель.

Непосредственно из определения делимости (1) следуют свойства делимости:

1. Если делит , и − любое целое число, то делит произведение :

.

2. Если делит , а , в свою очередь, делит , то делит :

.

3. Если делит , и делит

---

, то делит :

.

В дальнейшем, для некоторого простого и целого, неотрицательного числа запись вида будем использовать для обозначения того факта, что − наивысшая степень , делящая :

.

В этом случае говорят, что точно делит .
Основная теорема арифметики утверждает, что любое натуральное число может быть представлено в виде произведения простых делителей единственным образом, с точностью до перестановки. Данное представление принято записывать в форме произведения делителей в соответствующих степенях, располагая простые числа в порядке возрастания.
Пример 1. Рассмотрим разложение числа в виде делителей в соответствующей степени:

.
Из основной теоремы арифметики следуют свойства отношение делимости:

4. Простое число делит произведение целых чисел

---

, в том и только в том случае, когда делит , либо делит :

.

5. Если делит и делит , и если и не имеют общих делителей больших 1, то произведение делит :

.

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

Таким образом, если , то для

---