Множества с алгебраическими операциями. Бинарные операции (лекция 4) презентация

Таким образом, любой упорядоченной паре (a,b) элементов
a,b ∈X ставится в соответствие определенный элемент τ(a,b) того же множества X.
Иногда вместо τ(a,b) пишут aτb, а еще чаще бинарную операцию на X обозначают каким-нибудь специальным символом: ∗, ·, ⋅ или +.

Пример . В множестве Z целых чисел, помимо естественных
операций +, ⋅ (сложения и умножения), легко указать получающиеся при
помощи + (или -) и ⋅ "производные" операции:
n• m=n+m-n × m,
n∗m=-n-m и т.д.
Мы приходим к различным алгебраическим структурам
(Z,+), (Z,-), (Z, •) и (Z, ∗). ♦

Она также называется коммутативной, если a*b=b*a.

Те же названия присваиваются и соответствующей алгебраической структуре (X,*).

Требования ассоциативности и коммутативности независимы.

Пример. Операция * на Z, заданная правилом n*m=-n-m, очевидно, коммутативна.
Но (1*2)*3=(-1-2)*3=-(-1-2)-3=0 ≠ 1* (2*3)= 1*(-2-3)=-1-(-5)=4. Так что условие ассоциативности не выполняется.

Коммутативные операции: сложение и умножение чисел, объединение и пересечение множеств.
Некоммутативные операции: умножение матриц, композиция отношений.

Множество X с заданной на нем бинарной ассоциативной операцией называется полугруппой.

Полугруппу с единичным (нейтральным) элементом принято называть моноидом.

Группа G обладающая конечным числом элементов называется конечной группой.
Число элементов конечной группы называется порядком группы и обозначается #G (или |G|).

Простейшими примерами колец являются кольца целых чисел Z и многочленов R[x] с вещественными элементами.

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

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

Подкольцо H кольца R называется идеалом (двухсторонним идеалом) этого кольца ,если для всех , имеет место .

А) не существует такого , что ;
Б) существует такоe , что ;

Поле классов конгруэнтности целых чисел по модулю простого числа р GF(p)
(обозначается также Z/pZ или Fp) и
называется простым полем.

Если многократное сложение 1 не позволяет получить 0, то поле называется полем характеристики ноль, в этом случае оно содержит копию поля рациональных чисел.
В противном случае, если существует простое число р такое, что р-кратное сложение 1 даёт 0, число р называется характеристикой поля.
В этом случае поле содержит копию поля Z/pZ.

Если a ≡ b (mod n),
то b называют вычетом числа a по модулю n.

Это соотношение справедливо для целых значений a,b и n ≠ 0, если, и только если
a = b + k ∗ n
для некоторого целого k.

Операцию нахождения вычета числа a по модулю n
a (mod n)
называют приведением числа a по модулю n или приведением по модулю.

Например, для n =12 полный набор вычетов:
{0, 1, 2, …, 11}.

Заметим, что
–12 (mod 7) ≡ –5 (mod 7) ≡ 2 (mod 7) ≡ 9 (mod 7) и т.д.

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

(a + b) mod n = [a (mod n) + b (mod n)] mod n,

(a – b) mod n = [a (mod n) – b (mod n)] mod n,

(a ∗ b) mod n = [a (mod n) ∗ b (mod n)] mod n,

[a ∗ (b + c)] mod n = {[a ∗ b (mod n)] + [a ∗ c (mod n)]} mod n.

Существуют способы сделать это быстрее.
Поскольку эти операции дистрибутивны, быстрее произвести возведение в степень как ряд последовательных умножений, выполняя каждый раз приведение по модулю. Это особенно заметно, если работать с длинными числами (200 бит и более).

Например, если нужно вычислить
a8 mod n,
не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа:
(a ∗ a ∗ a ∗ a ∗ a ∗ a ∗ a ∗ a) mod n.

Тем же способом вычисляют
a16 mod n = (((a2 mod n)2 mod n)2 mod n)2 mod n.

Вычисление
ax mod n,
где x не является степенью 2, лишь немного сложнее. Двоичная запись числа x позволяет представить число x как сумму степеней 2:
x = 25(10) → 1 1 0 0 1(2), поэтому 25 = 24 + 23 + 20.

При разумном накоплении промежуточных результатов потребуется только шесть умножений:
(((((((a2 mod n) ∗ a) mod n)2 mod n)2 mod n)2 mod n) ∗ a) mod n.
Этот метод уменьшает трудоемкость вычислений до 1,5хk операций в среднем, где k – длина числа в битах .

Пусть a – целое число, большее 1. Тогда
a является простым числом,
если его единственными положительными делителями будут 1 и само a,
в противном случае a называется составным .

Существенный с точки зрения криптографии факт состоит в том, что не известно никакого эффективного алгоритма разложения чисел на множители;
не было получено и никакой нетривиальной нижней оценки временной сложности разложения.
Никаких эффективных методов не известно даже в таком простом случае, когда необходимо восстановить два простых числа p и q из их произведения:
n = p ∗ q.

Наибольший общий делитель может быть вычислен с помощью алгоритма Евклида. Евклид описал этот алгоритм в своей книге "Начала", написанной около 300 лет до н.э. Он не изобрел его. Историки полагают, что этот алгоритм, возможно, старше еще на 200 лет. Это древнейший нетривиальный алгоритм, который просуществовал до настоящего времени и все еще хорош и сегодня.

a = b ∗ q1 + r1, 0 < r1< b,
b = r1 ∗ q2 + r2, 0 < r2< r1,
r1 = r2 ∗ q3 + r3, 0 < r3< r2,
…….
rn–2 = rn–1 ∗ qn + rn, 0 < rn< rn–1,

rn–1 = rn ∗ qn+1 rn+1=0

Как следствие из алгоритма Евклида, можно получить утверждение, что
наибольший делитель целых чисел a и b
может быть представлен в виде линейной комбинации этих чисел, т.е. существуют целые числа и и v такие, что справедливо равенство

(a,b)=(b,r)=(r,r1) = …=(rn-1,rn)=rn

Вычислить а' можно, например, воспользовавшись представлением наибольшего общего делителя чисел а и n в виде их линейной комбинации: а*и + n*v = 1.

Взяв наименьшие неотрицательные вычеты обеих частей этого равенства по модулю n, получим, что искомое значение а' удовлетворяет сравнению
а' = и (mod n)

В процессе вычисления используются вспомогательные векторы (v1, v2, v3), (t1, t2, t3). Действия с векторами производятся таким образом, что в течение всего процесса вычисления выполняются соотношения

a ∗ t1 + b ∗ t2 = t3, a ∗ u1 + b ∗ u2 = u3,

a ∗ v1 + b ∗ v2 = v3.

2. u3 =1 ?. Если u3 =1, то алгоритм заканчивается.
3. Разделить, вычесть.
Установить q : = [u3/v3].
Затем установить
(t1, t2, t3) : = (u1, u2, u3) – (v1, v2, v3) ∗ q,
(u1, u2, u3) : = (v1, v2, v3),
(v1, v2, v3) : = (t1, t2, t3).
Возвратиться к шагу 2.

q : = [u3/v3].
(u1, u2, u3) : = (v1, v2, v3),
(t1, t2, t3) : = (u1, u2, u3) – (v1, v2, v3) ∗ q,
(v1, v2, v3) : = (t1, t2, t3).

Если п - простое число, в приведенную систему вычетов по модулю п входит всё множество чисел от 1 до п— 1.

Для любого n, не равного 1, число 0 никогда не входит в приведенную систему вычетов.

Иными словами, φ(п) - это количество положительных целых чисел, меньших п и взаимно простых с п (для любого n, большего 1).

Если п — простое число, то φ(п) = п-1.

Если n = pq, где р и q - простые числа, то φ(п) = (р-1)(q-1).

Теперь нетрудно вычислить а-1 mod n: