|
Masalan,
Ushbu fokuslar hisoblash uchun qulay bo'ladi
Asosiy faktorizatsiya murakkabligi
|
| bet | 2/3 | | Sana | 18.05.2024 | | Hajmi | 4,63 Mb. | | #243339 |
Bog'liq shifrlashMasalan,
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.
|
| |
