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.
