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

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

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

Если кольцо содержит нейтральный элемент по умножению, его обычно называют единицей и обозначают 1 (не путать с числом 1), то, подставляя

с=1, получим, что . Явное противоречие. Таким образом, справедливость, т.е. симметричность определения кольца относительно сложения и умножения, невозможна принципиально.

Пример 7. Множество целых чисел относительно обычных операций сложения и умножения является коммутативным кольцом.

Пример 8. Пусть К – кольцо, множество многочленов K[x] от переменной х с коэффициентами из кольца К относительно обычных операций сложения и умножения многочленов является кольцом. Если кольцо К коммутативно, то и кольцо K[x] тоже коммутативно.

Следствие.

1. Если нейтральный элемент существует, то он единственный.

2. Если операция ассоциативна и у элемента а существует обратный элемент, то он тоже единственный и обозначается «-а », если операция называется сложением, и «а^-1 » или «1/a », если операция называется умножением.

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

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

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

1. Допустим, есть два нейтральных элемента x и y, тогда по определению нейтрального элемента x имеем xy=y и, с другой стороны, xy=x. Значит, x=y.

2. Пусть «b » и «c » – элементы обратные элементу «а ». В силу аксиомы ассоциативности имеем b= b1=b(ас)=(ba)с=1с=с.

3. Имеем, 0а=(0+0)а=0а+0а, следовательно, 0а=0. Отметим, что в этом доказательстве использовалась аксиома нейтрального элемента по сложению, аксиома наличия обратного по сложению, дистрибутивность и неявно ассоциативность по сложению. Всего четыре аксиомы.

(Кстати, при сокращении обеих частей на элемент 0а, которое мы произвели в одно действие, на самом деле использовалось три аксиомы – наличие обратного по сложению, ассоциативность сложения, аксиома нейтрального элемента. Подробно это выглядит так. Пусть «b » - элемент обратный по сложению к элементу 0а, тогда из 0а=0а+0а, следует

0=0а+b=(0а+0а)+b=0а+(0а+b)=0а+0=0а.)

4. Вначале докажем, что (-а)b=-(ab). Для этого нужно проверить, что элемент (-a)b является обратным по сложению к элементу ab. В самом деле, ab+(-а)b=(a—a)b=0а=0. Здесь использовалась дистрибутивность, свойство обратного по сложению и свойство нуля, а также пункт 3 нашего доказательства.

Теперь, используя только что полученный результат, вычисляем

(-а)(-b)=-(а(-b))=-(-(ab)). Так как обратный к обратному есть исходный, то

–(-ab)=ab.

□

Познавательный смысл следствия в том, что оно объясняет, почему при умножении на 0 всегда получается 0 и почему «минус на минус дает плюс». Оба эти свойства выполняются, если верны четыре аксиомы: ассоциативность сложения, дистрибутивность, наличие нейтрального элемента и обратного элемента по сложению.

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

Пример 9. Пусть К – кольцо, M_n(K) – множество квадратных матриц размера n×n с коэффициентами из кольца К. Относительно обычных операций сложения и умножения матриц M_n(K) является кольцом.

Отметим, что в отличие от кольца многочленов К[x] кольцо M_n(K) не наследует коммутативность от кольца коэффициентов К.

Упражнение. Доказать, что при n>1 кольцо M_n(K) всегда некоммутативное.

Пример 10. Рассмотрим множество остатков (вычетов)

Z_n={0,1,2,…, n—1} от деления на натуральное число n. Введем на нем операции сложения и умножения

,

где a+b и ab обозначают обычные сложение и умножение целых чисел.

Относительно введенных операций множество Z_n является коммутативным кольцом с единицей.

Самое маленькое кольцо, и самое любимое программистами, это кольцо Z₂ = {0,1} вычетов по модулю 2. В дальнейшем мы не будем использовать обозначения , , а пользоваться привычной плюсом и точкой.

Предупреждение. Нередко считают, что если n>m, то кольцо Z_n содержит кольцо Z_m . Это вредное заблуждение. Конечно, внешне кольцо Z₅={0,1,2,3,4} выглядит как подмножество кольца Z₈={0,1,2,3,4,5,6,7}. Однако, в первом кольце 3·3=4, 3+3=1, а во втором 3·3=1, 3+3=6. Элемент 3 в первом кольцо отличается от элемента 3 во втором, как Вася Петров от Васи Иванова. Это омонимы – одинаково звучащие слова с разным смыслом.

И завершим наше короткое алгебраическое введение определением поля.

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

Пример 11. Множество Q рациональных чисел с обычными операциями сложения и умножения является полем.

Множество R действительных чисел с обычными операциями сложения и умножения является полем.

Кольцо вычетов Z_p , где p – любое простое число, является полем. (Это мы докажем позже).

Упражнение.

Проверить, что кольцо многочленов K[x] не является полем. (Подсказка. Какой многочлен является обратным к многочлену х² по умножению?).

Проверить, что кольцо матриц M_n(K) при n>1 не является полем.

1.2. Делимость в кольцах.

Неформально говоря, в полугруппе можно только умножать (или прибавлять). В группе можно умножать и делить (или прибавлять и вычитать). В кольце можно прибавлять, вычитать и умножать. В поле можно прибавлять и вычитать, умножать и делить.

Когда в поле рациональных чисел мы говорим, что «делим число 2 на число 3», то это является вольным изложением более правильного выражения «умножаем число 2 на число обратное по умножению к числу 3». Почему нельзя делить на 0? Поскольку, 0a=0, то 0 не имеет обратного по умножению и поэтому делить не на что.

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

Определение. Элемент а кольца К делит элемент b кольца K, если существует элемент c кольца K, такой что b=ac. Точнее делит слева, т.к. кольцо может быть некоммутативным. Если b=ca, то а делит элемент b справа.

Обратим внимание, что в этом определении наличие обратного элемента у элемента «а » не предполагается.

Поскольку 0a=0, то по этому определению получается, что 0 делит 0. Получается лингвистическое противоречие. Ноль делит ноль, но ноль на ноль не делится!

В дальнейшем мы будем иметь дело только с коммутативными кольцами, то правую и левую делимость мы различать не будем. Если элемент a делит элемент b, то это обозначается a/b.

Свойства делимости. Пусть К – кольцо, a,b,c – его элементы.

1. Если a/b, a/c, то a/(b+c), a/(b-c).

2. Если a/b, то для любого с из К a/(bc).

3. Если a/b, b/c, то a/c.

4. Если , то

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

1. По определению делимости найдутся b₁, c₁ , принадлежащие К, такие, что b=ab₁, c=ac₁, поэтому , следовательно, элемент а делит элемент . Кроме определения делимости здесь использовалась дистрибутивность.

2. Так как b=ab₁, то bc=(ab₁)c=a(b₁c) в силу ассоциативности умножения.

3. Если b=ab₁, c=bc₁, то c=bc₁=(ab₁)с₁=a(b₁с₁) опять использовалась ассоциативность умножения.

4. Последнее свойство следует из свойств 1 и 2.

□

Третье свойство обычно называют транзитивностью. Кроме транзитивности среди свойств бинарных отношений, а делимость – это бинарное отношение, популярны рефлексивность и симметричность.

Чтобы выяснить, когда эти свойства имеют место, нам потребуется еще ряд определений.

Определение. Элемент a кольца К называется обратимым (или единицей), если существует элемент b, принадлежащий кольцу К, такой что, ab=1, где 1 – нейтральный элемент по умножению.

Теорема.

Множество К^* обратимых элементов кольца К является группой относительно операции умножения.

Доказательство очевидно. □

Определение. Элемент a≠0 кольца К называется делителем нуля, если существует элемент b≠0 кольца К, такой, что ab=0.

Упражнение. Проверить, что кольца вычетов по составному модулю и кольца матриц M_n(K), при n >1, имеют делители нуля.

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

Пример 1.

Рассмотрим кольцо Z₈ и два уравнения с коэффициентами в этом кольце: 4x=0 и x²+x+1=0. Как легко проверить первое уравнение имеет четыре решения – 0, 2, 4, 6, а второе ни одного. □

Определение. Элементы a и b кольца К называются ассоциированными, если a\b и b\a.

Исследуем подробнее ассоциированные элементы. Если a\b и b\a, то одновременно выполняются два равенства b=ab₁, a=ba₁. Следовательно, . Таким образом, b(1—a₁b₁) = 0, и a(1—b₁a₁)=0. Если кольцо К не имеет делителей нуля, то получается, что

a₁b₁=1. То есть ассоциированные элементы отличаются друг от друга на обратимый элемент. Например, в кольце целых чисел группа обратимых элементов состоит из двух элементов Z^*={1, -1}, поэтому ассоциированными элементами будут, например, 3 и -3, 5 и -5.

Фундаментальную роль в алгебре и теории чисел, а также в криптографии, играют простые элементы кольца. В случае кольца целых чисел – простые числа.

Определение. Элемент p кольца К без делителей нуля называется простым, если он делится только на обратимые элементы и на ассоциированные с ним.

Если ограничится только натуральными числами, то определение простого элемента будет звучать так: «простой элемент делится только на себя и на единицу», поскольку среди натуральных чисел обратимым элементом является только 1.

У колец без делителей нуля есть одного замечательное свойство.

Основное свойство колец без делителей нуля.

Пусть К – кольцо без делителей нуля и a≠0, тогда из равенства ab=ac следует, что b=c.

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

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

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