|
Isomov Bakhodir Shukhratovichning kriptografiya fanidan tayyorlagan referat
|
| bet | 1/2 | | Sana | 06.01.2024 | | Hajmi | 0,51 Mb. | | #131244 | | Turi | Referat |
Bog'liq referat ishi
O’ZBEKISTON RESPUBLIKASI AXBOROT
TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI
RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY
NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI
071-21-guruh talabasi
Isomov Bakhodir Shukhratovichning
kriptografiya fanidan
tayyorlagan referati
Aniqlashtirilgan va ehtimollikka asoslangan sonlarni tublikka sinash usullari tahlili
Bajardi: Isomov Bakhodir
Tekshirdi: Mardiyev U.R.
2-variant
Reja:
Tub son nima?
Tub sonlarni aniqlashning klasifikatsiyasi.
Aniqlashtirilgan tublikka sinash.
Ehtimollikka asoslangan tublikka sinash.
Matematika hayotda, sonlar orasida bo’linuv xususiyatlari bilan ajralib turuvchi va tub elementlar sifatida turgan raqamlar bilan tanishishimiz kerak. Tub, 1 dan katta butun son bo'lgan, faqat 1 va o'zi bilan bo'linadigan raqamdir. Ya'ni, tubning asosiy ikki xususiy bo’luvchisi bo'lishi kerak: 1 va o'zi. Tub sonini aniqlash uchun uning bo'linuvchilarini ko'rish zarur. Agar raqam faqat 1 va o'ziga bo'linsa, unda bu tub sanalgan hisoblanadi. Masalan, 7 ni ko'rib chiqamiz. Faqat 1 va 7 ni ko'paytirish orqali hosil bo'ladigan butun sonlar faqat 1 va 7. Shuning uchun, 7 tub sonidir. Quyidagi misollarni o'rganish maqsadida ba'zi tub sonlarni ko'ramiz:
2: Eng kichik tub son, faqat 1 va 2 bilan bo'linadi.
5: Yana bir tub son, faqat 1 va 5 ga bo'linadi.
13: Faqat 1 va 13 ga bo'linadi, shuning uchun bu ham tub son.
Tub sonlari matematikda va kriptografiyada muhim ahamiyatga ega. Ularning unikal bo'linish xususiyatlari ma'lumotni xavfsiz ravishda kodlash va dekodlash uchun muhimdir. Raqamlarni tub sonlariga bo'lish orqali, ulardan tashkil topgan, bir raqamning tub tahlili qisqaradi. Xulosa qilib, tub sonlar, ularning ajralib turuvchi xususiyatlari va matematikada asosiy o'riniga ega bo'lishi bilan, raqamlar dunyosidagi go'zallikka ega bo'lgan asosiy qo'shmadir.
Sonni tubligini aniqlovchi ko‘pgina usullar (algoritmlar) mavjud bo‘lib, ular orasida sonlarning ma’lum bir ko‘rinishi yoki strukturasiga bog‘liq bo‘lgan testlar hamda ixtiyoriy sonlar uchun sinov testlari ham mavjud. Ixtiyoriy sonlar uchun ishlab chiqilgan test sinovlari ham nazariy ham amaliy jihatdan katta qiymatga ega.Mavjud tub sonni generatsiyalash algoritmlarida bir marta tasodifan tanlangan sonning eng katta va eng kichik bitlari 1 ga teng qilib olinadi. Eng katta bitning 1 ga teng qilib olinishi tub sonning zarur uzunligini taʼminlasa, eng kichik bitning 1 ga teng boʼlishi uning toqligini taʼminlaydi. Keyin n ning uncha katta boʼlmagan jadvallardan maʼlum boʼlgan: 3, 5, 7, 11, ... tub sonlarga boʼlib koʼriladi. Barcha mavjud tublikka sinash algoritmlarini ikki sinfga bo‘lish mumkin: aniqlashtirilgan testlar - bu sinov natijasida tadqiq etilayotgan son tubmi yo yo‘qmiligining kafolatlangan aniq javobi beriladi; ehtimolli testlar - bu sinovning natijasi yetarlicha katta ehtimollik bilan haqiqiy bo‘ladi. Bitta son uchun turli parametrlar bilan ularning ko‘p martalik takrorlanishi xatolik bo‘lishi ehtimolligini yetarlicha kichik qiymatli qilish imkonini beradi. Tub sonlarni generasiya qilish ochiq kalitli kriptotizimlarni loyihalashda asosiy bosqichlardan biri, chunki ular asosida modul arifmetikasining hal qiluvchi elementi - moduli shakllantiriladi. Tub sonlarni generasiya qilishda qo‘llaniladigan barcha algoritmlar ma’lum ehtimollik bilan tub sonni hosil qiladi. Bunda tublikka sinash algoritmlaridan foydalaniladi va ular hal qiluvchi ahamiyat kasb etadi. Sinash algoritmlari qanchalik ko‘p “tublik guvohlari”ni ko‘rsatsalar, sinalayotgan n sonining tub bo‘lish ehtimolligi shunchalik katta bo‘ladi. Odatda, katta tub sonlarni generasiya qilishda quyidagi yondoshuvdan foydalaniladi: 1. Tasodifan berilgan uzunlikdagi (bitlar soni bo‘yicha) toq son n tanlanadi. 2. Tublikka sinash (test) o‘tkaziladi. 3. Agar 𝑛 murakkab son bo‘lsa, u holda 1-qadamga qaytiladi.
Aniqlashtirilgan testlar - bu sinov natijasida tadqiq etilayotgan son tubmi yo yo‘qmiligining kafolatlangan aniq javobi beriladi. Ushbu testlar sinfiga Mersenne tub sonlarni tekshirish uchun testi kiradi. Kiruvchi: Tub son p.
Topish: Mp = 2p − 1 ni hisoblang. Ketma-ketlikni tuzing: {si} ketma-ketlikni quyidagi tartibda yaratish: si = s2i−1 − 2, s0 = 4 bo'yicha, to p − 2 gacha i = p − 2 bo'lguncha davom ettirilsin.Agar sp−2 ≡ 0 (mod Mp) bo'lsa, "Mp tub"ni qaytaring. Aks holda, "Mp composite"ni qaytaring. Diqqat qiling, ketma-ketlik doimiy bo'lsa-da, si sonini hisoblash uchun kerak bo'lgan sanalar soni p o'lchamiga bog'liq. Bu, demak, 2-qadamda, s0 = 4 bilan boshlanadi va si = s2i−1 − 2 (mod Mp) p − 2 marta takrorlanadi. To'g'ri bo'lish sp−2 ≡ 0 (mod Mp) ⇐⇒ Mp tub bo'lishini isbotlash uchun, ω = 2 + √3 va ω = 2 − √3 ni aniqlab olishimiz kerak. Endi ω = ω2n + ω2n, bu yerda L0 = ω1 + ω1 = 4. Bundan tashqari, Ln+1 = ω2n+1 + ω2n+1 ni aniqlashimiz kerak. ωω = (2 + √3)(2 − √3) = 1 bo'lganidan, oxirgi tenglama ω2n+1 + ω2n+1 + 2ω2nω2n − 2 = (ω2n + ω2n+1)2 − 2 = L2n − 2 ga o'tkazilishi mumkin. Bu, Ln va si ning bir xil ketma-ketliklar bo'lishi kerakligini anglatadi. Endi, bu Ln ni isbatlash uchun uni theoremning har ikki tomonini ham ishlatishimiz mumkin. "⇐": Mp = 2p − 1 bo'lgan qiymatlarga ega a + b√3 shaklidagi sonlar guruhi ko'rib chiqamiz (mod Mp). Bizga AKS algoritmning isbotidan sabab, (1 + √3)Mp ≡ 1 + √3 Mp (mod Mp) = 1+ √ √3 3 √3 Mp (mod Mp) = 1+(√3)3 Mp−1 2 (mod Mp). Kvadrat reciprocality qonuni orqali, 3 Mp−1 2 ≡ ±1 (mod Mp). Endi to'g'ri belgilash kerak bo'lgan alamatni aniqlashimiz. Mp va 3 mod 4 ga mos kelganda, kvadrat reciprocality qonuni bizga ayta, yoki Mp tub son yoki 3 tub son o'rniga bo'lishi mumkin. Bizda Mp ≡ 1 (mod 3), shuning uchun Mp tub son (mod 3) va shu sababli 3 Mp−1 2 ≡ −1 (mod Mp). Bu demak, (1+√3)Mp ≡ 1− √3 (mod Mp). Endi biz ildizni (1+ √3) bilan ko'paytirishimiz kerak, bu bizga (1+√3)Mp+1 ≡ −2 (mod Mp) ni beradi. Biz ham (1+√3)2 = (4+2√3) = 2ω deb yozishimiz mumkin, bu esa (1 + √3)Mp+1 ni (2ω) Mp+1 2 = 2 Mp+1 2 ω Mp+1 2 = 212 Mp−1 2 ω Mp+1 2 ≡ −2 (mod Mp) ga aylantiradi. Bizda 2 Mp−1 2 ≡ 1 (mod Mp) sababli, oxirgi tenglamani 12 2ω Mp+1 2 ≡ −2 (mod Mp) deb yozishimiz mumkin. 2 ning Mp ga nisbatan tub son bo'lishi sababli, bu oxirgi tenglama ω Mp+1 2 ≡ −Mp −1 ≡ −1 (mod Mp) ga o'tkaziladi. Biz bu tenglamani ω2p−1+1 2 = ω2p−1 = ω2p−2 ω2p−2 sifatida yozishimiz mumkin, bu esa Mp ga nisbatan −1 (mod Mp) ga teng bo'ladi. Hozir, biz bu tenglamani ω2p−2 bilan ko'paytirib olishimiz kerak, bu esa ω2p−2 + ω2p−2 ≡ sp−2 ≡ 0 (mod Mp) ga o'tadi. "⇒": Mp sp−2 ni bo'ladigan qilish, ya'ni, CMp = ω2p−2 + ω2p−2. Biz bu tenglamani ω2p−2 bilan ko'paytirib olishimiz mumkin, shu bilan ω2p−1 = CMpω2p−2 − 1. Uning o'ng tarafini ko'paytirish uchun uni kvadratga olib yuboramiz, va bizga ω2p = (CMpω2p−2 − 1)2 ni olishimiz kerak. Mp tub son emas deb faraz qilamiz, bu esa, q < p Mp bo'lgan bo'lsa. Biz G sonlar guruhiga barcha q ni mod q bo'yicha invertib sonlar ekanligini ko'ramiz va ko'rishimiz kerak, chunki |G| ≤ q2 − 1 (0 ni invertib son sifatida o'z ichiga olmaydi).
U shbu test qo’llash uchun foydalaniladigan algoritm:
Adabiyotlar Ro'yhati
|
| |
