Cantor-Zassenhaus algoritmi - Cantor–Zassenhaus algorithm

Yilda hisoblash algebra, Cantor-Zassenhaus algoritmi faktoring uchun usul polinomlar ustida cheklangan maydonlar (Galois dalalari deb ham ataladi).

Algoritm asosan darajalashtirish va polinomdan iborat GCD hisoblashlar. U tomonidan ixtiro qilingan Devid G. Kantor va Xans Zassenxaus 1981 yilda.

Muammoni hal qilish uchun dominant algoritm, shubhasiz, avvalgisini almashtirgan Berlekamp algoritmi Hozirda ko'pchilikda amalga oshirilmoqda kompyuter algebra tizimlari.

Umumiy nuqtai

Fon

Cantor-Zassenhaus algoritmi kvadrat shaklida polinomni kiritadi ${displaystyle f (x)}$ (ya'ni takrorlanadigan omillarga ega bo'lmagan) daraja n cheklangan maydonda koeffitsientlar bilan ${displaystyle mathbb {F} _ {q}}$ kimning kamaytirilmaydigan polinom omillar teng darajadagi (algoritmlar o'zboshimchalik polinomlarini ushbu shartlarni qondiradigan polinomlar mahsulotiga samarali ravishda faktor qilish uchun mavjud, masalan, ${displaystyle f (x) / gcd (f (x), f '(x))}$ kabi koeffitsientlarga ega kvadratik polinom ${displaystyle f (x)}$ , shuning uchun Kantor-Zassenxaus algoritmidan ixtiyoriy ko'pburchaklarni omil qilish uchun foydalanish mumkin). Chiqish sifatida polinom beradi ${displaystyle g (x)}$ bir xil sohadagi koeffitsientlar bilan shunday ${displaystyle g (x)}$ ajratadi ${displaystyle f (x)}$ . Keyinchalik, algoritm ushbu va keyingi bo'luvchilarga rekursiv ravishda qo'llanilishi mumkin ${displaystyle f (x)}$ kamaytirilmaydigan polinomlarning kuchlariga ( uzuk har qanday maydon bo'yicha polinomlarning soni a noyob faktorizatsiya domeni ).

Mumkin bo'lgan barcha omillar ${displaystyle f (x)}$ ichida joylashgan faktorli uzuk ${displaystyle R = {frac {mathbb {F} _ {q} [x]} {f (x) burchak burchagi}}}$ . Agar shunday deb taxmin qilsak ${displaystyle f (x)}$ kamaytirilmaydigan omillarga ega ${displaystyle p_ {1} (x), p_ {2} (x), ldots, p_ {s} (x)}$ , hamma daraja d, keyin bu omil halqasi uchun izomorfik bo'ladi to'g'ridan-to'g'ri mahsulot omil halqalari ${displaystyle S = prod _ {i = 1} ^ {s} {frac {mathbb {F} _ {q} [x]} {langle p_ {i} (x) burchak}}}$ . Dan izomorfizm R ga S, demoq ${displaystyle phi}$ , polinomni xaritada aks ettiradi ${displaystyle g (x) R}$ uchun s- uning kamayishining moduli har birining moduli ${displaystyle p_ {i} (x)}$ ya'ni, agar:

{Displaystyle {egin {aligned} g (x) & {} equiv g_ {1} (x) {pmod {p_ {1} (x)}}, g (x) & {} equiv g_ {2} (x) ) {pmod {p_ {2} (x)}}, & {} vdots g (x) & {} equiv g_ {s} (x) {pmod {p_ {s} (x)}}, end { tekislangan}}}

keyin ${displaystyle phi (g (x) + langle f (x) burchak) = (g_ {1} (x) + langle p_ {1} (x) burchak, ldots, g_ {s} (x) + langle p_ {s) } (x) burchak)}$ . Shu o'rinda quyidagilarni ta'kidlash zarur, chunki u keyinchalik algoritmda juda muhim ahamiyatga ega bo'ladi: beri ${displaystyle p_ {i} (x)}$ har biri kamaytirilmaydi, bu to'g'ridan-to'g'ri yig'indidagi omil halqalarining har biri aslida maydon. Ushbu maydonlarning har biri ilmiy darajaga ega ${displaystyle q ^ {d}}$ .

Asosiy natija

Cantor-Zassenhaus algoritmi asosida yotgan asosiy natija quyidagicha: Agar ${displaystyle R (x)$ qoniqarli polinom:

{displaystyle a (x) eq 0, pm 1}

{displaystyle a_ {i} (x) {0, -1,1} {ext {for}} i = 1,2, ldots, s,}

qayerda ${displaystyle a_ {i} (x)}$ ning kamayishi hisoblanadi ${displaystyle a (x)}$ modul ${displaystyle p_ {i} (x)}$ oldingi kabi, va agar quyidagi uchta to'plamning ikkitasi bo'sh bo'lmasa:

{displaystyle A = {imid a_ {i} (x) = 0},}

{displaystyle B = {imid a_ {i} (x) = - 1},}

{displaystyle C = {imid a_ {i} (x) = 1},}

unda quyidagi ahamiyatsiz omillar mavjud ${displaystyle f (x)}$ :

{displaystyle gcd (f (x), a (x)) = prod _ {iin A} p_ {i} (x),}

{displaystyle gcd (f (x), a (x) +1) = prod _ {iin B} p_ {i} (x),}

{displaystyle gcd (f (x), a (x) -1) = prod _ {iin C} p_ {i} (x).}

Algoritm

Cantor-Zassenhaus algoritmi bir xil turdagi polinomlarni hisoblaydi ${displaystyle a (x)}$ Yuqorida Fon qismida muhokama qilingan izomorfizm yordamida. Maydon qaerda bo'lsa, u quyidagicha davom etadi ${displaystyle mathbb {F} _ {q}}$ g'alati xarakterga ega (jarayonni to'g'ridan-to'g'ri xarakterli 2 maydonga umumlashtirish mumkin). Tasodifiy polinomni tanlang ${displaystyle b (x) R}$ shu kabi ${displaystyle b (x) eq 0, pm 1}$ . O'rnatish ${displaystyle m = (q ^ {d} -1) / 2}$ va hisoblash ${displaystyle b (x) ^ {m}}$ . Beri ${displaystyle phi}$ bu izomorfizm, bizda (hozir o'rnatilgan belgi yordamida):

{displaystyle phi (b (x) ^ {m}) = (b_ {1} ^ {m} (x) + langle p_ {1} (x) burchak, ldots, b_ {s} ^ {m} (x) + langle p_ {s} (x) burchak).}

Endi har biri ${displaystyle b_ {i} (x) + langle p_ {i} (x) burchak}$ tartib maydonining elementidir ${displaystyle q ^ {d}}$ , ilgari ta'kidlanganidek. Ushbu maydonning multiplikativ kichik guruhi tartibga ega ${displaystyle q ^ {d} -1}$ va shunday, agar bo'lmasa ${displaystyle b_ {i} (x) = 0}$ , bizda ... bor ${displaystyle b_ {i} (x) ^ {q ^ {d} -1} = 1}$ har biriga men va shuning uchun ${displaystyle b_ {i} (x) ^ {m} = pm 1}$ har biriga men. Agar ${displaystyle b_ {i} (x) = 0}$ , keyin albatta ${displaystyle b_ {i} (x) ^ {m} = 0}$ . Shuning uchun ${displaystyle b (x) ^ {m}}$ bilan bir xil turdagi polinom hisoblanadi ${displaystyle a (x)}$ yuqorida. Keyinchalik, beri ${displaystyle b (x) eq 0, pm 1}$ , to'plamlarning kamida ikkitasi ${displaystyle A, B}$ va C bo'sh emas va yuqoridagi GCDlarni hisoblash orqali biz ahamiyatsiz bo'lmagan omillarni olishimiz mumkin. Maydon ustidagi polinomlarning halqasi a bo'lganligi sababli Evklid domeni, biz ushbu GCDlarni. yordamida hisoblashimiz mumkin Evklid algoritmi.

Ilovalar

Cantor-Zassenhaus algoritmining muhim dasturlaridan biri bu hisoblashda alohida logarifmalar asosiy kuch buyurtmasining cheklangan maydonlari ustida. Diskret logarifmlarni hisoblash muhim muammo hisoblanadi ochiq kalit kriptografiyasi. Bosh darajadagi buyurtma sohasi uchun eng tez ma'lum bo'lgan usul indeksni hisoblash usuli, bu maydon elementlarini faktorizatsiya qilishni o'z ichiga oladi. Agar biz asosiy kuchlar tartibini odatdagi usulda ifodalasak - ya'ni asosiy buyurtma bazasi maydonidagi polinomlar, modulni mos darajadagi kamaytirilmaydigan polinomni kamaytirgan bo'lsak - bu shunchaki Kantor-Zassenxaus algoritmi tomonidan taqdim etilgan polinom faktorizatsiyasi. .

Kompyuter algebra tizimlarida amalga oshirish

Kantor - Zassenxaus algoritmi PARI / GP sifatida kompyuter algebra tizimi factorcantor () funktsiya.

Shuningdek qarang

Adabiyotlar

Kantor, Devid G.; Zassenxaus, Xans (1981 yil aprel), "Sonli maydonlar bo'yicha polinomlarni faktoring qilishning yangi algoritmi", Hisoblash matematikasi, 36 (154): 587–592, doi:10.1090 / S0025-5718-1981-0606517-5, JSTOR 2007663, JANOB 0606517
http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor-zassenhaus-in-odd-characteristic/