Какие арифметические действия обладают свойствами коммутативности

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

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

В лекциях 2-3 мы обсуждали некоторые множества чисел, таких как Z, Zn, Zn*, Zp^ и Zp*. Криптография требует, чтобы были заданы множества целых чисел, и операции, определенные для них. Комбинация множеств и операций, которые могут быть применены к элементам множества, называются алгебраической структурой. В этой лекции мы определим три общих алгебраических структуры: группы, кольца и поля ( рис. 5.1).

Группы

Группа ( G ) — набор элементов с бинарной операцией «•» обладает четырьмя свойствами (или удовлетворяет аксиомам), которые будут перечислены ниже.

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

• Замкнутость. Если a и b — элементы G, то c = a • b — также элемент G.
  Это означает, что результат применения операции с любыми двумя элементами множества есть элемент этого множества.
• Ассоциативность. Если a, b и c — элементы G, то верно (a• b) • c = a• (b •c)
  Другими словами, не имеет значения, в каком порядке мы применяем операцию более чем с двумя элементами.
• Коммутативность. Для всех a и b в G мы имеем a • b = b • a. Обратите внимание, что это свойство должно быть верно только для коммутативной группы.
• Существование нейтрального элемента. Для всех элементов в G существует элемент e, который называется нейтральным элементом, такой, что e • a = a • e = a.
• Существование инверсии. Для каждого a в G существует элемент a’, называемый инверсией, такой, что a • a’ = a’ • a = e.

Рисунок 5.2 иллюстрирует понятие группы.

Приложение

Хотя группа включает единственный оператор, свойства, присущие каждой операции, позволяют использование пары операций, если они — инверсии друг друга. Например, если определенный выше оператор — сложение, то группа поддерживает и сложение, и вычитание, ибо вычитание и сложение — аддитивно инверсные операции. Это также верно для умножения и деления. Однако группа может поддержать только сложение/вычитание или умножение/деление, но не оба сочетания операторов одновременно.

Пример 5.1

Множество целых чисел, входящих в вычет с оператором сложения, G = <Zn, +>, является коммутативной группой. Мы можем выполнить сложение и вычитание на элементах этого множества, не выходя за его пределы.

Проверим эти свойства.

1. Замкнутость удовлетворяется. Результат сложения двух целых чисел в Zn — другое целое число в Zn.
2. Ассоциативность удовлетворяется. Результат 4 + (3 + 2) тот же самый, что в случае (4 + 3) + 2.
3. Коммутативность удовлетворяется. Мы имеем 3 + 5 = 5 + 3.
4. Нейтральный элемент — 0. Мы имеем 3 + 0 = 0 + 3 = 3.
5. Каждый элемент имеет аддитивную инверсию. Инверсия элемента — его дополнение. Например, инверсия 3 — это –3 ( n – 3 в Zn ), и инверсия –3 — это 3. Инверсия позволяет нам выполнять вычитание на множестве.

Пример 5.2

Множество Zn* с оператором умножения G = <Zn*, >, является также абелевой группой. Мы можем выполнить умножение и деление на элементах этого множества, не выходя за его пределы. Это облегчает проверку первых трех свойств. Нейтральный элемент равен 1. Каждый элемент имеет инверсию, которая может быть найдена согласно расширенному алгоритму Евклида.

Пример 5.3

Хотя мы обычно представляем группу как множество чисел с обычными операторами, такими, как сложение или вычитание, определения группы позволяют нам определять любое множество объектов и операций, которые удовлетворяют вышеупомянутым свойствам. Определим множество G = <{a, b, c, d,}, •> и операцию, показанную с помощью таблицы 5.1.

Это — абелева группа. Все пять свойств удовлетворены.

1. Замкнутость удовлетворена. Применение оператора на любой паре элементов дает в результате другой элемент этого множества.
2. Ассоциативность также удовлетворена. Чтобы доказать это, мы должны проверить свойство для любой комбинации из трех элементов. Например, (a+ b) + c = a+ (b + c) = d.
3. Операция коммутативна. Мы имеем a + b = b + a.
4. Группа имеет нейтральный элемент, которым является a.
5. Каждый элемент имеет инверсию. Обратные пары могут быть найдены. В таблице они указаны теневыми элементами в каждой строке. Пары — (a, a), (b, d), (c, c).

Пример 5.4

В группе элементы в множестве не обязательно должны быть числами или объектами; они могут быть правилами, отображениями, функциями или действиями. Очень интересная группа — группа подстановок. Множество всех перестановок и оператор является композицией: применения одной перестановки за другой. Рисунок 5.3 показывает композиции двух перестановок, которые перемещают три входных сигнала, чтобы создать три выходных сигнала.

Входные сигналы и выходные сигналы могут быть символами (лекции 2-3) или битами. Мы изобразили каждую перестановку прямоугольником, внутри которого показано, где исходящий входной сигнал и индекс ( 1,2,3 ) определяет выходной сигнал. Композиция состоит из двух перестановок одна за другой. При трех входных сигналах и трех выходных сигналах может быть 3! или 6 различных перестановок. Таблица 5.2 дает определение этого оператора. Первая строка — первая перестановка; первый столбец — вторая перестановка. Результат содержится на пересечении.

В этом случае удовлетворены только четыре свойства; поэтому группа — не абелева.

1. Замкнутость удовлетворена.
2. Ассоциативность также удовлетворена. Чтобы доказать это, мы должны проверить свойство для любой комбинации из трех элементов.
3. Свойство коммутативности не удовлетворено. Это может быть легко проверено, но мы оставим это для упражнения.
4. Множество имеет нейтральный элемент [1 2 3] (перестановка отсутствует). Эти элементы показаны другим цветом.
5. Каждый элемент имеет инверсию. Обратные пары могут быть найдены, если использовать нейтральные элементы.

Пример 5.5

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

Конечная группа

Группа называется конечной группой, если множество имеет конечное число элементов; иначе это — бесконечная группа.

Порядок группы

Порядок группы, G, — это число элементов в группе. Если группа не конечна, ее порядок бесконечен; если конечна, порядок конечен.

Подгруппы

Подмножество H группы G — подгруппа G, если само H — группа относительно операции на G. Другими словами, если G = <S, •> — группа, то H = <T, •> — группа для той же самой операции, и T — непустое подмножество S, то H — подгруппа G. Вышеупомянутое определение подразумевает, что:

1. если a и b — члены обеих групп, то c = a • b — также элемент обеих групп;
2. для группы и подгруппы имеется один и тот же нейтральный элемент;
3. если этот элемент принадлежит обеим группам, инверсия a — также элемент обеих групп;
4. группа, полученная с помощью нейтрального элемента G, H = <{e}, •>, является подгруппой G ;
5. каждая группа — подгруппа самой себя.

Пример 5.6

Является ли группа H = <Z10, +> подгруппой группы G = <Z12, +>?

Решение

Ответ — нет. Хотя H — подмножество G, операции, определенные для этих двух групп, различны. Операция H — сложение по модулю 10 ; операция в G — сложение по модулю 12.

    Если читателю интересно, он может проверить, как из приведенных выше соображений можно вывести наиболее удивительные свойства Л+-функций суперпозиция обладает теми же свойствами, что и объединение, и, следовательно, коммутативна и идемпотентна. [c.251]

    Операция умножения матрицы не обладает свойством коммутативности. Это значит, что результат умножения матрицы Ашг В слева или справа (т. е. С = АВ или С = ВА), вообще говоря, различен. [c.234]

    При соблюдении размерностей перемножаемых матриц операция умножения обладает следующими свойствами умножение матриц ассоциативно (АВ) С = Л (ВС)-, умножение матриц дистрибутивно А — — В) С = АС + ВС единичная матрица коммутативна (перестановочная) с любой квадратной матрицей того же порядка, т. е. АЕ = ЕА = А нри перемножении квадратных матриц определитель матрицы произведения равен произведению определителей матриц сомножителей. Например, если и jB—квадратные матрицы порядка п, то [c.234]

    Операторы Д и с) обладают свойствами коммутативности, т, е. 5 (Aa»)—A (ддг). Действительно, [c.104]

    Из этих примеров следует, что операторы классов К/ обладают важным свойством коммутативности  [c.195]

    Множество неособенных матриц и-го порядка образует группу, если в качестве групповой операции взять правило умножения матриц. Нейтральным элементом будет единичная матрица, обратным — обратная матрица. Так как в общем случае умножение матриц свойством коммутативности не обладает, эта группа не является абелевой. [c.120]

    Коммутативность А [j В = В [ ] А, А В = В А. Данные свойства с очевидностью вытекают из приведенных определений операций над нечеткими множествами. [c.33]

    Свертка, как и произведение, обладает свойством коммутативности fx fi — /2 fx или [c.40]

    В общем случае произведение элементов группы не обладает свойством коммутативности. Это означает, что результат последовательного применения операций симметрии зависит от того порядка, в котором они применяются. На рис. 4-3 показан пример с молекулой аммиака, принадлежащей к точечной группе Результат различается в зависимости от того, применяется ли сначала операция С , а затем а» или же, наоборот. Произведение операции идентичности с любым элементом группы обладает свойством коммутативности по определению. Так, например, [c.183]

    Точечная группа необычна в том отношении, что все возможные произведения ее элементов обладают свойством коммутативности. Так, на рис. 4-2, а мы могли бы получить тот же самый результат, сначала применив отражение а , а уже потом поворот второго порядка. [c.183]

    Свойства коммутативности и аддитивности означают, что  [c.91]

    Графический анализ для трех- и четырехкомпонентных смесей позволяет легко установить, что сформулированное выще для зеотропных смесей (см. разд. 6) свойство коммутативности и аддитивности при четком разделении не всегда выполняется в случае азеотропных смесей. [c.109]

    Свойство коммутативности и аддитивности означает, в частности, следующее  [c.109]

    Если указанные точки не связаны между собой непосредственно, то свойство коммутативности и аддитивности не выполняется, если же они связаны непосредственно, но связывающие их с-линии криволинейны, то это свойство выполняется только приближенно. [c.110]

    Второй пример — произведения матрицы-строки и матрицы-столбца — иллюстрирует отсутствие свойства коммутативности  [c.168]

    Четыре продуктовых симплекса попарно пересекаются, так что каждой зоне ректификации соответствуют два продуктовых симплекса. Покажем, что в пределах продуктового симплекса свойство аддитивности и коммутативности соблюдается. [c.121]

    В отношении свойства аддитивности и коммутативности схем разделения продуктовый симплекс эквивалентен зеотропной смеси. При переборе вариантов по ключевым особым точкам необходимо только предварительно исключить варианты, не удовлетворяющие условиям для размерностей продуктовых точек. Примерами продуктовых симплексов для четырехкомпонентных смесей могут служить симплексы 12—1—3—4, 1—3— 23—24, 1—3—4—24, 12—3—23—24 для структуры, изображенной на рис. П1-7, и симплексы 12—24—4—3, 12—23—24—3, 12—23—24—3, 12—4—3—1 для структуры, изображенной на рис. П1-5,(3. [c.121]

    В разд. 4.1 мы познакомились с определением коммутирующих операторов. Ниже мы убедимся, что коммутативность двух, операторов отражает важное физическое свойство системы. [c.57]

    Следовательно, если оператор Т обладает всеми свойствами симметрии оператора 6 , оба оператора проявляют свойство коммутативности. [c.115]

    Очевидно, что единичная матрица остается единичной в любом представлении, т. е. всякое представление является ее собственным представлением. Подумайте, как связать этот факт со свойством коммутативности оператора I с другими операторами. Покажите, что если С = А -Ь В, то С п = = Акп + Впп- Для доказательства воспользуйтесь выражением (1.18). [c.32]

    Любой элемент абелевой группы есть класс действительно, из свойства коммутативности АХ = ХА следует равенство А — ХАХ К В неабелевых группах класс может состоять из нескольких элементов. С помощью таблицы умножения (табл. А.1) мы без труда найдем, что группа содержит 5 классов  [c.335]

    Начнем с того, что не только числа можно складывать и умножать на другие числа. Аналогичным свойством обладают векторы, полиномы от одной или нескольких переменных, поля скоростей движущейся жидкости, электромагнитные поля, волновые функции в квантовой механике и множество других совокупностей физических и математических объектов. При этом сумма двух векторов является вектором, а сумма двух электромагнитных полей, конечно, опять представляет собой электромагнитное поле. То же относится и к остальным перечисленным видам величин. Существенно, что какие бы однотипные величины мы ни взяли, их сложение и умножение на число приводят к величине того же типа. Эти два действия подчиняются коммутативному, двум ассоциативным и двум дистрибутивным законам  [c.101]

    Это указывает на возможность использования матричного представления в квантовой механике в таком представлении основные динамические операторы заменяют на динамические матрицы, бра -векторы — на однострочные и кет -векторы — на одностолбцовые матрицы. Такое представление не только возмо но, но оно было одной из форм, в которых первоначально развивалась квантовая механика [представление Гейзенберга). То обстоятельство, что матрицы не подчиняются коммутативному закону умножения и что свойства собственных значений динамических матриц не зависят от представления, которое было использовано для построения матричных элементов, наводит на мысль, что собственные значения таких матриц определяются их правилами коммутации так оно и есть в действительности. Более того, правила коммутации для динамических матриц совпадают с правилами коммутации для соответствующих операторов. Например, матрицы q , [рц соответствующие координатам положения и сопряженным с ними моментам рт, подчиняются таким же правилам коммутации, как и для операторов рт [см. (1.34)], т. е. [c.68]

    В большинстве случаев произведение матриц не обладает свойством коммутативности, но обладает свойствами ассоциативности и дистрибутивности  [c.168]

    Произведение прямой матрицы на обратную обладает свойством коммутативности  [c.169]

    А + В)С=АС + ВС 3°. А(В + С)=АВ + АС Умножение в общем случае не обладает переместительным свойством, т. е. не коммутативно [c.14]

    Совместную реализацию (х,-, х/) переменных X,- и X/, между которыми установлено причинно-следственное отношение, можно рассматривать как состояние ху некоторого сложного фактора X//, представляющего собой объединение факторов Х/ и X/, т. е. Х11 = Х [ Х,-. Объединение факторов соответствует структурной операции, обладающей свойствами идемпотентности, коммутативности и ассоциативности. Такая структурная операция порождает структурное преобразование Су исходного графа С. Граф Оц представляет собой граф О, в котором пара вершин X и X/ заменяется новой вершиной, соответствующей сложному фактору Хг/. При этом локальные степени вершины Хц будут Р / = Р + Р/ 1 и р у = р + Ру — 1. Количество возможных структурных преобразований исходного графа О равно числу его ориентированных ребер (дуг). При этом максимальное число дуг в п-вершинном орграфе С равно I = /2 ( — 1). [c.56]

    Термин автомодельность уже встречался в 13 для описания частных случаев кратных волн, обладающих конической автомодельностью. В более щирокой трактовке, применительно к физическому содержанию решаемых задач, автомодельными принято называть решения, которые получаются путем анализа размерностей всех участвующих величин. С точки зрения теоретико-группового подхода это равносильно использованию допускаемых уравнениями групп растяжений. Однако свойство некоторой группы преобразований быть группой растяжений зависит от выбора системы координат в пространстве основных переменных. На самом деле единственным инвариантным характеристическим свойством групп растяжений является то, что они абелевы (коммутативны). Поэтому рационально использовать термин автомодельный применительно к любым решениям, инвариантным относительно абелевых подгрупп основной группы. При этом представление рещения в той системе координат, в которой группа является группой растяжений, удобно называть автомодельным в узком смысле. [c.197]

    Я ) строится оснащение (1.4) с требуемыми свойствами 1, 2 при помощи конструкций, близких к описанным в теореме 3.9 гл. 3 (с использованием пространства iO (IR»), при этом, разумеется, нужно требовать V ф Яо слабую непрерывность функции IR» Э л — Л g б Яо). Таким образом, в этом случае теорема 1.2 переходит в обычную теорему Стоуна требования, связанные с оснащением, выполняются автоматически. Аналогичная ситуация имеет место, если X — локально компактная сепарабельная коммутативная группа со счетным базисом окрестностей. Однако сейчас выбор требуемого оснащения гораздо более сложный. Он будет произведен в 2, п. 4, сразу для общего случая гиперкомплексной системы с локально компактным базисом.  [c.316]

    Обобщение такой г. с., фигурирующее ниже, заключается в переходе от конечного базиса Q к некоторому локально компактному пространству Q. Сейчас в связи с имеющимися примерами уместно с заменить на структурную меру с (а, р, г) (а, Р с Q г Q), а не функцию иа Q X Q X Q. Наиболее полные результаты гармонического анализа получаются в случае коммутативной г. с. с неотрицательной с, напоминающей своими свойствами групповую алгебру локально компактной коммутативной группы G (так называемые нормальные г. с. с базисной единицей о). [c.327]

    В этом параграфе мы введем необходимый класс г. с., установим некоторые их свойства, построим необходимую для дальнейшего теорию обобщенных функций на базисе Q г. с. и затем получим спектральные представления для семейства (Ap)p Q коммутирующих нормальных операторов, реализующего представление (в определенном смысле) г. с. Отметим, что ситуация, когда Q — локально компактная коммутативная группа, охватывается этой схемой. [c.327]

    Как видно из (3.55), семейство А = (Л/) ,, где Лу = ВЦ состоит из самосопряженных коммутирующих операторов. Будем по нему строить разложение Я в прямой интеграл (3.4), беря в качестве т множество X 5 X. .. (для фиксированного неприводимого представления) благодаря ограниченности операторов, фигурирующих в (3.55), трудностей с построением оснащения не будет. Первые два равенства в (3.55) имеют вид (3.11) с должным выбором отображения Р ( ) пространства точек А. = (Яу) в себя. Третье равенство в (3.55) должно быть учтено при описании свойств операторов С ( , ) в коммутативной модели. В результате получим следующее представление. Пусть б = (буу ) , к 1Ы), тогда [c.379]

    Предположим, для простоты, что действие 81- и 8]-объектов друг на друга коммутативно, т.е. т(sj,si)=т(si,sj), поэтому достаточно рассмотреть только Т(5],зО, поскольку Т(81,81) И T(sj,sj) — воздействие объекта на самого себя равно нулю (Т(81,80 = T(Sj,Sj) = 0). Для наглядности примера, предположим, что — положительный электрический заряд (допустим, заряд протона), Sj — отрицательный электрический заряд (допустим, равный заряду электрона). Один электрон (8]-объект) — еще ничего не говорит о свойствах электричества и заряда. Добавление к электрону 81-объекта порождает новое качество [c.25]

    В общем случае «накопление» качественных свойств системы не коммутативно. Наращивание системы новыми компонентами, как и добавление нового символа в уже существующий текст, может перевернуть все предыдущее содержание, а может пройти и незамеченным. В процессе включения в систему каждого нового объекта возможны три типа новых для нее состояний а) незначительные количественные изменения, б) переход в качественно новое устойчивое состояние, в) прекращение существования («взрыв» или «коллапс»). [c.26]

    Заметим, что двукратное полудифференцирование или полу-интегрирование эквивалентны соответствующим однократным операциям первого порядка. При этом операции полудифференцирования и полуинтегрирования, как и целочисленные, являются линейными операциями, обладающими свойствами коммутативности, что позволяет изменять последовательность их выполнения. [c.18]

    Его можно представить также в ином, более удобном для практического применения виде, если учесть, что в (8.39) полупроизводная функции АС(0) равна обычной производной полуинтеграла этой функции. Поскольку линейные по своему характеру операции дифференцирования и интегрирования (как целого, так и дробного порядка) обладают свойством коммутативности, то [c.279]

    Технологические схемы четкого разделения зеотропных смесей без распределяющихся компонентов обладают свойствами коммутативности и аддитивности. Чтобы уяснить эти свойства, рассмотрим два саркапта технологической схемы разделения многокомпонентной зеотропной смеси. При этом достаточно рассмотреть только две колонны для каждого варианта схемы с легкими ключевыми компонентами и /(7(первом варианте схемы колонна с -тым ключевым компонентом расположена непосредственно перед колонной с /-тым ключевым компонентом, а при втором варианте — наоборот. [c.90]

    Сравнение уравнений (41) и (42) показывает, таким образом, что АВ может быть эрмитовским оператором только в том случае, если АВ тождественно ВА. Иными словами, произведение двух эрмитовских операторов является также эрмитовским оператором только в том случае, если они обладают свойством коммутативности. Частным случаем коммутирующих операторов является случай двух идентичных операторов. Отсюда следует, что если А представляет собой эрми-товский оператор, то и АА, т. е. А , также является эрмитовским. [c.47]

    Коммутативность, вообще говоря, нарушается, если время входит в постановку задачи не только в связи с реономностью свойств среды, а, например, и в исходные уравнения или в граничные условия. [c.119]

Статистические методы оптимизации химических процессов (1972) — [

c.168

]