RSA algoritmi
Quyida RSA algoritmi keltirilgan. Hozircha bizning so'zlarimizni qabul
qilishingiz mumkin, agar biz asosiy faktorizatsiyani qanday samarali qilishni bilsak,
RSA tarix bo'ladi.
Biroq, biz yuqoridagi bir nechta atamalarni tushunishimiz kerak. Eng katta
umumiy bo'luvchi
( gcd )
ikkita son orasidagi eng katta bo'luvchini topadi. Masalan,
Ikkita son umumiy omillarga ega bo'lmasa, birgalikda
tub son
hisoblanadi.
“ mod ”
dasturchilarga tanish boʻlgan modul operatori (masalan, 14 % 10 = 4).
Keling, ba'zi modul hisoblarini ko'rib chiqaylik.
Masalan,
Ushbu fokuslar hisoblash uchun qulay bo'ladi
Asosiy faktorizatsiya murakkabligi
Klassik hisoblash bilan biz asosiy faktorizatsiyani hal qila oladigan eng yaxshi narsa:
bu yerda n - tub sonlar mahsulotini ifodalovchi bitlar soni. Shor algoritmi buni
amalga oshirishi mumkin.
taxminan eshiklar soni bilan
Asosiy faktorizatsiya
Ammo uni hal qilish uchun biz yechimni noodatiy tarzda rasmiylashtirishimiz
kerak. Quyidagi tenglamalar yordamida 21 ning tub omillarini topamiz. Sehrli
tarzda, bu tenglamalar bizning javobimiz bo'lgan 7 va 3 raqamlari bilan tugaydi.
Biroq, bu oddiy omad emas. Ularning orqasida ko'plab matematik nazariyalar
mavjud. Asosiy g'oya - kvadrati pastdagi o'ngdagi atamaga teng bo'lgan raqamni
(bizning holatda 8) topishdir.
Shunday ekan, keling, omadimizni yana bir bor sinab ko'ring. X = 2 tasodifiy
taxmin bilan boshlang . Birinchidan, biz x va N ko'p tub ekanligini bilmoqchimiz .
Buni Evklid algoritmi yordamida amalga oshirish mumkin . Quyida 21 dan 15 gacha
bo'lgan umumiy omilni topishga misol keltirilgan.
Shunday qilib, 3 21 va 15 uchun umumiy koeffitsient bo'lib, shuning uchun
21 va 15 umumiy son emas. Agar x va 21 birgalikda tub bo'lmasa, gcd(x, 21) asosiy
omillardan biri bo'ladi va biz tugatdik. Ammo bu haqiqiy muammoda tez-tez sodir
bo'lishini kutmang. Katta ehtimol bilan, x N bilan birga tub sondir . Endi biz
quyidagi kuchlar funksiyasini hisoblaymiz.
ya'ni x=2 bilan .
Bu funksiya 6 ( r = 6 ) davriga ega , ya'ni funksiya qiymatlari har 6 ta qiymatda
takrorlanadi. Agar r 2 ga bo'linsa, u 3 ga aylanadi. Biz xohlagan 8 raqami oddiygina
pow(2, 3), ya'ni . pow(x, 3) .
Xulosa qilib aytganda, biz taxmin qilishdan boshlaymizda u bilan birgalikda
ishlayotganligini tekshiring. Agar yo'q bo'lsa, biz asosiy omillarni topish uchun gcd
dan foydalanamiz. Aks holda, quvvat funksiyasining davrini hisoblaymiz.
Agar r davri juft bo'lsa, biz qidirayotgan raqam pow(x, r/2) - quyida qizil rang
bilan chizilgan. Agar r juft bo'lmasa, biz x bo'yicha yana bir taxmin qilamiz va
qaytadan urinib ko'ramiz.
Amalda, siz davrni tenglashtirish uchun juda teng imkoniyatga ega bo'lishingiz
kerak.
N = 15
uchun vaziyatni ko'rib chiqing . Bizda ... bor
X
ning juda ko'p tanlovi bizni to'g'ri echimga olib boradi. Imkoniyatlar juda qulay.
Qiyin qism modul funksiyasining davrini topishdir. Shor algoritmi bizni
Cheklangan xatolik ehtimoli polinom vaqti (BPP) deb nomlangan algoritmlar
sinfiga olib boradi. Murakkablik nazariyasida biz eng yomon stsenariy uchun
murakkablikni hisoblaymiz, aytaylik
O(n)
. Amalda, eng yomon vaziyat senariysi
hali ham eksponent bo'lsa ham (lekin imkoniyat odatda juda kichik) ko'p nomli
vaqtda yechim topish umumiy norma bo'lgan muammolar mavjud.Afsuski,
yuqoridagi modul funksiyasining davrini topish klassik hisoblash yordamida
osonlikcha hal etilmaydi. Bu erda kvant hisoblash keladi. Quyidagi funktsiyaning
davri bir marta
kvant hisoblash orqali topiladi va u teng, biz
gcd ni
hisoblaymiz . Buni biz avval
muhokama qilganimizdek, Evklid algoritmi yordamida osonlik bilan bajarish
mumkin
.
Ammo davrni aniqlash usulini tushunish uchun birinchi navbatda bir nechta asosiy
tushunchalarni qamrab olishimiz kerak.
Endi IBMni Kvant labaratoriyasida davom etiramiz.
|
