Rossiya Federatsiyasi Ta'lim va fan vazirligi Oliy kasbiy ta'lim davlat ta'lim muassasasi

2.2 Katta butun sonlar uchun faktorizatsiya masalasi

Katta butun sonlarni faktorlarga ajratish masalasi bu sonlarning tub bo‘luvchilarini izlashni o‘z ichiga oladi. Taxminlarga ko'ra, muammoni hal qilish qiyin, chunki etarlicha ko'p sonlar uchun uni hal qilish uchun katta vaqt sarflanishi kerak.
Hozirgi vaqtda ushbu muammoni hal qilish uchun ko'plab algoritmlar mavjud. An'anaviy ravishda ularni ikki guruhga bo'lish mumkin: eksponensial algoritmlar (mumkin bo'luvchilarni sanab o'tish, Fermaning faktorizatsiya usuli, Pollard p-algoritmi, Lenstra algoritmi va boshqalar) va subeksponensial algoritmlar (Dikson algoritmi, davomli kasr usuli, kvadratiklash va boshqalar). ).
Har bir guruhning algoritmlaridan birini ko'rib chiqing: p-algoritmi va kvadratik elak usuli.
P-algoritmi 1975 yilda Jon Pollard tomonidan butun sonlarni faktorizatsiya qilish muammosini hal qilish uchun taklif qilingan. Algoritmning mohiyati elementlari ma'lum n sonidan boshlab tsiklni tashkil etuvchi sonli ketma-ketlikni qurishdan iborat.
() takomillashtirilgan algoritm yozish.
G[ y 1)mod N, bu yerda N faktorlarga ajratiladigan son. Keyin agar xj - ) 0(mod p), u holda (f(xj) - f(xt)) = 0(mod p).
Bundan kelib chiqadiki, agar ( Xi,xj juftligi yechim bersa, u holda (xt+k, xj+k) juftligi
Shunga ko'ra, biz Xi, x, raqamlar juftligini tekshirish bilan cheklanamiz .


Robert V. Floyd tomonidan ishlab chiqilgan Pollard p-algoritmining yana bir o'zgarishi mavjud. Robert V. Floydning so'zlariga ko'ra , y ning qiymati har bir qadam bilan formula bo'yicha yangilanadi: y = F ² (y) = i bosqichda biz Xi = ni olamiz.
X2i F ^2l (xo) •
Endi subeksponensial algoritmni ko'rib chiqaylik - 1981 yilda K. Pomeranz tomonidan ishlab chiqilgan kvadratik elak usuli. Algoritm universaldir, chunki uning bajarilish vaqti uning maxsus tuzilishi va xususiyatlariga emas, balki faqat faktorlashtirilgan raqamning o'lchamiga bog'liqdir [8].
() algoritmni yozamiz .
^{Eff BE7} T ^T ( bundan buyon matnda L(n) deb yuritiladi ) kattalik tartibidagi P va A chegaralarini shunday tanlaymizki, P < A < P ²
2-bosqich. t = [46] + 1, + 2, ..., [mb] + A uchun ustunga t ² - n butun sonlarni tartibda yozing.
3-bosqich . ) Har bir toq tub son r R uchun Legendre belgisini hisoblaymiz. Shu bilan birga, biz shartni tekshiramiz - = 1. Agar qoniqtirilmasa, u holda p faktorlar bazasidan chiqariladi.
4-qadam. P shunday toq tub son bo'lsinki, n kvadrat qoldiq (mod p), keyin tenglamani yechamiz t ² n( mod p ^V ), bu erda = 1,2, . ... p ning qiymatlari o'sish tartibida qabul qilinadi, toki bu tenglama p modulida [Mb] + 1 [46] + A mintaqasidagi biron bir raqam bilan taqqoslanadigan yechimga ega emas.
,B ko'rsatilgan sohada t ² n(mod r ^R ) bo'lgan shunday t soni mavjud bo'lgan sonlarning eng kattasi bo'lsin.
C1 va t2 yechimlar t ² n( mod p ⁱⁿ ) va t2 -t1 (mod p ⁱⁿ ) bo‘lsin.
5-bosqich. 2-bosqichda olingan t ² - n natijalari p ning bir xil qiymatida ko'riladi. P ga mos keladigan ustunda u barcha t ² - n ga qarshi joylashtiriladi, buning uchun t t1 dan p ning bir necha karrali bilan farq qiladi. Shundan so'ng, t ² - n ning barcha qiymatlari uchun 1 2 ga almashtiriladi, shunda t t1 dan p ning ko'paytmasi bilan farq qiladi va hokazo.
Keyin t2 bilan ham xuddi shunday qilinadi. Ustundagi mumkin bo'lgan eng katta raqam
6-bosqich. Raqamga keyingi birlikni qo'shganda 5-bosqichda olingan ustunda mos keladigan son t ² - n p ga bo'linadi va natija saqlanadi.
7-bosqich. n 1 (mod 8) uchun p \u003d 2 ostidagi ustunda biz 1 qarama-qarshi t ² - n ni toq t bilan qo'yamiz va mos keladigan t ² - n 2 ga bo'linadi. N 1 uchun (mod 8), tenglama t ² - n ( mod 2( ³ ) va yechim toq p bilan bir xil tarzda davom etadi.
Bosqich 8. Natijada, P dan oshmaydigan barcha tub sonlar uchun biz t ² - n raqamlarini istisno qilamiz, P ning barcha darajalari bo'yicha bo'lingandan keyin 1 ga aylanganlar bundan mustasno. Natijada, jadval. olinadi, bunda bi ustunda faqat t (KL] + 1 t + A) qiymatlari mavjud bo'lib, t ² - n B raqam bo'ladi, qolgan ustunlar esa n kvadrat qoldiq bo'lgan p P qiymatlariga mos keladi. .
9. Keyinchalik, umumlashtirilgan Ferma faktorizatsiya usuli (omilli asos usuli) qo'llaniladi.