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

1.

МНОЖЕСТВА С АЛГЕБРАИЧЕСКИМИ
ОПЕРАЦИЯМИ
БИНАРНЫЕ ОПЕРАЦИИ
Пусть X – произвольное множество.
Бинарной алгебраической операцией (или законом композиции)
на X называется произвольное (но фиксированное)
отображение
t:X X®X декартова квадрата X2=X X в X.
Таким образом, любой упорядоченной паре (a,b) элементов
a,b ÎX ставится в соответствие определенный элемент t(a,b)
того же множества X.
Иногда вместо t(a,b) пишут atb, а еще чаще бинарную
операцию на X обозначают каким-нибудь специальным
символом: *, ·, × или +.

2.

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

3.

Наряду с бинарными алгебраическими операциями не лишены
интереса гораздно более общие n-арные операции:
унарные при n=1,
тернарные при n=3 и т.д., равно как и их комбинации.
Связанные с ними алгебраические структуры составляют
специальную теорию универсальных алгебр.

4.

ПОЛУГРУППЫ И МОНОИДЫ
Бинарная операция * на множестве X называется
ассоциативной,
если (a*b)*c=a*(b*c) для всех a,b,cÎX .
Она также называется коммутативной, если
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.
Так что условие ассоциативности не выполняется.

5.

Некоторые свойства операций имеют специальные названия.
Пусть задана алгебра (M, ) и a,b,c M,
”•“,”*” . (, т.е. бинарные операции).
Тогда:
1. ассоциативность: (a*b) *c=a* (b*c);
2. коммутативность: a*b=b*c;
3. дистрибутивность слева: a• (b*c)=a•b*a•c;
4. дистрибутивность справа: (a*b) •c=a•c*b•c;
5. поглощение: (a*b) •a=a;
6. идемпотентность: a*a=a.

6.

Ассоциативные операции: сложение и умножение чисел,
объединение и пересечение множеств, композиция отношений.
Неассоциативные операции: возведение числа в степень,
вычитание множеств.
Коммутативные операции: сложение и умножение чисел,
объединение и пересечение множеств.
Некоммутативные операции: умножение матриц,
композиция отношений.
Дистрибутивные операции: умножение относительно
сложения чисел.
Недистрибутивные операции: возведение в степень
дистрибутивно относительно умножения справа, но не слева:
ab
c
a b
c
c
a
bc
a a
b
c

7.

Элемент e X называется единичным (или нейтральным)
относительно рассматриваемой бинарной операции *, если
e*x = x*e = x для всех x X.
Если e' – еще один единичный элемент, то, как следует из
определения,
e'=e'*e=e*e'=e.
Следовательно, в алгебраической структуре (X,*) может
существовать не более одного единичного элемента.
Множество X с заданной на нем бинарной
ассоциативной операцией называется полугруппой.
Полугруппу с единичным (нейтральным) элементом
принято называть моноидом.

8.

Элемент a моноида (M,×,e) называется обратимым, если
найдется элемент b M, для которого a×b=b×a=e
(понятно, что элемент b тоже обратим).
Если еще и a×b' = e = b'×a,
то b' = e×b' = (b×a)×b' = b×(a×b') = b×e = b.
Это дает основание говорить просто об обратном элементе a-1 к
(обратимому) элементу a M:
a×a-1 = e = a-1×a.
Разумеется, (a-1)-1=a.

9.

Группой называется непустое множество G с бинарной
операцией * на нем, для которой выполнены следующие
аксиомы:
операция * ассоциативна, т.е. для любых a,b,c G
a*(b*c)=(a*b)*c;
В множестве имеется единичный элемент (или единица) e такой,
что для любого a*e=e*a=a;
Для каждого a G существует обратный элемент a-1 G такой, что
a* a-1 = a-1 * a = e;
Группа называется абелевой (или коммутативной), если для
любых a,b G выполняется a*b =b*a.

10.

Множество Z целых чисел образует абелеву группу
относительно операции сложения.
То же самое можно сказать относительно рациональных чисел
Q, вещественных R и комплексных C
Группа G с мультипликативной операцией называется
циклической , если она порождена одним элементом,
т.е. в ней имеется такой элемент a (образующий), что любой
другой элемент b представим в виде
n 0, a n ( a 1 )
b = an , n Z.
n
Группа G обладающая конечным числом элементов называется
конечной группой.
Число элементов конечной группы называется порядком группы и
обозначается #G (или |G|).

11.

Кольцом называется множество R с двумя
бинарными операциями, обозначаемыми «+»и «•»,
такими, что:
R- абелева группа относительно операции «+»;
Операция «•» ассоциативна ,т.е. для любых выполнено (ab)c =
a(bc);
Выполнены законы дистрибутивности, т.е. для всех a, b, c Î R
a (b c) ab ac, (b c)a ba ca
выполнено
Нейтральный элемент аддитивной группы кольца называют нулем
и обозначают 0.
Противоположный (обратный) к a элемент обозначают -a.
Обычно пишут вместо a ( b) a b.
Простейшими примерами колец являются кольца целых чисел Z
и многочленов R[x] с вещественными элементами.

12.

Кольцо называется кольцом с единицей, если оно имеет
мультипликативную единицу, т.е. такой элемент , что
ea ae a
для любого a Î R .
Кольцо называется коммутативным, если операция умножения
коммутативна.
Два элемента называться делителями нуля, если :
a 0, b 0
ab 0

13.

Рассмотрим кольцо матриц размера 2 2 над полем
действительных чисел.
0 0
Нулем этого кольца является матрица:
0 0
единицей - матрица :
1 0
0 1
.
10 00
1 0
и b
Делителями нуля являются матрицы: a
00 10
0 0

14.

Поля
Основные понятия

15.

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

16.

Примерами являются
Q - поле рациональных чисел,
R - поле действительных чисел,
С - поле комплексных чисел,
Поле
,
такое, что
,
называется расширением поля
,
например, поле С есть расширение как поля Q, так и поля R,
последнее является расширением поля Q.

17.

Число к элементов поля называется порядком поля.
Различают бесконечные
рациональных чисел)
поля
(например,
множество
и
конечные поля, например, поле {0,1} с операциями сложения
по модулю два и умножения.
Конечные поля называются полями Галуа .
Поле Галуа порядка к обозначается GF(k) или
.

18.

Простейшим конечным полем является бинарное поле GF(2) с
операциями
сложения по модулю 2 и
Å
• умножения.
Эти операции определяются таблицами

19.

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

20.

Множество смежных классов по модулю m (или их
обозначений ) с операциями сложения и умножения по
модулю m
на множестве обозначений этих классов
является полем тогда и только тогда,
когда m = р, где р - простое число.
Единицами по сложению и умножению этого поля GF(p)
являются классы, содержащие числа 0 и 1 соответственно.

21.

Элемент g поля называется примитивным, или образующим,
если для любого другого ненулевого элемента а поля найдется
неотрицательное число х, такое, что а = gх.
Поле классов конгруэнтности целых чисел по модулю
простого числа р GF(p)
(обозначается также Z/pZ или Fp) и
называется простым полем.
Если многократное сложение 1 не позволяет получить 0, то
поле называется полем характеристики ноль, в этом случае
оно содержит копию поля рациональных чисел.
В противном случае, если существует простое число р такое,
что р-кратное сложение 1 даёт 0, число р называется
характеристикой поля.
В этом случае поле содержит копию поля Z/pZ.

22.

23.

ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ
Модулярная арифметика

24.

Запись в модулярной арифметике
a b (mod n)
читается так: "a сравнимо с b по модулю n".
Это соотношение справедливо для целых значений a,b
и n 0, если, и только если
a=b+k*n
для некоторого целого k.
Если a b (mod n),
то b называют вычетом числа a по модулю n.
Операцию нахождения вычета числа a по модулю n
a (mod n)
называют приведением числа a по модулю n или
приведением по модулю.

25.

Набор целых чисел от 0 до (n –1) называют полным
набором вычетов по модулю n.
Это означает, что для любого целого a (a > 0) его вычет
r по модулю n есть некоторое целое число в интервале
от 0 до (n –1), определяемое из соотношения
r = a – k * n,
где k – целое число.
Например, для n =12 полный набор вычетов:
{0, 1, 2, …, 11}.

26.

Обычно предпочитают использовать вычеты
r Î {0, 1, 2, …, n –1},
но иногда полезны вычеты в диапазоне целых:
1
1
r Î (n 1),..., (n 1)
2
2
Заметим, что
–12 (mod 7) –5 (mod 7) 2 (mod 7) 9 (mod 7) и т.д.

27.

Целые числа по модулю n с использованием операций
сложения и умножения образуют коммутативное кольцо
при соблюдении законов ассоциативности,
коммутативности и дистрибутивности.
Фактически мы можем либо сначала приводить по
модулю 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.

28.

Вычисление степени числа a по модулю n
ax mod n
можно выполнить как ряд умножений и делений.
Существуют способы сделать это быстрее.
Поскольку эти операции дистрибутивны, быстрее
произвести возведение в степень как ряд
последовательных умножений, выполняя каждый раз
приведение по модулю. Это особенно заметно, если
работать с длинными числами (200 бит и более).
Например, если нужно вычислить
a8 mod n,
не следует применять примитивный подход с
выполнением семи перемножений и одного приведения
по модулю громадного числа:
(a * a * a * a * a * a * a * a) mod n.

29.

Вместо этого выполняют три малых умножения и три
малых приведения по модулю:
((a2 mod n)2 mod n)2 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.

30.

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

31.

Алгоритм Евклида для нахождения наибольшего
общего делителя
Целое число a делит без остатка другое целое число b,
если, и только если
b=k*a
для некоторого целого числа k.
В этом случае a называют делителем числа b или
множителем в разложении числа b на множители.
Пусть a – целое число, большее 1. Тогда
a является простым числом,
если его единственными положительными делителями
будут 1 и само a,
в противном случае a называется составным .

32.

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

33.

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

34.

Опишем алгоритм Евклида для нахождения НОД (a,b).
Введем обозначения:
qi – частное;
ri – остаток.
Тогда алгоритм можно представить в виде следующей
цепочки равенств:
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

35.

(a,b)=(b,r)=(r,r1) = …=(rn-1,rn)=rn
Остановка гарантируется, поскольку остатки ri от
делений
образуют
строго
убывающую
последовательность натуральных чисел.
Таким образом, rn = НОД (a, b) или rn = (a, b).
Как следствие из алгоритма Евклида, можно получить
утверждение, что
наибольший делитель целых чисел a и b
может быть представлен в виде линейной комбинации
этих чисел, т.е. существуют целые числа и и v такие, что
справедливо равенство
a × u b × v rn

36.

Алгоритм Евклида для вычисления наибольшего
общего делителя
begin
g[0]: = b;
g[1]: = a;
i : =1;
while g[i] ! = 0 do
begin
g[i+1] : = g[i–1] mod(g[i]);
i : = i +1;
end
gcd : = g[i–1];
/*gcd – результат*/
end

37.

Вычисление обратного элемента по заданному модулю
Если целые числа а и n взаимно просты, то существует
число а', удовлетворяющее сравнению а • а' = 1(mod n).
Число a' называют обратным к а по модулю n и
используют обозначение : a-1(mod n) .
Вычислить а' можно, например, воспользовавшись
представлением наибольшего общего делителя чисел а
и n в виде их линейной комбинации: а*и + n*v = 1.
Взяв наименьшие неотрицательные вычеты обеих
частей этого равенства по модулю n, получим, что
искомое значение а' удовлетворяет сравнению
а' = и (mod n)

38.

Расширенный алгоритм Евклида
При заданных неотрицательных целых числах a и b
этот алгоритм определяет вектор
(u1, u2, u3),
такой, что
a * u1 + b * u2 = u3 = НОД (a, b).
В процессе вычисления используются вспомогательные
векторы (v1, v2, v3), (t1, t2, t3). Действия с векторами
производятся таким образом, что в течение всего процесса
вычисления выполняются соотношения
a * t1 + b * t2 = t3, a * u1 + b * u2 = u3,
a * v1 + b * v2 = v3.

39.

Для вычисления обратной величины
a–1 (mod n)
используется частный режим работы расширенного
алгоритма Евклида, при котором b = n, НОД (a,n) = 1, и
этот алгоритм определяет вектор
(u1, u2, u3),
такой, что
u3 =1, a * u1 + n * u2 = НОД (a,n) =1,
(a * u1 + n * u2) mod n a * u1 (mod n) 1,
a–1 (mod n) u1 (mod n).

40.

Шаги алгоритма:
1. Начальная установка.
Установить (u1, u2, u3) : = (0, 1, n),
(v1, v2, v3) : = (1, 0, a).
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.

41.

Пример. Заданы модуль n = 23 и число a = 5.
Найти обратное число a–1 (mod 23), т.е. x = 5–1 (mod
23).
Используя расширенный алгоритм Евклида, выполним
вычисления, записывая результаты отдельных шагов
табл.
q П.3. u1
u2
u3
v1
v2
v3
–
4
1
1
–
0
1
–4
5
–9
1
0
1
–1
2
n = 23
5
3
2
1
1
–4
5
–9
0
1
–1
2
a=5
3
2
1
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).

42.

q
u1
–
4
1
1
–
0
1
–4
5
–9
u2
1
0
1
–1
2
u3
n = 23
5
3
2
1
v1
v2
1
–4
5
–9
0
1
–1
2
v3
a=5
3
2
1
При u3 =1, u1 = –9, u2 = 2
(a * u1 + n * u2 ) mod n = (5 * (– 9) + 23 * 2) mod 23 =
= 5 * (– 9) mod 23 1,
a–1 (mod n) = 5–1 (mod 23) = (– 9) mod 23 = (– 9 + 23) mod 23
= 14.
Итак, x = 5–1 (mod 23) 14 (mod 23) = 14.

43.

Малая теорема Ферма
Если m – простое число, и a не кратно m ,то малая теорема
Ферма утверждает:
a
m 1
1 mod m

44.

Функция Эйлера
Приведенной системой вычетов по модулю п называют
подмножество полной системы вычетов, члены которого
взаимно просты с п.
Например, приведенную систему вычетов по модулю 12
составляют числа {1, 5, 7, 11}.
Если п - простое число, в приведенную систему вычетов по
модулю п входит всё множество чисел от 1 до п— 1.
Для любого n, не равного 1, число 0 никогда не входит в
приведенную систему вычетов.

45.

Функция Эйлера, которую иногда называют функцией «фи»
Эйлера и записывают как φ(п), указывает число элементов в
приведенной системе вычетов по модулю п.
Иными словами, φ(п) - это количество положительных целых
чисел, меньших п и взаимно простых с п (для любого n,
большего 1).
Если п — простое число, то φ(п) = п-1.
Если n = pq, где р и q - простые числа, то φ(п) = (р-1)(q-1).

46.

В соответствии с обобщением Эйлера малой теоремы Ферма,
если НОД(а,п) = 1,то:
a
j (n)
mod n 1
Теперь нетрудно вычислить а-1 mod n:
1
a a
j ( n ) 1
mod n

47.

Основные способы нахождения обратных величин
a–1 (mod n).
1. Проверить поочередно значения 1, 2, ..., n – 1, пока не
будет найден a–1 (mod n), такой, что a*a–1 (mod n) 1.
n=Prime[number];
a= Mod[b, n]
Do[,]
While[,]
For[,]
If[,]
Break[]

48.

2. Если известна функция Эйлера j(n), то можно
вычислить
a–1 (mod n) aj(n)–1 (mod n),
используя алгоритм быстрого возведения в степень.
EulerPhi[n];
PowerMod[a,b,n] = ab mod n.

49.

3. Если функция Эйлера
j(n) не известна,
использовать расширенный алгоритм Евклида.
n=23
a=5
ExtendedGCD[n,a]
In [ 3 ] : =
O u t[3 ]=
можно
g321 ExtendedGCD 23, 5
2, 9
1,
In [ 2 ] : =
ExtendedGCD 23, 5
O u t[2 ]//M a tr ix F o r m =
1
2, 9
In [ 4 ] : =
O u t[4 ]=
g321
9
2, 2
MatrixForm

50.

3. Если функция Эйлера
j(n) не известна,
использовать расширенный алгоритм Евклида.
n=23
a=5
ExtendedGCD[n,a]
можно
{1,{2,-9}}
u3 =1, u2 = 2 ,u1 = –9
5–1 (mod 23) = (– 9) mod 23 = (– 9 + 23) mod 23 = 14.
Mod[-9,23]
14
In [ 1 ] : =
O u t[1 ]=
PowerMod 5, 1, 23
14

51.

Для решения более сложных сравнений
a * x b (mod n), т.е. b 1, x = ?
используется
сравнение
следующий
прием.
Сначала
a * y 1 (mod n),
т.е. определяют
y = a–1 (mod n),
а затем находят
x = a–1 b (mod n) = y * b (mod n).
решают