АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Алгебраические структуры

Читайте также:
  1. Абсолютное изменение валового сбора под влиянием изменения структуры посевных площадей рассчитывается с помощью индексов
  2. Абсолютное изменение средней заработной платы под влиянием изменения структуры работников на предприятиях определяется по формуле
  3. Абсолютное изменение средней урожайности под влиянием изменения структуры посевных площадей рассчитывается с помощью индексов
  4. Алгебраические циклы
  5. Анализ объема структуры и качества строительно-монтажных работ
  6. Анализ состава, размера и структуры земельных угодий
  7. Анализ состава, размера и структуры земельных угодий
  8. Анализ состава, структуры и динамики основных средств
  9. Анализ структуры и динамики изменений баланса
  10. Анализ структуры почвы
  11. Анализ структуры рисунка.

Множество элементов G с заданной на нем некоторой бинарной операцией "∙" называется группоидом, если для любых двух его элементов а, b однозначно определён элемент
c=а
b, который также лежит в G и считается результатом выполнения этой бинарной операции над этими элементами а и b. Обычно используется обозначение (G,∙).

Множество элементов G с заданной на нем бинарной операцией "∙" называется группой, если выполнены три условия:

  1. Операция "∙" ассоциативна, то есть (аb) ∙ с = а ∙ (bс), для любых элементов группы G.
  2. Существует элемент е из G, такой, что для любого g из G выполняются равенства
    еg = gе = g,
  3. Для любого g из G существует элемент g ' из G со свойством gg ' = g ' ∙ g = е.

Обычно используется обозначение (G,∙).

Элемент е из G называют нейтральным элементом группы, а элемент g ' – обратным элементом к g. Для обратного элемента g ' обычно используется обозначение g ' = g -1.

Следует отметить, что в группе G нейтральный элемент е и элемент g -1, обратный к элементу g, определены однозначно.

С точки зрения решения уравнений, основное свойство группы состоит в том, что в ней однозначно разрешимы уравнения вида

aх = b,
ya = b

при любых a, bG. Упражнение: найдите a и b.

Повторим, что группоидом (G,∙) называется любое множество G с любой определённой на ней бинарной операцией ∙.

Если при всех a, b и с эти уравнения

aх = b,
ya = b

однозначно разрешимы относительно х и у, то (G,∙) называется квазигруппой. Для квазигруппы не обязательно выполняются условия 1)-3) из определения группы. Вместе с тем ассоциативная квазигруппа всегда является группой. Ассоциативность – это выполнение тождества 1).

Упражнение: обоснуйте это.

Решение уравнения ya = b обычно обозначается как y=b / a.

Решение уравнения aх = b обычно обозначается как x=a \ b.

Это правое и левое деление в квазигруппе. Если она коммутативна, т.е. выполняется тождество uv = vu, то правое и левое деления совпадают, и тогда используется для обозначения операции деления обычная дробная черта.

Квазигруппы находят криптографические применения в эндоморфных совершенных шифрах с минимальным числом ключей. Шифр называется эндоморфным, если алфавиты шифрвеличин открытых X и закрытых Y текстов совпадают. Для таких шифров количество ключей минимально, если мощность множества ключей K совпадает с мощностью множеств шифрвеличин открытых X и закрытых Y текстов. Обычно при этом полагают K=X=Y. В таком случае пусть (G,∙) – квазигруппа на множестве G= K=X=Y.
Если x ∈X, y ∈Y, k ∈K, то уравнением зашифрования будет уравнение y= x ∙ k, уравнением расшифрования будет уравнение x=y / k, уравнением дешифрования (уравнением определения ключа) будет уравнение k= x \ y. Сообщение (открытый текст) из n шифрвеличин (слово из n букв) x 1 … xn на ключевом потоке (гамме шифра) k 1 , , kn криптографически преобразуется в сообщение (закрытый текст) из n шифрвеличин (слово из n букв) y 1 … yn посредством последовательности уравнений зашифрования ym= xm ∙ km,
где m= 1 ,…n.

Операция "∙" называется коммутативной, если для любых двух элементов а и b из G выполнено равенство аb = bа. В этом случае группа G называется коммутативной или абелевой. Абелевы группы находят применение в асимметричных алгоритмах шифрования, в том числе с использованием задач дискретного логарифмирования в конечных полях и на эллиптических кривых.

Примером абелевой группы является множество комплексных корней степени п из 1 с операцией умножения корней как комплексных чисел – циклическая группа (Z n,+), т.е. множество вычетов по модулю п с операцией сложения по модулю п.

Множество R с двумя бинарными ассоциативными операциями сложения "+" и умножения "∙" называется кольцом, если выполнены следующие условия:

  • - множество R с бинарной операцией сложения "+" является абелевой группой,
  • - операция "∙" удовлетворяет условию дистрибутивности относительно операции "+", т.е. (а + b) ∙ с = ас + bс и а ∙ (b + с) = аb + aс.

Если операция "∙" коммутативна, то кольцо называется коммутативным.

Если операция "∙" ассоциативна, то кольцо называется ассоциативным.

 

Примером кольца является множество Zn, образующее полную систему вычетов целых чисел по модулю n с операциями сложения и умножения по модулю n, причем это кольцо является коммутативным и ассоциативным.

Нейтральный элемент кольца относительно операции "+" называют нулем кольца и обозначают через 0. При умножении на 0 любого элемента кольца будет получаться 0.

Можно отдельно рассмотреть множество всех ненулевых элементов кольца с операцией умножения "∙". Для этого множества можно ввести понятия нейтрального и обратного элементов относительно операции умножения "∙". Нейтральный элемент кольца относительно операции "∙" называют единицей кольца и обозначают через 1.

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

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

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


1 | 2 | 3 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)