asyan.org
добавить свой файл
1 2 ... 6 7
Алгоритмічні основи криптології

Лагун Андрій Едуардович

17/9/09 14:23

Лекція №1

Основні поняття і теореми

Відображення


Задано дві множини X та Y. Нехай кожному ел-ту мн-ни X поставлено деякий елемент y=f(x) множини Y. В такому випадку задано відображення або ф-я f:X->Y із множини X у множину Y.

Відобаження f:X->Y називається ін'єктивним, якщо воно різним аргументам співставляє різні значення:

,

Відображення з X в Y — сур'єктивне, якщо кожен елемент множини Y має праображ — такий ел-т x, що f(y)=x.

Бієктивним є відображення,яке ін'єктивне і сур'єктивне одночасно.

Тотожне відображення позначається залишає елементи x на своїх місцях .

Відображення назив. відображенням лівим оберненим до f:X->Y, за умови, що композиція є тотожним відображенням, і правим оберненим .

Відображення g називається оберненим до f, якщо воно є одночасно і лівим і правим оберненим до f.
^

Властивості оберненого відображення


1. Відображення f:X->Y ін'єктивне тоді і тільки тоді, коли до нього існує ліве обернене.

2. Від. f:X->Y сур'єктивне тоді і тільки тоді, коли до нього існує праве обернене.

3. Якщо відображення f:X->Y бієктивне, то його ліве обернене збігається з правим оберненим.

4. У випадку, якщо множини X та Y — скінчені, і містять однакову к-ть елементів, то відображення f:X->Y має ліве обернене тоді і тільки тоді, коли воно має праве обернене.

Групи


Групою називається множина G, наділена бінарною операцією * з такими властивостями:

1. — асоціативність

2. В G існує нейтральний елемент e такий, що

3. Для кожного елемента x групи G іс

Якщо підмножина H мн-и G утворює групу, відносно тієї ж операції *, то вона називається підгрупою групи G. Напр., множина раціональних чисел Q утворює групу за додаваням, якій нейтральний елемент 0, а обернений — протилежний, а множина цілих чисел Z є її підгрупою. Множина ++их раціональних чисел утворює групу за множенням:

e=1,

Якщо групова операція — множення, то група називається мультиплікативною, її нейтральний елемент є 1-ця, якщо операція ++я, група називається адетивною, нейтральний елемент, а обернений — протилежний елемент.

Для ел-та x групи G =x*x*x, де операція * виконана x-1 раз. В адетивній формі . Для кожного ел-та x скінченої групи для деякого показника m виконується рівність . Найменше з таких m називається порядком ел-та x в групі G. Порядком скінченої групи називається к-ть її елементів. Всі степені ел-та групи утворюють в ній підгрупу, порядок якої = порядку елемента.

Нехай маємо 2 групи G і G' з операціями * і відповідно. Відображення f:G->G' зберігає операцію, якщо . Таке відображення називається гомоморфізмом з групи G в групу G'. Ядром гомоморфізму f:G->G' є мн-а всіх ел-ів G в які f відображає нейтральний ел-т групи G'. Наприклад, відображення, яке кожному цілому числу ставить у відповідність його остачу від ділення наснатуральне n є гомоморфізмом з адетивної групи в адетивну групу , ядро якого утворює цілі числа кратні n.

Ядро гомоморфізму f:G->G' утворює в G підгрупу. Гоморфізм f:G->G' є ін'єктивним <=>, коли його ядро складається з нейтрального елемента групи G. Таке ядро називається тривіальним.

Гомоморфізм, який є бієктивним відображенням називається ізоморфізмом. Напр., двійковий логарифм задає ізоморфізм з мультиплікативної групи невід'ємних дійсних чисел в адетивну групу всіх дійсних чисел .

Для груп G1 і G2 з операція * і відповідно, позначається їх прямий добуток. Множина пар (x1, x2), де із покомпонентним. Результатом виконання операцій з компонентами x та y множин G вважається ел-т:. Група називається комутативною або абелевою, якщо групова операція має властивість комутативності:

Якщо кожен ел-т групи G є степенем її ел-та g, то цей ел-т називається твірним. Якщо група G має порядок n, то g є її твірним ел-том тоді і тільки тоді, коли його порядок також = n. Група, яка має твірний елемент називається циклічною.



следующая страница >>