Texnologiyalari universiteti kriptografiyaning matematik asoslari

2.2. Akslantirishlar

Akslantirishlar berilgan to‘plamlar ustida amallar bajarish bilan ularning elementlari orasida moslik o‘rnatish jarayonini ifodalaydi. Akslantirishlarning xossalarini tahlil qilish bilan bog‘liq bo‘lgan ayrim tushuncha va ta’riflarni keltiramiz.
Berilgan _-akslantirish (funksiya) X - to‘plamni Y - to‘plamga bir qiymatli akslantiradi deyiladi (va _: X _ Y ko‘rinishda belgilanadi), agarda har bir xX elementga faqat bitta y _(x)_Y element mos qo‘yilsa. Bu yerda X - to‘plam _akslantirishning aniqlanish sohasi, Y - to‘plam esa qiymatlar sohasi, y-element xelementning aksi, x-element y-elementning asli deyiladi.
Agarda berilgan _ va _ akslantirishlarning aniqlanish va qiymatlar sohalari to‘la ustma-ust tushib, x X element uchun xx tenglik bajarilsa, bunday akslantirishlar teng deyiladi.
Ushbu _: X _Y akslantirish berilgan bo‘lsin, u holda : X ^' Y akslantirish _ akslantirishning X ^'  X to‘plamdagi izi deyiladi, agarda _x _ X ^' uchun xx tenglik o‘rinli bo‘lsa.
Berilgan _: X _Y akslantirish uchun:

1. 
   ixtiyoriy xX uchun x yY element mavjud bo‘lib, ba’zi y Y elementlar uchun _^1 y_ x tenglikni qanoatlantiruvchi xX elementlar mavjud bo‘lmasa, bunday akslantirish syuryektiv yoki ustiga akslantirish deyiladi;
   
2. 
   x₁  x₂bo‘lgan x₁,x₂  X elementlar uchun y₁ x₁x₂ y₂ shu kabi bo‘lsa, bunday akslantirish inyektiv akslantirish deyiladi.
   
3. 
   bir paytning o‘zida ham syuryektivlik ham inyektivlik shartlari bajarilsa,
   

bunday akslantirish biyektiv yoki o‘zaro bir qiymatli akslantirish deyiladi.
Ushbu _: X _ Y va _: Y _ Z akslantirishlarning ko‘paytmasi
(kompozisiyasi, superpozisiyasi) deb, _x__x tenglikni qanoatlantiruvchi
: X  Z akslantirishga aytiladi hamda _{} ko‘rinishda ifodalanadi.
: X _ X akslantirish X - to‘plamni o‘zini-o‘ziga akslantirish
deyiladi.
x_ X element uchun Ix_ x tenglikni qanoatlantiruvchi
X - to‘plamni o‘zini-o‘ziga akslantiruvchi I - akslantirish birlik (aynan) akslantirish deyiladi.
Agar  I shart bajarilsa, berilgan : X  Y va : Y  X -
akslantirishlar o‘zaro teskari akslantirishlar deyiladi hamda _^1 _, _^1 _ deb yoziladi.
Teskarisi mavjud bo‘lmagan akslantirishlar bir tomonlama akslantirishlar
deyiladi.
Biror xX element uchun x x tenglik bajarilsa, bu element _
akslantirishning qo‘zg‘almas elementi deyiladi.
Elementlari soni n ta bo‘lgan X - to‘plamni o‘zini-o‘ziga biyektiv akslantiruvchi _- akslantirish X - to‘plamda n-darajali o‘rniga qo‘yish deyiladi.
Agarda to‘plam X  x₁,,x_n bo‘lsa, u holda _- akslantirish quyidagicha:
 x₁ ,, x_n  x₁,,x_n 
 x1 ,,xn  =xi1 ,,xin  ,
yoziladi, bu yerda i₁ ,,i_n  - indekslar 1,2,,n- sonlarning o‘rin almashtirishlaridan iborat.
Agarda o‘rniga qo‘yish akslantirishi _ ushbu _^1 _ tenglikni qanoatlantirsa, u holda bu akslantirish involyusiya deyiladi.
X -to‘plamni o‘zini-o‘ziga akslantiruvchi _- o‘rniga qo‘yish akslantirishi x_i ,x _j  X elementlar uchun x_i  x _j va _x _j  x_i tengliklarni qanoatlantirib, X -
to‘plamning boshqa elementlari bu akslantirishga nisbatan qo‘zg‘almas elementlar bo‘lsa, bunday _-akslantirish x_i va x _j elementlarning X -to‘plamdagi transpozisiyasi deyiladi.

2.3. Binar munosabatlar

Istalgan ikkita X va Y to‘plam uchun barcha O _ X _Y qism to‘plamlar X va Y to‘plam o‘rtasidagi binar munosabat deb aytiladi [12].
X ga nisbatan ~ binar munosabat ekvivelentlik munosabati deyiladi, agarda barcha x,x₁,x₂ X uchun quyidagi shartlar bajarilsa:

1. 
   x~x (refleksivlik);
   
2. 
   x~x_{1 }x₁~x (simmetriklik);
   
3. 
   x~x₁, x₁~x_{2 }x₂~x (tranzitivlik).
   

Berilgan x ga ekvivalent bo‘lgan barcha elementlar qism to‘plami H={x'_X|x'~x}_X x ni o‘z ichiga olgan ekvivalentlik sinfi deyiladi. x~x (1-shart) bajarilsa, u holda x'_H bo‘ladi. x'_H ning istalgan elementi H sinfining vakili deyiladi.
Teorema. X kesishmaydigan qismto‘plamlar birlashmasi bo‘lib, ~ munosabat bo‘yicha ekvivalentlik sinfi to‘plami uning tarkibiy qismi hisoblanadi.
Isbot. x_H dan X=_H_i kelib chiqadi. So‘ngra ixtiyoriy vakili orqali H
aniqlab olinadi, ya’ni H_i=H_{j } x_i~x_j. Bir tomonga: x_i~x_j va x_H_{i }x~x_ix~x_jx_H_jH_i H_j bajariladi. Ammo x_i~x_j^x_j~x_i (2-shart). bo‘lgani uchun H_j H_i bajariladi. Demak H_j=H_i ya’ni x_H bo‘lsa, u holda
Hi=HxHix~xi.
AgarH _j  H_i   va xH _j  H_i bo‘lsa, u holda x~x_i va x~x_j bo‘ladi, tranzitivlik shartidan x_i~x_j va H_j=H_i ga ega bo‘linadi.. Demak turli sinflar kesishmaydi. Teorema isbotlandi.
Misol. To‘g‘riburchakli koordinatalar tizimida V=R² – tekislik berilgan bo‘lsin. U holda ~ xossasidan kelib chiqib P, P'_V nuqtalarning biror gorizontal to‘g‘ri chiziqqa tegishliligidan gorizontal to‘g‘ri chiziqlar sinfi bilan ekvivalentlik munosabati kelib chiqadi (2.1 a)-rasm).
xy=p>0 shakldagi Gp giperbola V₊V sohada x>0, y>0 koordinatali P(x,
y) nuqta bilan ekvivalentlik munosabatini aniqlaydi. (2.1 b)-rasm)

a) b)
2.1- rasm. Ekvivalentlik munosabati
2.4. Arifmetikaning asosiy teoremasi
Arifmetika natural sonlar xossalari bilan shug‘ullanuvchi fan bo‘lib, unda qadimdan asosiy e’tibor tub sonlarga qaratilib kelingan. Tub sonlarning fundamental xossasini arifmetikaning asosiy teoremasi ochib beradi [12].
Asosiy teorema. Birdan boshqa ixtiyoriy natural son tub son yoki tub sonlar ko‘paytmasi shaklida yoziladi, agar bu ko‘paytmada ko‘paytuvchilarning o‘rni e’tiborga olinmasa, u holda bu ko‘paytma yagona bo‘ladi.
Bu teorema birinchi qismining sodda isboti Yevklidning VII
“Boshlang‘ich” kitobida keltirilgan va uning to‘la shakli (ko‘paytmaning yagonaligi bilan birgalikda) K.F. Gauss tomonidan berilgan.
Mazkur teoremadan birdan boshqa ixtiyoriy natural son a ning kanonik yoyilmasi
a=p11 p22… pnn shaklida ifodalanishi ayon bo‘ladi. Bu yerda p₁, p₂,…, p_n har xil tub sonlar, ₁, ₂, … , , _n - birga teng yoki undan katta daraja ko‘rsatkichlari, n1.

Nazorat savollari

1. 
   To‘plam deb nimaga aytiladi ?
   
2. 
   Qanday to‘plamlarni bilasiz?
   
3. 
   To‘plamlar juftligi uchun qanday amallar aniqlangan?
   
4. 
   Amallarning asosiy xossalari nimalardan iborat?
   
5. 
   To‘plamning asosiy xossalari nimalardan iborat?
   
6. 
   To‘plamlarni akslantirish deganda nimani tushunasiz?
   
7. 
   Binar munosabatlar deganda nimani tushunasiz?
   
8. 
   Arifmetikaning asosiy teoremasiga ta’rif bering?
   

3. TO‘PLAMLAR USTIDA ALGEBRAIK AMALLAR