А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

Из равенства ab=ac следует, что a(b—c)=0. Так как элемент а ненулевой, то b–c=0, т.е. b=c.

□

Обратим внимание, что данное свойство означает логическое сокращение, а не умножение на элемент, обратный к элементу «а ». Кстати, такого обратного может и не существовать.

1.3. Деление с остатком.

Помните фильм про Буратино и знаменитый диалог Лисы Алисы и Кота Базилио: “Пять на два не делится! Вот тебе, Базилио, один золотой, а вторую неделящуюся половину я забираю себе!” Кот ничего не понял, но почувствовал, что его обманывают.

Что означает «делится», мы выше видели, это когда есть дополнительный множитель и он восстанавливает равенство. А если множителя нет. Тут мы вступаем на зыбкую почву приближений.

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

Формально понятие степени можно ввести так.

Определение. Пусть К – кольцо без делителей нуля. Степенью элементов кольца К называется отображение ненулевых элементов кольца во множество натуральных чисел такое, что выполняется условие монотонности: Другими словами, степень произведения не меньше степени сомножителя. (Обратим внимание, что для нуля степень не определена!)

Если определено понятие степени элемента, то можно говорить о делении с остатком.

Определение Кольцо К называется кольцом с алгоритмом деления с остатком или евклидовым, если или r=0.

Евклидовых колец не очень много. Нас же будут в основном интересовать два из них.

Пример 1.

Кольцо целых чисел Z является евклидовым, при этом степенью целого числа является его модуль. Алгоритм деления с остатком в кольце целых чисел изучался в школе.

Пример 2.

Пусть P – поле, тогда кольцо многочленов P[x] является евклидовым, при этом степенью является обычная степень многочлена. Алгоритм деления с остатком – обычное деление многочленов уголком.

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

Но прежде введем понятие наибольшего общего делителя (НОД) и двойственное ему наименьше обще кранное (НОК).

Определение. Элемент d=НОД(a,b) называется наибольшим общим делителем элементов a и b, если выполняются два условия:

1) d\a, d\b – т.е. d - общий делить,

2) Если s\a, s\b , то s\d – наибольший делитель, в том смысле, что он делится на все остальные делители.

Понятие наименьшего общего кратного НОК не так важно как НОД, но его введение поучительно в силу свой двойственности к НОД. «Наибольший» заменяется на «наименьший», «делится» на «делит».

Определение. Элемент m=НОК(a,b) называется наименьшим общим кратным элементов a и b, если выполняются два условия:

1) m: a\m, b\m - общий кратный,

2) Если a\n, b\n , то m\n – наименьшее кратное, в том смысле, что оно делит все остальные кратные.

Фундаментальный факт состоит в том, что в евклидовых кольцах, а значит в кольце целых чисел и кольце многочленов над полем, – НОД существует и его можно выразить через исходные элементы.

Теорема (Основная теорем о евклидовых кольцах).

Пусть К – евклидово кольцо, тогда любые элементы имеют наибольший общий делитель и, более того, такие, что d=НОД(a,b)=au +bv.

Доказательство.

а) Применяя свойство деления с остатком получим табличку уменьшающихся остатков. Так как степень каждого остатка – натуральное число, а натуральные числа не могут убывать бесконечно, то табличка будет конечной, а последний остаток нулевым.

В нашей табличке получилось n+2 строки. Какой же из участвующих в ней элементов является долгожданным НОД? Это последний ненулевой остаток r_n. Для того, чтобы убедиться, что d=r_n, нужно проверить оба свойства НОД. Прежде всего, просматривая табличку снизу вверх, убеждаемся, что r_n делит a и b. В самом деле, последняя строка нам гарантирует, что r_n\r_n-1. Из предпоследней строки следует, что r_n\r_n-2 и т.д. Из третьей строки следует, что r_n\r, из второй, что делит b, а из первой, что r_n\a.

Теперь проверим, что r_n - наибольший делитель, т.е., что он делится на любой s такой, что s\a и s\b. Теперь просматриваем нашу табличку сверху вниз. Из первой строчки следует, что s\r, из второй, что s\r₁ и т.д. Из предпоследней строки следует, что s\r_n. Таким образом, последняя строка даже не понадобилась.

б) Осталось выразить остаток r_n через исходные элементы a и b. Для этого опять просматриваем нашу табличку снизу вверх. Из предпоследней строки получаем r_n =r_n-2+(-q_n)r_n-1, из третьей снизу r_n-1=r_n-3+(-q_n-1)r_n-2, поэтому

r_n=r_n-2+(-q_n)r_n-1=r_n-2+(-q_n)(r_n-3+(-q_n-1)r_n-2)=r_n-2(1+(-q_n)(-q_n-1))+r_n-3(-q_n).

Поднимаясь снизу вверх, мы последовательно выразим r_n через r_n-2 и r_n-1, потом через r_n-3 и r_n-2 и т.д. И, наконец, через a и b.

□

Таким образом, в кольце целых чисел и кольце многочленов над полем всегда можно эффективно найти НОД. Алгоритм, приведенный выше, его называют алгоритмом Евклида, реализован в большинстве компьютерных систем, в том числе и в тех, что используются для нужд криптографии.

Данная теорема имеет массу приложений, например, с ее помощью строятся поля Галуа.

Теорема (Первая теорема о поле Галуа).

Если натуральное число p является простым, то кольцо вычетов Z_p на самом деле является полем.

Эта теорема была доказана в п.5 §3 Главы 1 как утверждение.

Упражнение. Найдите обратные по умножению к остатку 5 в полях Z₇, Z_17, Z₁₂₇. Проще всего обратный искать по алгоритму Евклида.

1.4. Основная теорема арифметики.

Название это несколько устарело, но сама теорема об однозначном разложении на простые множители не устарела. Теорема эта несколько суховата и аккуратно ее сформулировать не так-то просто. Но на ней, как на фундаменте держится вся арифметика, и все приложения теории чисел. Эта же теорема имеет место и для кольца многочленов над полем, а более широко для всех евклидовых колец. Для них мы ее и докажем.

Однозначность далеко не всегда имеет место. Например, игрушку Лего как не разбирай, простейшие детали окажутся одни и те же. А вот огурец можно разрезать вдоль, а можно и поперек.

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

.

Можно предложить и другие. Однако, различия в этих представлениях не очень существенные. Минус единица и единица, это единственные обратимые элементы в кольце целых чисел (на обратимые элементы делятся любые элементы), а числа 2 и -2, 5 и -5 – ассоциированные, т.е. отличаются друг от друга на обратимые. То, что 2 и 5 в разных записях числа 10 переставлены местами тоже не существенно, поскольку имеем место коммутативность умножения. Все эти наблюдения подсказывают определение.

Определение. Два разложения элемента “a” коммутативного кольца К на простые множители

называются ассоциированными, если - обратимые элементы, n=m, простые элементы p_i и q_j, возможно после перестановки, попарно ассоциированы, т.е. p₁ ассоциирован с q₁, p₂ ассоциирован с q₂ и т.д.

В кольце многочленов простые элементы обычно называют неприводимыми многочленами. Так сложилось исторически, поскольку в прежние времена, разложение многочленов на множители называлось приведением к простому виду. Поэтому, если разложить не удавалось, то и называли неприводимым. Это примерно то же самое, почему у моряков не повар, а кок. Поскольку говорить, что неприводимые элемент кольца многочленов – это простой элемент кольца многочленов, излишний педантизм, то приведем и явное определение.

Определение. Многочлен называется неприводимым, если он не раскладывается в произведение многочленов меньшей степени.

Поиск простых элементов, в том числе и простых чисел и неприводимых многочленов, весьма нетривиальная задача, над которой в мире работают тысячи специалистов и миллионы микропроцессоров. Нам нужно доказать, что в кольце целых чисел Z и кольце P[x] многочленов над полем имеет место однозначное разложение на простые множители. Кстати, на этом факте держится вся криптография с открытым ключом, в том числе и знаменитый RSA.

Как обычно, сделаем это сразу для всех евклидовых колец.

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

Кратко такие кольца называются факториальными. Но можно это слово и не запоминать. Некоторые племена Африки не знают слова зонтик, они просто говорят: “Домик, который белый человек носит в руках и раскрывает над головой, когда идет дождь.”

Фраза в определении факториального кольца о том, что каждый элемент должен иметь хотя бы одно разложение, не ритуальная. Не факт, что такие разложения есть вообще, а про то, чего нет можно доказать все что угодно. Например, я утверждаю, что все алмазы, хранящиеся у меня в доме, имеют вес больше 10 кг. (50 тыс. карат). Что бы меня опровергнуть требуется найти хотя бы один алмаз, который бы весил меньше 10 кг. Такого алмаза найти невозможно потому, что алмазов у меня нет вообще!

Теорема.

В евклидовом кольце любой элемент имеет разложение на простые множители.

Доказательство.

Идея доказательства очень проста. Поскольку каждый элемент евклидова кольца имеет степень, а степень сомножителя не больше чем степень произведения, то мы не сможем бесконечно раскладывать на множители. Неразложимые множители и будут простыми элементами. Теперь реализуем эту идею аккуратно. Запустим индукцию по степени элемента “a”. База индукции – неразложимые элементы (независимо от их степени, так что, фактически, имеет место двойная индукция).

Шаг индукции. Пусть , тогда, по предположению индукции сомножители b и c имеют разложение на простые множители, а значит, разложим и исходный элемент “a”.

Самый трудный случай. Пусть , т.е. один из сомножителей не уменьшил свою степень, это допускается определением степени. Тогда применим деление с остатком, «непокорный» элемент “b” поделим на элемент a: .

Следовательно, . Чтобы не возникло противоречия , остается согласиться, что 1–cq=0, т.е. cq=1. Значит элементы a и b ассоциированы, т.е., “а” – и принадлежит базе индукции.

Характеристики

Список файлов книги