Cantor-Zassenhaus algoritması - Cantor–Zassenhaus algorithm

İçinde hesaplamalı cebir, Cantor-Zassenhaus algoritması faktoring için bir yöntemdir polinomlar bitmiş sonlu alanlar (Galois alanları da denir).

Algoritma esas olarak üs alma ve polinomdan oluşur GCD hesaplamalar. Tarafından icat edildi David G. Cantor ve Hans Zassenhaus 1981'de.

Muhtemelen sorunu çözmek için baskın algoritmadır, daha önce Berlekamp algoritması 1967. Şu anda birçok ülkede uygulanmaktadır. bilgisayar cebir sistemleri.

Genel Bakış

Arka fon

Cantor-Zassenhaus algoritması, girdi olarak karesiz bir polinom alır ${displaystyle f (x)}$ (yani tekrar eden faktörleri olmayan) derece n sonlu bir alanda katsayılarla ${displaystyle mathbb {F} _ {q}}$ kimin indirgenemez polinom faktörlerin tümü eşit derecededir (rastgele polinomları bu koşulları sağlayan polinomların bir ürününe verimli bir şekilde çarpanlarına ayırmak için algoritmalar mevcuttur, örneğin ${displaystyle f (x) / gcd (f (x), f '(x))}$ ile aynı faktörlere sahip karesiz bir polinomdur ${displaystyle f (x)}$ , böylece Cantor – Zassenhaus algoritması rastgele polinomları çarpanlarına ayırmak için kullanılabilir). Çıktı olarak bir polinom verir ${displaystyle g (x)}$ katsayıları aynı alanda olacak şekilde ${displaystyle g (x)}$ böler ${displaystyle f (x)}$ . Algoritma daha sonra bu ve sonraki bölenlere yinelemeli olarak uygulanabilir, ta ki ayrışmasını bulana kadar ${displaystyle f (x)}$ indirgenemez polinomların güçlerine dönüşür (şunu hatırlayarak yüzük herhangi bir alan üzerindeki polinomların sayısı bir benzersiz faktörleştirme alanı ).

Olası tüm faktörler ${displaystyle f (x)}$ içinde bulunur faktör halkası ${displaystyle R = {frac {mathbb {F} _ {q} [x]} {langle f (x) açısı}}}$ . Varsayalım ki ${displaystyle f (x)}$ indirgenemez faktörlere sahiptir ${displaystyle p_ {1} (x), p_ {2} (x), ldots, p_ {s} (x)}$ tüm derece dbu faktör halkası, izomorfiktir. direkt ürün faktör halkalarının sayısı ${displaystyle S = prod _ {i = 1} ^ {s} {frac {mathbb {F} _ {q} [x]} {langle p_ {i} (x) açı}}}$ . İzomorfizm R -e S, söyle ${displaystyle phi}$ , bir polinomu eşler ${displaystyle g (x) in R}$ için s-triple indirgeme modulo her biri ${displaystyle p_ {i} (x)}$ , yani eğer:

{displaystyle {egin {hizalı} g (x) ve {} eşdeğer g_ {1} (x) {pmod {p_ {1} (x)}}, g (x) ve {} eşdeğeri g_ {2} (x ) {pmod {p_ {2} (x)}}, & {} vdots g (x) & {} eşdeğeri g_ {s} (x) {pmod {p_ {s} (x)}}, end { hizalı}}}

sonra ${displaystyle phi (g (x) + langle f (x) angle) = (g_ {1} (x) + langle p_ {1} (x) angle, ldots, g_ {s} (x) + langle p_ {s } (x) açı)}$ . Algoritmada daha sonra kritik öneme sahip olacağı için, bu noktada aşağıdakilere dikkat etmek önemlidir: ${displaystyle p_ {i} (x)}$ her biri indirgenemez, bu doğrudan toplamdaki faktör halkalarının her biri aslında bir alandır. Bu alanların her birinin derecesi var ${displaystyle q ^ {d}}$ .

Temel sonuç

Cantor – Zassenhaus algoritmasının temelinde yatan temel sonuç şudur: ${R içinde displaystyle a (x)}$ tatmin edici bir polinomdur:

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

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

nerede ${displaystyle a_ {i} (x)}$ azalması ${displaystyle a (x)}$ modulo ${displaystyle p_ {i} (x)}$ daha önce olduğu gibi ve aşağıdaki üç kümeden herhangi ikisi boş değilse:

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

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

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

aşağıdaki önemsiz olmayan faktörler vardır: ${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).}

Algoritma

Cantor-Zassenhaus algoritması, aynı tipteki polinomları hesaplar ${displaystyle a (x)}$ Yukarıdaki, Arka Plan bölümünde tartışılan izomorfizmi kullanarak. Alanın bulunduğu durumda aşağıdaki gibi ilerler. ${displaystyle mathbb {F} _ {q}}$ garip özelliktedir (süreç oldukça basit bir şekilde karakteristik 2 alana genelleştirilebilir). Rastgele bir polinom seçin ${displaystyle b (x) in R}$ öyle ki ${displaystyle b (x) eq 0, pm 1}$ . Ayarlamak ${displaystyle m = (q ^ {d} -1) / 2}$ ve hesapla ${displaystyle b (x) ^ {m}}$ . Dan beri ${displaystyle phi}$ bir izomorfizmdir, bizde (şimdi oluşturulmuş gösterimimizi kullanarak):

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

Şimdi her biri ${displaystyle b_ {i} (x) + halka p_ {i} (x) açı}$ bir düzen alanının unsurudur ${displaystyle q ^ {d}}$ , daha önce belirtildiği gibi. Bu alanın çarpımsal alt grubunun sırası var ${displaystyle q ^ {d} -1}$ ve böyle olmadıkça ${displaystyle b_ {i} (x) = 0}$ , sahibiz ${displaystyle b_ {i} (x) ^ {q ^ {d} -1} = 1}$ her biri için ben ve dolayısıyla ${displaystyle b_ {i} (x) ^ {m} = pm 1}$ her biri için ben. Eğer ${displaystyle b_ {i} (x) = 0}$ o zaman tabii ki ${displaystyle b_ {i} (x) ^ {m} = 0}$ . Bu nedenle ${displaystyle b (x) ^ {m}}$ ile aynı tipte bir polinomdur ${displaystyle a (x)}$ yukarıda. Dahası, o zamandan beri ${displaystyle b (x) eq 0, pm 1}$ en az iki set ${displaystyle A, B}$ ve C boş değildir ve yukarıdaki GCD'leri hesaplayarak önemsiz olmayan faktörleri elde edebiliriz. Bir alan üzerindeki polinom halkası bir Öklid alanı, bu GCD'leri şu şekilde hesaplayabiliriz: Öklid algoritması.

Başvurular

Cantor – Zassenhaus algoritmasının önemli bir uygulaması hesaplamadır ayrık logaritmalar asal güç düzeninin sonlu alanları üzerinde. Ayrık logaritmaların hesaplanması, açık anahtarlı kriptografi. Asal güç düzeninin olduğu bir alan için, bilinen en hızlı yöntem, indeks hesabı yöntemi, alan elemanlarının faktörleştirilmesini içeren. Asal-güç düzeni alanını olağan şekilde temsil edersek - yani, asal mertebeden temel alan üzerindeki polinomlar olarak indirgenmiş modülo, uygun derecedeki indirgenemez bir polinomdur - bu, Cantor-Zassenhaus algoritması tarafından sağlanan basitçe polinom faktörleştirmesidir. .

Bilgisayar cebir sistemlerinde uygulama

Cantor – Zassenhaus algoritması, PARI / GP bilgisayar cebir sistemi olarak faktörcantor () işlevi.

Ayrıca bakınız

Referanslar

Cantor, David G.; Zassenhaus, Hans (Nisan 1981), "Polinomları sonlu alanlar üzerinden çarpanlarına ayırmak için yeni bir algoritma", Hesaplamanın Matematiği, 36 (154): 587–592, doi:10.1090 / S0025-5718-1981-0606517-5, JSTOR 2007663, BAY 0606517
http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor-zassenhaus-in-odd-characteristic/