SEMIGROUPS OF BINARY OPERATIONS AND MAGMA-BASED CRYPTOGRAPHY

Full Text

1. Предварительные сведения

   В статье рассматриваются бинарные операции как частный случай 3-местных отношений, заданных на множестве. Возможны два подхода к исследованию и конструктивной реализации операций– функцио- нальный и объектный. В первом случае с операцией связывают алгоритм построения результирующего значения операции на наборе значений ее аргументов. При этом в момент времени начала исполне- ния алгоритма результат операции не определен и недоступен для использования. Во втором случае операцию задают при помощи графика или таблиц Кэли, указывая связи между наборами значений аргументов и результатом, причем в любой момент времени результат операции определен, а доступ к нему определяет «ключ»– наборы значений аргументов. Сложность реализации функционального под- хода измеряют числом элементарных операций, исполняемых процессором при построении результата.

   Цветов В.П. Полугруппы бинарных операций и криптосистемы на группоидах

   24Tsvetov V.P. Semigroups of binary operations and magma-based cryptography

    

   Сложность реализации объектного — числом элементарных ячеек памяти, которые требуются для хра- нения связей между аргументами и результатом. Эти меры в некотором смысле условны, т. к. для хранения инструкций, реализующих алгоритм, требуется определенный объем памяти, а для доступа к хранимому результату по набору аргументов необходим набор инструкций, осуществляющих этот до- ступ. Однако в сравнении с основными затратами на реализацию того или иного представления они считаются пренебрежимо малыми.

   Функциональный и объектный подходы не являются взаимоисключающими уже хотя бы потому, что таблица Кэли «прошивается» в алгоритм, исполняемый процессором, в виде базовой «таблицы умноже- ния», а для построения графика операции часто используются алгоритмы построения результата.

   В дальнейшем изложении мы будем придерживаться объектного подхода, т. к. он позволяет при рассмотрении операций как объектов определять «операции над операциями» и использовать уже из- вестные алгебраические методы при изучении самих операций и порождаемых ими алгебр.

   В качестве прикладного примера мы рассмотрим направление асимметричной криптографии, связан- ное с созданием и реализацией протоколов безопасного распространения ключей шифрования в недове- ренной среде. Оно опирается на идеи теории односторонних функций с секретом и существенно использу- ет вычислительную сложность применяемых алгоритмов. Первой опубликованной и наиболее известной в этой области является работа У. Диффи и М. Хеллмана [1], в которой описывался протокол откры- того распределения ключей. Статья была написана под влиянием идей Р. Меркла о распространении открытого ключа [2], а сам протокол получил название протокола Диффи — Хелмана DH (Diffie — Hellman) или Диффи — Хелмана — Меркла DHM (Diffie — Hellman — Merkle).

   Протокол DHM формулировался в терминах мультипликативных групп конечных полей GF (p). Од-

   ним из сновных условий, обеспечивающих криптостойкость протокола DHM, является ассоциативность

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

   счисления

   r r−1

   gn = g2 dr +2

   dr−1 ...d0 = g2(...2(2(2dr +dr−1 )+dr−1 )...)+d0 .

   i−1

    

   Действительно, полагая a0 = g и выполняя последовательно r вычислений ai = a2

   gdi при i ∈ 1..r, на

   завершающем шаге получим gn = ar

   −1. Нетрудно понять, что данный алгоритм имеет логарифмическую

   сложность O(log(n)) групповых операций. Вместе с тем известные к настоящему времени алгоритмы

   логарифмирования, т. е. нахождения n ∈ N из уравнения gn = a при изветных g и a, имеют корневую сложность O(√n).

   Не менее известный протокол RSA (Rivest — Shamir — Adleman), опирается на схему Шамира [3], использующую интерполяционные полиномы Лагранжа в конечных полях для многостороннего разде- ления секрета при генерации ключей шифрования. В данном случае от алгебраических операций сло- жения и умножения, в терминах которых формулируется эта схема, требуется выполнение всех свойств операций поля.

   Аналогичные требования к свойствам алгебраических операций предъявляет система HFE (Hidden Field Equations) [4; 5], пригодная для применения в рамках так называемой «постквантовой криптогра- фии» [6; 7], или эллиптические и гиперэллиптические криптографические системы [8; 9].

   Криптографические системы, основанные на целочисленных векторных решетках, в частности схема GGH (Goldreich–Goldwasser–Halevi), помимо полевых свойств операций используют евклидову метрику многомерных вещественных линейных векторных пространств [10; 11].

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

   С другой стороны, тот же арсенал алгоритмических приемов может применяться для атак на крипто- графические протоколы с целью их дискредитации. Поэтому в последнее время исследователи все чаще стали проявлять интерес к более «бедным» алгебраическим системам, таким, например, как полугруп- пы и полукольца [12; 13]. Этим же объясняется возрождение интереса к криптографии, основанной на

   квазигруппах [14–18], а также исследования в области n-арных квазигрупп и полугрупп [19].

   Как было отмечено выше, одним из условий существования криптостойкого «доквантового» асиммет- ричного протокола является свойство ассоциативности его базовой бинарной операции. Отказ от этого свойства является первым шагом на пути от полугрупп – алгебр с ассоциативной бинарной операци- ей, к группоидам – алгебрам, на бинарную операцию которых не накладывается никаких ограничений. В англоязычной литературе группоид часто называют магмой (magma), подчеркивая тем самым пер- вичность и неструктурированность этого класса алгебр, из которого в результате дополнительных огра-

   Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 1. С. 23–51

   Vestnik of Samara University. Natural Science Series. 2020, vol. 26, no. 1, pp. 23–51 25

    

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

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

   i=1

    

   Будем придерживаться следующей терминологии. Обозначим символом ⊗n

   Ui декартово произве-

   дение n множеств Ui. Обозначим символом 2U булеан над множеством U . Мощность множества U будем

   i=1

    

   обозначать символом |U |. Множество R ⊆ ⊗n

   Ui будем называть n-местным отношением на множе-

   ствах Ui. В тех случаях, когда все множества Ui совпадают, R ⊆ Un называют n-местным отношением на множестве U .

   В дальнейшем нас в основном будут интересовать 3-местные отношения R ⊆ U 3. Мы будем рассматри- вать бинарные операции на U как 3-местные отношения со специальным свойством функциональности.

   Такой подход позволит определить алгебры, сигнатура которых обобщает сигнатуру хорошо известной

   2

   алгебры 2-местных (бинарных) отношений ⟨2U

   , (∪, ∩, −, ∅, U 2, ◦, −1, IU )⟩. Хотя теория отношений восхо-

   дит к теории множеств, теории порядковых типов [20; 21], математической логике и основаниям мате-

   матики [22; 23], она имеет обширные приложения в дискретной математике [24; 25], теории графов [26], теоретической информатике и кибернетике [27].

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

    

   1. Общие сведения об алгебре 2-местных отношений

      2-местные отношения R ∈ 2U×V принято называть отношениями из множества U в множество V . Если U = V , 2-местные отношения R ∈ 2U×U принято называть отношениями на множестве U . Хорошо

      i=1

       

      известно, что |2U | = 2|U| и | ⊗n

      i=1

       

      Ui| = ∏n

      |Ui|.

       

      Определение 1.1. Обратным к 2-местному отношению R ∈ 2U×V называется 2-местное отношение

      R−1 ∈ 2V ×U , определяемое правилом

      R−1 = {(v, u) | u ∈ U ∧ v ∈ V ∧ (u, v) ∈ R}.

      Определение 1.2. Произведением (левой композицией) 2-местных отношений R1 ∈ 2U×V и R2 ∈

      ∈ 2V ×W называется 2-местное отношение R1 • R2 ∈ 2U×W , определяемое правилом

      R1 • R2 = {(u, w) | u ∈ U ∧ w ∈ W ∧ ∃v0 ∈ V (u, v0) ∈ R1 ∧ (v0, w) ∈ R2}.

      Суперпозицией (правой композицией) 2-местных отношений R1 ∈ 2U×V и R2 ∈ 2V ×W называется 2-местное отношение R2 ◦ R1 ∈ 2U×W , определяемое правилом

      R2 ◦ R1 = R1 • R2 = (R−1 • R−1)−1.

      2 1

       

      Определения операций произведения и суперпозиции симметричны и одинаково часто встречаются в литературе. Использование той или иной операции зависит от предпочтений авторов. Операция • более естественна для теории бинарных отношений и теории графов, а операция ◦ согласуется с операцией композиции функций. Мы будем в основном пользоваться операцией произведения. Все последующие результаты могут быть легко переформулированы в терминах суперпозиции.

      Определение 1.3. Тождественным 2-местным отношением на множестве U называется 2-местное

      2

      отношение IU ∈ 2U

      , определяемое правилом

      IU = {(u, u) | u ∈ U }.

      U

       

      Вполне понятно, что I−1 = IU • IU = IU ◦ IU = IU .

      Определение 1.4. Областью определения 2-местного отношения R ∈ 2U×V называется множество

      DR = {u | u ∈ U ∧ ∃v0 ∈ V (u, v0) ∈ R} ⊆ U.

       

      Определение 1.5. Областью значений 2-местного отношения R ∈ 2U×V называется множество

      ER = {v | v ∈ V ∧ ∃u0 ∈ U (u0, v) ∈ R} ⊆ V.

      Цветов В.П. Полугруппы бинарных операций и криптосистемы на группоидах

      26Tsvetov V.P. Semigroups of binary operations and magma-based cryptography

       

      Вполне понятно, что DR = ER−1 и ER = DR−1 .

       

      Утверждение 1.1. Помимо свойств операций булевой алгебры ⟨2U×V , (∪, ∩, −, ∅, U ×V )⟩ справедливы следующие свойства операций •, −1 для произвольных 2-местных отношений R1, R˜1 ∈ 2U×V , R2, R˜2 ∈

      ∈ 2V ×W , R3 ∈ 2W ×Q

      R1. R1 • (R2 • R3) = (R1 • R2) • R3 — ассоциативность операции •;

      R2. R1 • (R2 ∪ R˜2) = (R1 • R2) ∪ (R1 • R˜2) — дистрибутивность операции • относительно операции ∪; R3. R1 • (R2 ∩ R˜2) ⊆ (R1 • R2) ∩ (R1 • R˜2) — полудистрибутивность операции • относительно операции ∩; R4. R1 ⊆ R˜1 ∧ R2 ⊆ R˜2 −→ R1 • R2 ⊆ R˜1 • R˜2 — монотонность операции •;

      R5. IU • R1 = R1 = R1 • IV — свойства нейтральных по операции •;

      1

       

      R6. (R−1)−1 = R1 — инволютивность операции −1;

      R7. (R1 • R2)−1 = R−1 • R−1

      • антидистрибутивность операции −1 относительно операции •;

        2 1

        R8. (R1 ∪ R˜1)−1 = R−1 ∪ R˜−1

      • дистрибутивность операции −1 относительно операции ∪;

        1 1

        R9. (R1 ∩ R˜1)−1 = R−1 ∩ R˜−1

      • дистрибутивность операции −1 относительно операции ∪;

        1 1

        R10. R1 ⊆ R˜1 −→ R−1 ⊆ R˜−1

      • монотонность операции −1;

      1

      R 1

       

      R11. ID ⊆ R1 • R−1

      1

      = ker(R1) — свойство ядра R1;

      1

       

      R12. IER ⊆ R−

      • R1 = ker(R−1

      ) — свойство ядра R−1.

      1 1 1

      R13. DR1 •R2 ⊆ DR1 — свойство области определения R1 • R2.

      R14. ER1 •R2 ⊆ ER2 — свойство области значений R1 • R2.

       

      Определение 1.6. Левым сужением 2-местного отношения R ∈ 2U×V на множество U0 ⊂ U назы-

      U′×V

      вается 2-местное отношение RU0 ∈ 2

      , определяемое правилом

      RU0 = {(u, v) | u ∈ U0 ∧ v ∈ V ∧ (u, v) ∈ R}.

       

      Определение 1.7. Правым сужением 2-местного отношения R ∈ 2U×V на множество V0 ⊂ V назы- вается 2-местное отношение RV0 ∈ 2U×V0 , определяемое правилом

      RV0 = {(u, v) | u ∈ U ∧ v ∈ V0 ∧ (u, v) ∈ R}.

      0

       

      В тех случаях, когда это не приводит к недоразумениям, будем сохранять за сужениями RU ∈ 2U0 ×V

      и RV0 ∈ 2U×V0 прежнее обозначение R.

      Часто вместо записи (u, v) ∈ R используют инфиксную запись uRv. В терминах операций над 2-мест-

      ными отношениями удобно дать следующие определения.

      Определение 1.8. Говорят, что 2-местное отношение R ∈ 2U×V тотально (слева), если

      DR = U,

      или, что то же самое,

      IU ⊆ R • R−1.

       

      Определение 1.9. Говорят, что 2-местное отношение R ∈ 2U×V сюръективно (тотально справа), если

       

      или, что то же самое,

      ER = V,

      IV ⊆ R−1 • R.

      Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 1. С. 23–51

      Vestnik of Samara University. Natural Science Series. 2020, vol. 26, no. 1, pp. 23–51 27

       

      С учетом определения 1.1 можно утверждать, что 2-местное отношение сюръективно тогда и только тогда, когда обратное к нему тотально, и наоборот.

      Определение 1.10. Говорят, что 2-местное отношение R ∈ 2U×V функционально (функция из U

      в V ), если

       

      или, что то же самое,

      ∀u ∈ U ∀v1, v2 ∈ V (u, v1) ∈ R ∧ (u, v2) ∈ R −→ v1 = v2,

      R−1 • R ⊆ IV .

       

      В подобных случаях принята запись R : U → V , а вместо записей (u, v) ∈ R или uRv используют запись v = R(u), при этом u называют аргументом функции, а v — значением функции на аргументе. Множество тотальных функций из U в V принято обозначать V U . Хорошо известно, что |V U | = |V ||U|. Функция из U в U называется функцией на U . Тотальная функция на U называется преобразованием U . Непосредственно из определений следует, что если R1 : U → V и R2 : V → W , то R1 • R2 : U → W и

      R1 • R2(u) = R2(R1(u)) = R2 ◦ R1(u). В силу того что I−1 • IU = IU • I−1 = IU • IU = IU , тождественное

      U

       

      отношение IU — преобразование U , причем I−1(u) =

      U U

      IU (u) = u.

       

      Определение 1.11. Говорят, что 2-местное отношение R ∈ 2U×V инъективно, если

      ∀v ∈ V ∀u1, u2 ∈ U (u1, v) ∈ R ∧ (u2, v) ∈ R −→ u1 = u2,

      или, что то же самое,

      R • R−1 ⊆ IU .

       

      С учетом определения 1.1 можно утверждать, что 2-местное отношение инъективно тогда и только

      тогда, когда обратное к нему функционально, и наоборот. Таким образом, обратное к функциональному отношению R ∈ 2U×V функционально тогда и только тогда, когда R инъективно.

      Инъективные функции принято называть инъекциями, а сюръективные — сюръекциями.

       

      Определение 1.12. Говорят, что 2-местное отношение R ∈ 2U×V – тотальная биекция, если R функ- ционально, инъективно, сюръективно и тотально, или, что то же самое,

      R • R−1 = IU ∧ R−1 • R = IV .

       

      В силу симметричности определения относительно R и R−1, а также инволютивности операции −1, можно утверждать, что R — тотальная биекция тогда и только тогда, когда R−1 — тотальная биекция. Непосредственно из определений следует, что R • R−1(u) = R−1(R(u)) = IU (u) = u и R−1 • R(v) =

      = R(R−1(v)) = IV (v) = v для произвольных элементов u ∈ U и v ∈ V . Если обозначить v = R(u) ∈ V , то R−1(R(u)) = R−1(v) = IU (u) = u ∈ U . Таким образом, для тотальных биекций v = R(u) тогда и только тогда, когда u = R−1(v).

      В силу свойств сюръективности и инъективности для каждого элемента v ∈ V будет существовать единственный элемент u ∈ U такой, что v = R(u), а в силу свойств тотальности и функциональности для каждого элемента u ∈ U будет существовать единственный элемент v ∈ V такой, что v = R−1(u). Тотальная биекция на U называется подстановкой множества U . Множество подстановок будем обо- значать BU . Вполне понятно, что тождественное отношение IU — подстановка множества U , которая

      называется тождественной подстановкой.

      В дальнейшем будем обозначать функции символами F, G, Φ, Ψ, f, g, ϕ, ψ.

      Утверждение 1.2. Пусть F1 : U → V , F2 : V → W , тогда

      F1. F1 • F2 ∈ 2U×W — функция;

      F2. Если F1, F2 — тотальны, то F1 • F2 : U → W — тотальнa;

      F3. Если F1, F2 — сюръекции, то F1 • F2 — сюръекция;

      F4. Если F1, F2 — инъекции, то F1 • F2 — инъекция;

      F5. Если F1, F2 — тотальные биекции, то F1 • F2 — тотальнaя биекция.

      Цветов В.П. Полугруппы бинарных операций и криптосистемы на группоидах

      28Tsvetov V.P. Semigroups of binary operations and magma-based cryptography

       

      Утверждение 1.3. Пусть F ∈ UU — инъекция (тотальная), и множество U конечно, т. е. состоит из конечного числа элементов, тогда F — подстановка.

       

      Определение 1.13. Функцией FR, индуцированной 2-местным отношением R ∈ 2U×V , называется функция из 2U в 2V , определяемая правилом

      FR(U0) = {v | v ∈ V ∧ u ∈ U0 ⊆ U ∧ (u, v) ∈ R} ⊆ V.

      Значения индуцированной функции и само 2-местное отношение R полностью определяются ее осто-

      вом (остовной функцией), т. е. значениями этой функции на одноэлементных подмножествах множе- ства U

       

      исходя из очевидных равенств,

      FR({u}) = {v | v ∈ V ⊆ U (u, v) ∈ R},

      FR(U0) = ∪

      u∈U0

      FR({u}),

      R = ∪ FR({u}) × {u}.

      u∈U

      Обычно отождествляют элемент u и одноэлементное подмножество {u}, понимая под остовной функ-

      цией функцию F 0 : U → 2V , значения которой определены правилом F 0 (u) = FR({u}).

      R R

       

      2

       

      Определение 1.14. Говорят, что 2-местное отношение R ∈ 2U

      ∀u ∈ U (u, u) ∈ R,

      рефлексивно, если

      или, что то же самое,

      IU ⊆ R.

       

      2

       

      Определение 1.15. Говорят, что 2-местное отношение R ∈ 2U

      симметрично, если

       

      или, что то же самое,

      ∀u1, u2 ∈ U (u1, u2) ∈ R −→ (u2, u1) ∈ R,

      R = R−1.

       

      2

       

      Определение 1.16. Говорят, что 2-местное отношение R ∈ 2U

      транзитивно, если

       

      или, что то же самое,

      ∀u1, u2, u3 ∈ U (u1, u2) ∈ R ∧ (u2, u3) ∈ R −→ (u1, u3) ∈ R,

      R • R ⊆ R.

       

      2

       

      Определение 1.17. 2-местное отношение R ∈ 2U

      рефлексивно, симметрично и транзитивно.

      называют отношением эквивалентности, если оно

       

   2. Общие сведения об алгебрах с бинарными операциями

   Напомним, что n-арной операцией на множестве U называется тотальная функция ϕ : Un → U . Алгеброй называется множество U с определенным на нем конечным набором операций ϕi : Uni → U . Множество U называют носителем алгебры, набор операций (ϕ1, . . . , ϕm) — сигнатурой алгебры, а набор арностей операций (n1, . . . , nm) — типом алгебры. Сигнатуру алгебры принято обозначать Σ, а сами алгебры A = ⟨U, Σ⟩. Для того чтобы указать, что операция ϕ входит в сигнатуру Σ, будем записывать ϕ ∈ Σ. Алгебра называется конечной, если множество U состоит из конечного числа элементов.

   Говорят, что подмножество U0 ⊆ U носителя алгебры A = ⟨U, Σ⟩ типа (n1, . . . , nm) замкнуто отно- сительно сигнатуры, если для любой операции ϕi ∈ Σ и любого набора ее аргументов u1, . . . , uni ∈ U0 следует, что ϕ1(u1, . . . , uni ) ∈ U0. В таких случаях также говорят, что алгебра A0 = ⟨U0, Σ0⟩ является подалгеброй алгебры A = ⟨U, Σ⟩. Здесь сигнатура Σ0 образована сужениями операций ϕi ∈ Σ на множе- ства U0ni . Обычно за сигнатурой Σ0 и ее операциями сохраняют прежние обозначения и записывают

   A0 ⊆ A.

   Тотальная функция F : U → V называется гомоморфизмом алгебр A1 = ⟨U, Σ1⟩ и A2 = ⟨V, Σ2⟩

   одного и того же типа (n1, . . . , nm), если для любых пар операций ϕi ∈ Σ1, ψi ∈ Σ2 и любого набора

   Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 1. С. 23–51

   Vestnik of Samara University. Natural Science Series. 2020, vol. 26, no. 1, pp. 23–51 29

    

   аргументов u1, . . . , uni ∈ U выполняются равенства F (ϕi(u1, . . . , uni )) = ψi(F (u1), . . . , F (uni )). В таких случаях говорят, что алгебры A1 и A2 находятся в отношении гомоморфизма или гомоморфны.

   2

    

   2

    

   Биективный гомоморфизм называют изоморфизмом, а алгебры алгебры A1 и A2 — изоморфными, при этом записывают A1 ∼ A2. Отношение изоморфизма однотипных алгебр является отношением эк- вивалентности.

   Понятно, что алгебры ⟨2U

   , (∪, ∩, −, ∅, U 2, •, −1, I)⟩ и ⟨2U

   , (∪, ∩, −, ∅, U 2, ◦, −1, I)⟩ изоморфны, а изомор-

   физм устанавливает функция F (R) = R−1.

   Инъективный гомоморфизм называют мономорфизмом, при этом говорят, что алгебра A1 = ⟨U, Σ1⟩

   изоморфно вложима в алгебру A2 = ⟨V, Σ2⟩, и записывают, A1 ,:. A2. Если F : U → V — мономорфизм,

   то ˜

   = ⟨E

   , Σ ⟩ — подалгебра алгебры A , а F : U → E

   — изоморфизм алгебр A

   и ˜ .

   A2 F 2

   2 F 1 A2

   Вполне понятно, что любая n-арная операция на U , как тотальная функция ϕ : Un 1→ U , явля- ется n + 1-местным отношением на U . В этом случае ϕ ⊆ Un × U = Un+1, а условия тотальности и

   функциональности могут быть записаны в следующей форме:

   ∀u1, . . . , un ∈ U ∃u0 ∈ U (u1, . . . , un, u0) ∈ ϕ,

   ∀u1, . . . , un, un+1, u˜n+1 ∈ U (u1, . . . , un, un+1) ∈ ϕ ∧ (u1, . . . , un, u˜n+1) ∈ ϕ −→ un+1 = u˜n+1.

    

   Простейший класс алгебр образуют алгебры с бинарными операциями. Обычно вместо префиксной записи результата операции ϕ(u1, u2) используют инфиксную запись u1ϕu2. Бинарные операции принято обозначать символами ·, +, −, ∗, ÷, ⋆, ◦, •, ⊙, ⊕, и т. п.

   Операции ∗ и ÷ называются взаимно обратными слева (справа), если u3 = u1 ∗ u2 тогда и только тогда, когда u2 = u3 ÷ u1 (u1 = u3 ÷ u2), для произвольных элементов u1, u2, u3 ∈ U .

   Группоидом называется множество U с определенной на нем бинарной операцией ∗. Группоиды при- нято обозначать ⟨U, (∗)⟩.

   При изучении группоидов обычно пользуются мультипликативной терминологией, трактуя опера- цию ∗ как умножение. Реже используется аддитивная терминология, когда операция ∗ трактуется как сложение. Мы будем придерживаться в основном мультипликативной терминологии.

   Мощность носителя конечного группоида |U | называют его порядком. Порядок бесконечных группо-

   идов считается бесконечным.

   Если ⟨U, (∗)⟩– группоид, то определяют группоид ⟨2U , (∗)⟩, полагая U1 ∗ U2 = {u | u = u1 ∗ u2 ∧ u1 ∈

   ∈ U1 ∧ u2 ∈ U2}, для произвольных подмножеств U1, U2 ⊆ U . Если множество U1 = {u} (U2 = {u}) одноэлементное, то вместо {u} ∗ U2 (U1 ∗ {u}) записывают u ∗ U2 (U1 ∗ u). Если операция группоида

   ⟨U, (∗)⟩ ассоциативна, то и операция группоида ⟨2U , (∗)⟩ ассоциативна.

   Непустое подмножество U1 ⊆ U называют левым (правым) идеалом группоида ⟨U, (∗)⟩, если U ∗

   U1 ⊆ U1 (U1 ∗ U ⊆ U1). Подмножество, которое одновременно является и левым, и правым идеалом,

   называют двусторонним идеалом или просто идеалом. Группоид называется простым слева (справа), если U является его единственным левым (правым) идеалом. Аналогично дается определение простого идеала. Группоид является простым слева (справа) тогда и только тогда, когда U ∗ u = U (u ∗ U = U ), для произвольного элемента u ∈ U .

   Если ∅ ̸= U1 ⊆ U , то пересечение всех левых (правых) идеалов, содержащих U1, называют левым (правым) идеалом группоида, порожденным U1. Левый (правый) идеал, порожденный U1, равен U1∪

   ∪U ∗ U1 (U1 ∪ U1 ∗ U ). Идеал L(u) = {u} ∪ U ∗ u ({u} ∪ u ∗ U ) называют левым (правым) главным идеалом группоида, порожденным u. В случае полугрупп двусторонний главный идеал, порожденный u, имеет вид J (u) = {u} ∪ U ∗ u ∪ u ∗ U ∪ U ∗ u ∗ U .

   В группоиде ⟨U, (∗)⟩ определяется левая (правая) положительная степень элемента u ∈ U по опера-

   ции ∗, при этом полагают u1 = u1 = u, и un+1 = u ∗ un

   (un+1 = un ∗ u), для n ∈ N. Иными словами,

   l r l

   un

   l r r

   l = u ∗ (. . . ∗ (u ∗ (u ∗ u)) . . .),

   n

   un

    

   r = (. . . ((u ∗ u) ∗ u) ∗ . . .) ∗ u .

   n

   Если операция ∗ коммутативна, то un = un.

   l r

   n-кратную сумму n · ul (n · ur ).

   В случае аддитивной терминилогии степень элемента обозначают как

   Ul n l

   Определим

   0 = {u0l | u0 ∈ U ∧ n ∈ N}. Группоид ⟨U0, (∗)⟩ называется левым циклическим, порож-

   денным элементом u0.

   0

    

   Аналогично определяется правый циклический группоид ⟨Ur, (∗)⟩, порожденный элементом u0.

   Если в группоиде существует элемент u ∈ U , обладающий свойством u ∗ u = u, то он называется

   идемпотентом.

   Цветов В.П. Полугруппы бинарных операций и криптосистемы на группоидах

   30Tsvetov V.P. Semigroups of binary operations and magma-based cryptography

    

   Элемент el ∈ U (er ∈ U ) называется левым (правым) нейтральным по операции ∗ (левой (правой)

   единицей в мультипликативной терминологии и нулем в аддитивной терминологии), если для любого элемента u ∈ U выполняется равенство el ∗u = u (u∗er = u). Если в группоиде одновременно существуют

   левый и правый нейтральные элементы, то они совпадают, единственны, и в таком случае элемент

   e = el = er называется нейтральным (единицей). Вполне понятно, что левые (правые) нейтральные

   элементы являются идемпотентами. Группоиды с (левым, правым) нейтральным элементом принято обозначать (⟨U, (∗, el)⟩, ⟨U, (∗, er )⟩) ⟨U, (∗, e)⟩.

   Если в группоиде с левым (правым) нейтральным элементом для некоторого элемента u ∈ U суще-

   ствует элемент u′ ∈ U (u′ ∈ U ), для которого выполняется равенство u′ ∗ u = el (u ∗ u′ = er ), то u′

   (u′ )

   l r l

   r l r

   называется левым (правым) обратным по операции ∗ к элементу u.

   Элемент θl ∈ U (θr ∈ U ) называется левым (правым) поглощающим элементом по операции ∗ (ле- вым (правым) нулем в мультипликативной терминологии), если для любого элемента u ∈ U выполняется равенство θl ∗ u = θl (u ∗ θr = θr ). Если в группоиде одновременно существуют левый и правый погло- щающие элементы, то они совпадают, единственны, и в таком случае элемент θ = θl = θr называется

   поглощающим (нулем). Вполне понятно, что левые (правые) поглощающие элементы являются идемпо- тентами.

   Важный класс группоидов образуют группоиды с сокращением. Группоид ⟨U, (∗)⟩ называется груп- поидом с левым (правым) сокращением, если для любых элементов u1, u2, u3 ∈ U из того, что u3 ∗ u1 =

   = u3 ∗ u2 (u1 ∗ u3 = u2 ∗ u3), следует, что u1 = u2. Группоид с левым и правым сокращением называется

   группоидом с сокращением.

   Группоид ⟨U, (∗)⟩ называется группоидом с левым (правым) делением, если для любых элементов

   u1, u3 ∈ U (u2, u3 ∈ U ) существует такой элемент u0 ∈ U , что u1 ∗ u0 = u3 (u0 ∗ u2 = u3). Группоид с

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

   Группоид ⟨U, (∗)⟩ с левым (правым) сокращением и делением называется левой (правой) квазигруп-

   пой. Группоид, который является одновременно и левой, и правой квазигруппой, называют квазигруп-

   пой. Понятие квазигруппы непосредственно связано с понятием взаимно обратных операций. Квази- группа (левая, правая) с нейтральным элементом называется лупой (левой, правой).

   Если операция ∗ ассоциативна, то группоид называется полугруппой. В полугруппе ⟨U, (∗)⟩ левые и правые положительные степени элемента u ∈ U совпадают и обозначаются un+1 = un ∗ u = u ∗ un, для n ∈ N.

   Для полугрупп справедливы следующие правила положительных степеней:

   un ∗ um = un+m = um+n = um ∗ un, (1.1)

   (un)m = unm = umn = (um)n. (1.2)

   Правило (1.2) является прямым следствием правила (1.1).

   В случае полугрупп рассматривают циклические полугруппы ⟨U0, (∗)⟩, порожденные элементом u0.

   Любая циклическая полугруппа коммутативна.

   Если для некоторого элемента u0 ∈ U группоида ⟨U, (∗)⟩ выполняется правило левых (правых) по-

   ложительных степеней

   un m

   n+m

   m+n m n

   0l ∗ u0l = u0l = u0l = u0l ∗ u0l,

    

   (1.3)

   un m

   n+m

   m+n m n

   0r ∗ u0r = u0r = u0r = u0r ∗ u0r,

   то левый (правый) циклический группоид ⟨Ul, (∗)⟩ (⟨Ur, (∗)⟩), порожденный этим элементом, является

   0 0

   полугруппой, причем коммутативной. При этом правило

   (un )m = unm = umn = (um)n,

   0l 0l 0l 0l

   0l l

   (1.4)

   (un )m = unm = umn = (um )n

   0r 0r 0r 0r

   будет прямым следствием правила (1.3).

   0r r

   Так как в полугруппах левые и правые степени элемента совпадают, то выполнение одного из пра-

   0l

    

   вил степеней (1.3) повлечет выполнение равенства un

   0r

    

   = un , из которого будет следовать равенство

   полугрупп ⟨Ul, (∗)⟩ и ⟨Ur, (∗)⟩.

   0 0

    

   Полугруппу с нейтральным элементом называют моноидом. В моноидах определяют нулевую степень элементов u ∈ U , полагая u0 = e. В моноидах с сокращением не существует идемпотентов, отличных от нейтрального элемента. В моноидах правила степеней обобщаются на случай показателей n ∈ N0 =

   = N ∪ {0}.

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

   элемента u ∈ U , то они совпадают, единственны, и в таком случае элемент u′ = u′ = u′

   называется

   l r

   Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 1. С. 23–51

   Vestnik of Samara University. Natural Science Series. 2020, vol. 26, no. 1, pp. 23–51 31

   обратным по операции ∗ к элементу u, а сам элемент u называется обратимым. Обратный элемент,

   очевидно, существует для нейтрального и совпадает с ним. Идемпотент, отличный от нейтрального, не обратим. Если в полугруппе для элементов u1, u2 ∈ U существуют левые (правые) обратные (u1)′, (u2)′

   ((u1)′ , (u2)′ ), то существует и левый (правый) обратный к u1 ∗ u2, причем (u1 ∗ u2)′

   = (u2)′ ∗ (u1)′

   l l

   ((u1 ∗

   r r l l l

   u2)′ = (u2)′ ∗ (u1)′ ).

   r r r

   Моноид, в котором для каждого элемента существует обратный, называется группой. В группах не

   существует идемпотентов, отличных от нейтрального элемента. В группах определяют отрицательные степени элементов u ∈ U , полагая u−n = (u′)n, где n ∈ N.

   Правила неотрицательных степеней, справедливые для полугрупп, распространяются на целые по- казатели степеней в группах.

    

   2

    

   Утверждение 1.4. Алгебра 2-местных отношений ⟨2U

   (моноидом).

   , (•, IU )⟩ является полугруппой с единицей

    

    

   ⟨2U

   Утверждение 1.5. Алгебра преобразований ⟨UU , (•, IU )⟩ является подмоноидом моноида

   2

    

   , (•, IU )⟩.

   Утверждение 1.6. Алгебра подстановок ⟨BU , (•, IU )⟩ является подгруппой моноида ⟨UU , (•, IU )⟩. При

   этом для произвольного F ∈ BU выполняются равенства F • F−1 = F−1 • F = IU .

    

   2

    

   Несмотря на то что алгебры ⟨2U

   2

    

   , (∪, ∩, −, ∅, U 2, •, −1, IU )⟩ и ⟨2U

   , (∪, ∩, −, ∅, U 2, ◦, −1, IU )⟩ изоморфны,

   2

    

   моноиды ⟨UU , (•, IU )⟩ и ⟨UU , (◦, IU )⟩ в общем случае таковыми не являются. Дело в том, что множе-

   ство преобразований UU ⊂ 2U

   незамкнуто относительно операции −1, при помощи которой задается

   2

   изоморфизм F (R) = R−1, если |U | > 1. Однако множество подстановок BU ⊂ UU ⊂ 2U

   уже обладает

   свойством замкнутости, и, следовательно, группы ⟨BU , (•, IU )⟩ и ⟨BU , (◦, IU )⟩ изоморфны. Эти группы

   принято называть симметрическими группами множества U .

    

   Утверждение 1.7. Любая полугруппа (группоид) ⟨U, (⋆)⟩ изоморфно вложима в моноид (группоид с единицей) ⟨U ∪ {e}, (∗, e)⟩, где e ∈/ U , и ∀u1, u2 ∈ U u1 ∗ u2 = u1 ⋆ u2, и ∀u ∈ U ∪ {e} e ∗ u = u ∗ e = u.

   Утверждение 1.8. (Кэли) Любой моноид ⟨U, (∗, e)⟩ изоморфно вложим в моноид преобразований

   ⟨UU , (•, IU )⟩ с операцией произведения, причем мономорфизм этого вложения задает инъекция F∗ : U →

   → UU , где f∗ = F∗(u˜), и f∗(u) = u∗u˜. Аналогичное справедливо и для моноида ⟨UU , (◦, IU )⟩ с операцией

   u˜ u˜

   суперпозиции, где g∗ = G∗(u˜), и g∗ (u) = u˜ ∗ u.

   u˜ u˜

    

   Замечание 1.2. В теории квазигрупп преобразование u 1→ u ∗ u˜ называют правой трансляцией груп- поида ⟨U, (∗)⟩ относительно элемента u˜ ∈ U , а преобразование u 1→ u˜ ∗ u — левой трансляцией.

    

   Утверждение 1.9. Пусть ⟨U, (∗)⟩ — конечная полугруппа, ⟨U0, (∗)⟩ — циклическая полугруппа, по- рожденная произвольным элементом u0 ∈ U , тогда существует идемпотент u ∈ U0. Если ⟨U, (∗, e)⟩ — конечная группа, то такой идемпотент единственен и совпадает с нейтральным e, при этом ⟨U0, (∗, e)⟩ — циклическая подгруппа группы ⟨U, (∗, e)⟩, порожденная элементом u0 ∈ U .

    

   Замечание 1.1. Минимальную степень m ∈ N элемента u0 ∈ U моноида ⟨U, (∗, e)⟩, для которой

   um

   0 = e, называют порядком элемента u0 (в моноиде) и обозначают ord(u0) = m. Если такой степени

   0

    

   не существует, то ord(u0) = ∞. Если элемент u0 имеет конечный порядок m, то он обратим, и u′ =

   0

    

   = um−1

   0) = 1,

   причем

   e′ = e0

   = e.

   Вполне понятно, что (uk )′ = (u′)k для любого обратимого элемента u0 ∈ U и любого k ∈ N, т. е. любая

   степень обратимого элемента обратима.

   Если ⟨U0, (∗)⟩ — циклическая полугруппа, порожденная произвольным элементом u0 ∈ U из носителя моноида, и порядок элемента u0 в этом моноиде конечен, то ⟨U0, (∗, e)⟩ — конечная группа, и |U0| =

   = ord(u0).

   Обратное утверждение не верно. Например, если в носителе моноида имеется идемпотент u0, отлич- ный от нейтрального элемента e, то ord(u0) = ∞, но |U0| = 1.

   В конечных группах порядок любого элемента делит порядок группы.

   Цветов В.П. Полугруппы бинарных операций и криптосистемы на группоидах

   32Tsvetov V.P. Semigroups of binary operations and magma-based cryptography

    

   Утверждение 1.10. Пусть ⟨U, (∗, e)⟩ — конечный моноид, u0 ∈ U обратим, тогда циклическая по- лугруппа, порожденная элементом u0, является группой.

   Утверждение 1.11. Для любой полугруппы ⟨U, (∗)⟩ следующие условия эквивалентны:

   G1. ⟨U, (∗)⟩ — группа;

   G2. Для любых u2, u3 ∈ U каждое из уравнений u2 ∗ u = u3 и u ∗ u2 = u3 однозначно разрешимо относительно u;

   G3. Для любых u2, u3 ∈ U каждое из уравнений u2 ∗ u = u3 и u ∗ u2 = u3 разрешимо относительно u;

   G4. ⟨U, (∗)⟩ является простой слева и справа;

   G5. Существует левый (правый) нейтральный элемент el ∈ U (er ∈ U ), относительно которого для

   l

    

   каждого элемента u ∈ U существует левый (правый) обратный элемент u′

   r

    

   (u′ ), т. е. такой, что

   ul ∗ u = el (u ∗ ur = er ).

   ′ ′

    

   Утверждение 1.12. Любая группа является моноидом и полугруппой с сокращением. Обратное верно только для конечных моноидов. Примером моноида с сокращением, который не является группой,

   может служить мультипликативный моноид натуральных чисел ⟨N, (·, 1)⟩.

    

2. Основные результаты

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

    

   1. Полугруппы и алгебры 3-местных отношений

      В дальнейшем мы будем существенно использовать утверждение 1.8, которое позволяет изучать полу- группы ⟨U, (∗)⟩ в терминах тотальных функций с операцией произведения, т. е. в терминах подмоноидов моноида преобразований ⟨UU , (•, IU )⟩.

      Сначала докажем три простых, не претендующих на новизну, утверждения.

      Утверждение 2.1. Пусть R ∈ 2U×V , R′ ∈ 2V ×U , R • R′ = IU , и R′ • R = IV , тогда R′ = R−1.

      Доказательство. Так как DIU = U , то DR•R′ = DIU = U . В силу свойства R13 можем записать U = DR•R′ ⊆ DR ⊆ U . Откуда следует, что DR = U . Аналогично из свойства R14 следует, что ER′ = V . В силу предположения свойств R5, R12 и R4 можем записать R′ = IV • R′ ⊆ R−1 • R • R′ = R−1 • IU =

      = R−1.

      Аналогично предыдущему R = R • IV ⊆ R • R′ • (R′)−1 = IU • (R′)−1 = (R′)−1. Откуда в силу свойств R6 и R9 следует, что R−1 ⊆ R′.

      Из полученного следует равенство R′ = R−1.•

       

      Из определения 1.12 и утверждения 2.1 следует

       

      2

       

      Утверждение 2.2. В моноиде ⟨2U

      , (•, IU )⟩ обратимы подстановки и только они.

       

      Замечание 2.1. Утверждения 2.1 и 2.2 останутся справедливыми после соответствующих замен опе- рации • на операцию ◦.

       

      Докажем утверждение, равносильное утверждению 1.12 для конечных полугрупп.

      Утверждение 2.3. Любая конечная полугруппа ⟨U, (∗)⟩, изоморфно вложимая в группу, сама яв-

      ляется группой.

      Доказательство. В силу утверждения 1.9 в полугруппе ⟨U, (∗)⟩ будет существовать идемпотент.

      Так как эта полугруппа изоморфно вложима в группу, то идемпотент должен обладать свойствами

      нейтрального элемента и быть единственным, в противном случае он будет необратим. Обозначим этот элемент e ∈ U и перейдем к рассмотрению моноида ⟨U, (∗, e)⟩.

      В силу утверждения 1.8 ⟨U, (∗, e)⟩ ,:. ⟨UU , (•, IU )⟩, причем мономорфизм F∗ : U → UU , устанавливаю-

      щий вложение u˜ 1→ f∗, задается правилом f∗(u) = u ∗ u˜.

      u˜ u˜

      Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 1. С. 23–51

      Vestnik of Samara University. Natural Science Series. 2020, vol. 26, no. 1, pp. 23–51 33

      Обозначим EF ∗ = {f∗ | u˜ ∈ U ∧f∗(u) = u∗u˜} — множество значений F∗, тогда ⟨U, (∗, e)⟩ ∼ ⟨EF ∗ , (•, IU )⟩.

      u˜ u˜

      Пусть ⟨

      U, (∗, e)⟩ ,:. ⟨V, (⋆, ε)⟩, где ⟨V, (⋆, ε)⟩ — группа, и F : U → V — мономорфизм, устанавливающий

      вложение полугруппы в группу. Без ограничения общности будем считать, что EF = U ⊆ V и u⋆u˜ = u∗u˜

      для всех u, u˜ ∈ U .

      В силу утверждения 1.5 ⟨V, (⋆, ε)⟩ ,:. ⟨V V , (•, IV )⟩, причем мономорфизм F⋆, устанавливающий вло-

      жение v˜ 1→ f⋆, задается правилом f⋆(v) = v ⋆ v˜.

      v˜

      Обозначим

      v˜

      ˜

       

      EF ⋆ = {fv⋆ | v˜ ∈ V ∧fv˜(v) = v∗v˜} — множество значений F⋆, тогда ⟨V, (⋆, ε)⟩ ∼ ⟨EF ⋆ , (•, IV )⟩.

      В силу того, что ⟨

      V, (⋆, ε)⟩

      является группой, то моноид ⟨EF ⋆ , (•, IV )⟩ должен быть подгруппой сим-

      BV , (•, IV )⟩.

      метрической группы подстановок ⟨

      ˜

       

      ˜

       

      Рассмотрим произвольный элемент u˜ ∈ EF = U ⊆ V и соответствующую ему подстановку fu⋆ : V → V . По построению ее значения определяются правилом fu⋆(v) = v ⋆ u˜, причем для всех u˜ ∈ EF = U справед-

      f⋆ ∗ ∗

      ливо равенство

      f⋆

      u˜ (u) = u⋆u˜ = u∗u˜ = fu˜ (u). Таким образом, функция fu˜ является сужением подстановки

      u˜ на множество U ⊆ V и, следовательно, является тотальной инъекцией.

      ˜

       

      В общем случае функция fu∗

      может не быть сюръекцией. Однако если множество U конечно, то, в

      ˜

       

      силу утверждения 1.3, fu∗

      — подстановка и поэтому обратима. Из утверждения 1.10 будет следовать,

      что ⟨EF ∗ , (•, IU )⟩ — группа, и изоморфный ей моноид ⟨U, (∗, e)⟩ также будет группой. •

       

      Замечание 2.2. Свойство правого сокращения

      ∀u1, u2, u3 ∈ U u1 ∗ u3 = u2 ∗ u3 −→ u1 = u2

      u3

       

      эквивалентно свойству инъективности функции f∗ (u) = u ∗ u3, а свойство левого сокращения

      ∀u1, u2, u3 ∈ U u3 ∗ u1 = u3 ∗ u2 −→ u1 = u2

      u3

       

      эквивалентно свойству инъективности функции g∗ (u) = u3 ∗ u. Причем в случае конечного моноида

      u3

       

      выполнение одного из этих свойств, ввиду обратимости f∗

      u3

       

      или g∗ , влечет выполнение другого.

       

      Замечание 2.3. Пусть F∗ : U → UU и G∗ : U → UU — мономорфизмы моноида ⟨U, (∗, e)⟩ и моноидов

      ⟨UU , (•, IU )⟩ и ⟨UU , (◦, IU )⟩, соответственно. Моноиды ⟨EF ∗ , (•, IU )⟩ и ⟨EG∗ , (◦, IU )⟩ изоморфны только в

      тех случаях, когда они являются группами.

       

      Далее мы будем следовать статье [28], в которой определялись и изучались операции над многомест- ными отношениями на множестве U .

      Рассмотрим множество 3-местных отношений на U и по аналогии с определениями 1.1–1.3 дадим

      следующие определения.

       

      Определение 2.1. 1|3Транспозицией (по первому и третьему аргументам) 3-местного отношения

      3

       

      R ∈ 2U

      3

       

      называется 3-местное отношение Rt ∈ 2U

      , определяемое правилом

      Rt = {(u3, u2, u1) | u1, u2, u3 ∈ U ∧ (u1, u2, u3) ∈ R}.

      3

       

      3

       

      3

       

      Определение 2.2. 1|3Композицией (по первому и третьему аргументам) 3-местных отношений R1 ∈

      ∈ 2U

      и R2 ∈ 2U

      называется 3-местное отношение R1 ⊙ R2 ∈ 2U

      , определяемое правилом

      R1 ⊙ R2 = {(u1, u2, u3) | u1, u2, u3 ∈ U ∧ ∃u0 ∈ U (u1, u2, u0) ∈ R1 ∧ (u0, u2, u3) ∈ R2}.

      Определение 2.3. 1|3Инвариантным (по первому и третьему аргументам) 3-местным отношением

      3

      на множестве U называется 3-местное отношение IU ∈ 2U

      , определяемое правилом

      IU = {(u, u2, u) | u, u2 ∈ U }.

       

      Замечание 2.4. Аналогичные определения могут быть даны для 2|3операций (по второму и тре- тьему аргументам). Все дальнейшие рассуждения, которые будут проводиться для 1|3операций, легко

      переносятся и на этот случай (при соответствующих заменах операции • на операцию ◦). Для просто- ты изложения мы будем опускать верхние индексы в названиях операций, отношений и свойств всюду, кроме их определений.

       

      ∈

       

      3

       

      По аналогии с определением 1.13, для каждого 3-местного отношения R 2U

      2

      определим остовную

      R

       

      функцию F 0 : U → 2U

      , положив

      F 0

       

      R(u2) = {(u1, u3) | u1, u2, u3 ∈ U ∧ (u1, u2, u3) ∈ R},

      Цветов В.П. Полугруппы бинарных операций и криптосистемы на группоидах

      34Tsvetov V.P. Semigroups of binary operations and magma-based cryptography

       

      или, что то же самое,

      F 0

       

      R = {(u2, (u1, u3)) ≡ (u2, u1, u3) | u1, u2, u3 ∈ U ∧ (u1, u2, u3) ∈ R}.

      R1

       

      Понятно, что если для всех элементов u2 ∈ U имеют место равенства F 0

      R2

       

      (u2) = F 0

      (u2), то R1 = R2.

      R

       

      В силу определения F 0

      для произвольного элемента u2 ∈ U выполняются легко проверяемые равен-

      ства

      F 0 0 0

      R1 ∪R2 (u2) = FR1 (u2) ∪ FR2 (u2),

      F 0 0 0

      R1 ∩R2 (u2) = FR1 (u2) ∩ FR2 (u2),

      

      F 0 0

      

      R(u2) = FR(u2),

      ∅

       

      F 0(u2) = ∅,

      F 0

       

      U 3 (u2) = U 2,

      F 0 0 −1

      Rt (u2) = (FR(u2)) ,

      F 0 0 0

      R1 •R2 (u2) = FR1 (u2) ⊙ FR2 (u2),

      IU

       

      F 0 (u2) = IU .

       

      3

       

      Замечание 2.5. Из сказанного следует, что для каждого R ∈ 2U

      IU ⊙ R = R ⊙ IU = R,

      выполняются равенства

      а также другие свойства, аналогичные свойствам R1–R14 для операций из сигнатуры алгебры

      3

      ⟨2U

      , (∪, ∩,− , ∅, U 3, ⊙,t , IU )⟩, в т. ч. и ассоциативность операции ⊙.

       

      Кроме того, определения 1.4–1.12 допускают подходящую переформулировку для 3-местных отноше- ний на множестве U .

       

      3

       

      Определение 2.4. 1|3Областью определения 3-местного отношения R ∈ 2U

      ство

      будем называть множе-

      DR = ∩

      u2 ∈U

      DF 0

       

      R (u2 )

      ⊆ U.

       

      3

       

      Определение 2.5. 1|3Областью значений 3-местного отношения R ∈ 2U

      будем называть множество

      ER = ∩

      u2 ∈U

      EF 0

       

      R (u2 )

      ⊆ U.

       

      3

       

      Определение 2.6. Левым 1сужением (по первому месту) 3-местного отношения R ∈ 2U

      U0 ×U 2

      на множе-

      ство U0 ⊂ U называется 3-местное отношение RU0 ∈ 2

      , определяемое правилом

      RU0 = {(u1, u2, u3) | u1 ∈ U0 ∧ u2, u3 ∈ U ∧ (u1, u2, u3) ∈ R}.

       

      3

       

      Определение 2.7. Центральным 2сужением (по второму месту) 3-местного отношения R ∈ 2U на

      U0 ×U 2

      множество U0 ⊂ U называется 3-местное отношение RU0 ∈ 2

      , определяемое правилом

      RU0 = {(u1, u2, u3) | u2 ∈ U0 ∧ u2, u3 ∈ U ∧ (u1, u2, u3) ∈ R}.

       

      2

       

      2

       

      Определение 2.8. Правым 3сужением (по третьему месту) 3-местного отношения R ∈ 2U ×U0 на множество U0 ⊂ U называется 3-местное отношение RU0 ∈ 2U ×U0 , определяемое правилом

      RU0 = {(u1, u2, u3) | u1, u2 ∈ U ∧ u3 ∈ U0 ∧ (u1, u2, u3) ∈ R}.

      U0 ∈

       

      В тех случаях, когда это не приводит к недоразумениям, будем сохранять за сужениями R 2U0 ×U 2

      2

       

      и RU0 ∈ 2U ×U0 прежнее обозначение R.

       

      3

       

      Определение 2.9. Будем говорить, что 3-местное отношение R ∈ 2U

      DR = U,

      1тотально, если

      Вестник Самарского университета. Естественнонаучная серия. 2020. Том 26, № 1. С. 23–51

      Vestnik of Samara University. Natural Science Series. 2020, vol. 26, no. 1, pp. 23–51 35

       

      или, что то же самое,

      IU ⊆ R ⊙ Rt.

       

      Заметим, что в силу определений

      R

       

      DR = ∩ DF

      u2 ∈U

      2

       

      (u ) = ∩ {u1 | u1 ∈ U ∧ ∃u0 ∈ U (u1, u2, u0) ∈ R} =

      u2 ∈U

      = {u1 | u1 ∈ U ∧ ∀u2 ∈ U ∃u0 ∈ U (u1, u2, u0) ∈ R},

      и условие выполнение равенства DR = U равносильно условиям

      ∀u1, u2 ∈ U ∃u0 ∈ U (u1, u2, u0) ∈ R,

      ∀(u1, u2) ∈ U ∃u0 ∈ U ((u1, u2), u0) ∈ R.

      2

       

      Таким образом, данное определение совпадает с определением тотальности R ∈ 2U

       

      2

       

      ≡ 2U ×U как

      2-местного отношения из U 2 в U с учетом общепринятого соглашения (u1, u2, u3) ≡ ((u1, u2), u3). Заме-

      тим, что тождественное отношение IU тотально.

       

      3

       

      Определение 2.10. Будем говорить, что 3-местное отношение R ∈ 2U

      ER = V,

      3сюръективно, если

      или, что то же самое,

      IU ⊆ Rt ⊙ R.

      С учетом определения 2.1 можно утверждать, что 3-местное отношение сюръективно тогда и только тогда, когда его транспозиция тотальна, и наоборот.

      Аналогично предыдущему условие сюръективности равносильно условиям

      ∀u2, u3 ∈ U ∃u0 ∈ U (u0, u2, u3) ∈ R,

      ∀(u2, u" + i + ".