Математика. Раздел 1. Дискретная математика. Тетрадь 1. Казанцев Э.Ф. - 11 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

Из при ве ден ных при ме ров вид но, что ал гебр, в прин ци пе, мо жет
быть ог ром ное ко ли че ст во. Осо бен но яс но это вид но из сле дую ще го
при ме ра.
При мер 4: пусть да но мно же ст во
N p
p
= -{ , , , }0 1 2 1K
. Оп ре де лим на
этом мно же ст ве опе ра ции
Å
— («сло же ние по мо ду лю p») и
Ä
— («ум но -
же ние по мо ду лю p») сле дую щим об ра зом:
a b cÅ =
;
a b dÄ =
, где c и d —
ос тат ки от де ле ния на p чи сел
( )a b+
и
( )a b×
со от вет ст вен но. На при мер,
ес ли
p = 7
, то
N
7
0 1 2 3 4 5 6= { , , , , , , }
. То гда
3 4 3 4 7 0Å = + =[( ) ]
(нет ос тат ка);
4 6 4 6 7 3Å = + =[( ) ]
(ос та ток от де ле ния 10 на 7);
3 4 3 4 7 5Ä = × =[( ) ]
(ос та -
ток от де ле ния 12 на 7) и так да лее.
Ес ли p — про стое чис ло, ал геб ра
( ; , )N
p
Å Ä
на зы ва ет ся ко неч ным
по лем ха рак те ри сти ки p. Дан ная ал геб ра на шла свое прак ти че ское при -
ме не ние в со вре мен ной крип то гра фии. Ана ло гич ная ал геб ра на мно же -
ст ве {0,1} —
({ , }; ,&)0 1 Å
— иг ра ет чрез вы чай но важ ную роль в ма те ма ти -
че ской ло ги ке — это ал геб ра Же гал ки на.
При мер 5: ал геб ра Же гал ки на. Ее сиг на ту ра
( ,&)Å
,
p = 2
, опе ра ции
«сло же ние по модулю 2» и конъ юнк ция & — би нар ны, сле до ва тель но
тип ал геб ры — (2,2). Сло же ние по мо ду лю 2 вы гля дит так:
0 1 0 1 2 1Å = + =[( ) ]
,
1 1 1 1 2 0Å = + =[( ) ]
.
Кро ме вы ше при ве ден ных к клас су фун да мен таль ных ал гебр от -
но сят ся так же груп пы, коль ца, по ля, ре шет ки и др.
На вес ти по ря док в этом не обо зри мом мо ре раз лич ных ал гебр по -
мо га ет свой ст во го мо мор физ ма, ко то рым об ла да ют ал геб ры од но го и
то го же ти па. Го мо мор физм — это од но из наи бо лее важ ных по ня тий в
ма те ма ти ке.
Пусть да ны две ал геб ры:
A K
p
= ( ; ; ; )j j
1
K
и
B M
p
= ( ; ; ; )y y
1
K
оди на ко во го ти па. Го мо мор физ мом ал геб ры А в ал геб ру В на зы ва ет ся
ото бра же ние
G :K M®
с со хра не ни ем опе ра ции, удов ле тво ряю щее ус -
ло вию:
( )
[ ]
( ) ( )
[ ]
G G G: , : , , :
( ) ( )
j y
i j j i j j
K K K K
l i l i1 1
K K=
(1)
для всех
i p=1,K
. Здесь
l i( )
— ар ность опе ра ций
j
i
и
y
i
(она долж на быть
оди на ко ва). Смысл ус ло вия (1) со сто ит в том, что ре зуль тат бу дет оди -
на ков не за ви си мо от то го, вы пол не на ли сна ча ла опе ра ция
j
i
в ал геб ре
А и за тем про из ве де но ото бра же ние G в ал геб ру В, ли бо сна ча ла про из -
11
     Из приведенных примеров видно, что алгебр, в принципе, может
быть огромное количество. Особенно ясно это видно из следующего
примера.

      Пример 4: пусть дано множество N p = {0, 1, 2, K p -1}. Определим на
этом множестве операции Å — («сложение по модулю p») и Ä — («умно-
жение по модулю p») следующим образом: a Å b = c; a Ä b = d, где c и d —
остатки от деления на p чисел (a + b) и (a × b) соответственно. Например,
если p = 7, то N 7 = {0,1,2,3, 4,5,6}. Тогда 3 Å 4 = [(3 + 4) 7] = 0 (нет остатка);
4 Å 6 = [(4 + 6) 7] = 3 (остаток от деления 10 на 7); 3 Ä 4 = [(3 × 4) 7] = 5 (оста-
ток от деления 12 на 7) и так далее.
       Если p — простое число, алгебра (N p ; Å, Ä) называется конечным
полем характеристики p. Данная алгебра нашла свое практическое при-
менение в современной криптографии. Аналогичная алгебра на множе-
стве {0,1} — ({0,1}; Å, &) — играет чрезвычайно важную роль в математи-
ческой логике — это алгебра Жегалкина.

      Пример 5: алгебра Жегалкина. Ее сигнатура (Å, &), p = 2, операции
«сложение по модулю 2» и конъюнкция & — бинарны, следовательно
тип алгебры — (2,2). Сложение по модулю 2 выглядит так:

                     0 Å 1 = [(0 +1) 2] = 1, 1 Å 1 = [(1 +1) 2] = 0.

      Кроме вышеприведенных к классу фундаментальных алгебр от-
носятся также группы, кольца, поля, решетки и др.
      Навести порядок в этом необозримом море различных алгебр по-
могает свойство гомоморфизма, которым обладают алгебры одного и
того же типа. Гомоморфизм — это одно из наиболее важных понятий в
математике.
      Пусть даны две алгебры: A = (K ; j1 ; K ; j p ) и B = (M ; y 1 ; K ; y p )
одинакового типа. Гомоморфизмом алгебры А в алгебру В называется
отображение G:K ® M с сохранением операции, удовлетворяющее ус-
ловию:

         [ (
      G: ji K j1 ,K K jl ( i )   )] = y [G:( K ),K , G:(K )]
                                      i       j1              jl ( i )          (1)

для всех i =1,K p. Здесь l(i) — арность операций j i и y i (она должна быть
одинакова). Смысл условия (1) состоит в том, что результат будет оди-
наков независимо от того, выполнена ли сначала операция j i в алгебре
А и затем произведено отображение G в алгебру В, либо сначала произ-
                                                                                 11

Страницы