Polinomların sonlu alanlar üzerinde çarpanlara ayrılması - Factorization of polynomials over finite fields

İçinde matematik ve bilgisayar cebiri bir polinomun çarpanlara ayrılması onu bir ürün nın-nin indirgenemez faktörler. Bu ayrıştırma teorik olarak mümkündür ve aşağıdakiler için benzersizdir: polinomlar ile katsayılar herhangi birinde alan, ancak çarpanlara ayırmanın bir aracılığıyla hesaplanmasına izin vermek için katsayılar alanında oldukça güçlü kısıtlamalara ihtiyaç vardır. algoritma. Uygulamada, algoritmalar yalnızca katsayıları olan polinomlar için tasarlanmıştır. sonlu alan, içinde mantık alanı veya içinde sonlu oluşturulmuş alan uzantısı bunlardan biri.

Rasyonel sayılar üzerindeki çok değişkenli polinomlar durumu da dahil olmak üzere tüm çarpanlara ayırma algoritmaları, sorunu bu duruma indirger; görmek polinom çarpanlarına ayırma. Ayrıca, sonlu alanların çeşitli uygulamaları için de kullanılır, örneğin kodlama teorisi (döngüsel artıklık kodlar ve BCH kodları ), kriptografi (açık anahtarlı kriptografi Vasıtasıyla eliptik eğriler ), ve hesaplamalı sayı teorisi.

Çarpanlara ayırmanın azaltılması olarak çok değişkenli polinomlar tek değişkenli polinomların sonlu bir alandaki katsayılar durumunda herhangi bir özgüllüğü yoktur, bu makalede sadece tek değişkenli polinomlar ele alınmıştır.

Arka fon

Sonlu alan

Kökenleri eserlerine kadar izlenebilen sonlu alanlar teorisi Gauss ve Galois, matematiğin çeşitli dallarında rol almıştır. Kavramın matematik ve bilimlerin bilgisayar bilimi gibi diğer konularındaki uygulanabilirliği nedeniyle, sonlu alanlara ilgi yeniden canlanmıştır ve bu kısmen, kodlama teorisi ve kriptografi. Sonlu alanların uygulamaları, bu gelişmelerden bazılarını tanıtmaktadır. kriptografi, bilgisayar cebiri ve kodlama teorisi.

Sonlu bir alan veya Galois alanı ile bir alandır sonlu sıra (eleman sayısı). Sonlu bir alanın sırası her zaman bir önemli veya asal bir güç. Her biri için asal güç q = p^r, tam olarak bir sonlu alan vardır q elementler, kadar izomorfizm. Bu alan gösterilir GF(q) veya F_q. Eğer p asal GF(p) ana alan düzenin p; alanı kalıntı sınıfları modulo p, ve Onun p elemanlar 0, 1, ..., p−1. Böylece a = b içinde GF(p) aynı anlama gelir a ≡ b (mod p).

İndirgenemez polinomlar

İzin Vermek F sonlu bir alan ol. Genel alanlara gelince, sabit olmayan bir polinom f içinde F[x] olduğu söyleniyor indirgenemez bitmiş F pozitif dereceli iki polinomun ürünü değilse. İndirgenemeyen pozitif dereceli bir polinom F denir indirgenebilir F.

İndirgenemez polinomlar, asal olmayan düzenin sonlu alanlarını inşa etmemize izin verir. Aslında, birinci sınıf bir güç için q, İzin Vermek F_q ile sonlu alan olmak q izomorfizme kadar benzersiz öğeler. Bir polinom f derece n birden büyük olan, indirgenemez F_q, derecenin alan uzantısını tanımlar n ile sahaya izomorfik olan qⁿ elemanlar: bu uzantının elemanları, daha düşük dereceli polinomlardır. n; bir elemanı ile toplama, çıkarma ve çarpma F_q polinomların olanlar; iki elementin ürünü, bölümün geri kalanıdır. f ürünlerinin polinomlar olarak; bir elemanın tersi, genişletilmiş GCD algoritması ile hesaplanabilir (bkz. Cebirsel uzantıların aritmetiği ).

Bunu takiben, asal olmayan sonlu bir alanda hesaplama yapmak için indirgenemez bir polinom üretilmesi gerekir. Bunun için yaygın yöntem, rastgele bir polinom almak ve onu indirgenemezlik açısından test etmektir. Alandaki çarpmanın verimliliği uğruna, şeklin polinomlarını aramak olağandır. xⁿ + balta + b.^{[kaynak belirtilmeli ]}

Sonlu alanlar üzerindeki indirgenemez polinomlar ayrıca Sahte rasgele geri besleme kayma kayıtlarını kullanan sayı üreteçleri ayrık logaritma bitmiş F_2ⁿ.

İndirgenemez sayısı monik polinomlar n derece üstü F_q sayısı periyodik olmayan kolyeler, veren Moreau'nun kolye sayma işlevi M_q(n). Yakından ilişkili kolye işlevi N_q(n) derecenin monik polinomlarını sayar n birincil olan (indirgenemez bir güç); veya alternatif olarak n'yi bölen tüm d derecelerindeki indirgenemez polinomlar.^[1]

Misal

Polinom P = x⁴ + 1 indirgenemez Q ancak herhangi bir sonlu alanın üzerinde değil.

Herhangi bir alan uzantısında F₂, P = (x+1)⁴.
Diğer her sonlu alanda, −1, 2 ve −2'den en az biri karedir, çünkü iki kare olmayanın çarpımı bir karedir ve bu nedenle bizde

Eğer ${ displaystyle -1 = a ^ {2},}$ sonra ${ displaystyle P = (x ^ {2} + a) (x ^ {2} -a).}$
Eğer ${ displaystyle 2 = b ^ {2},}$ sonra ${ displaystyle P = (x ^ {2} + bx + 1) (x ^ {2} -bx + 1).}$
Eğer ${ displaystyle -2 = c ^ {2},}$ sonra ${ displaystyle P = (x ^ {2} + cx-1) (x ^ {2} -cx-1).}$

Karmaşıklık

Polinom faktörleme algoritmaları, ürünler, bölümler, gcd, bir polinom modülo diğerinin üsleri vb. Gibi temel polinom işlemleri kullanır. çarpma işlemi en fazla iki derece polinomu n yapılabilir Ö(n²) operasyonlar F_q "klasik" aritmetik kullanarak veya Ö(ngünlük (n) günlük (günlük (n))) işlemleri F_q kullanma "hızlı" aritmetik. Bir Öklid bölümü (kalanla bölme) aynı zaman sınırları içinde gerçekleştirilebilir. Bir maliyeti polinom en büyük ortak bölen en fazla iki derece polinomu arasında n olarak alınabilir Ö(n²) operasyonlar F_q klasik yöntemler kullanarak veya Ö(ngünlük²(n) günlük (günlük (n))) işlemleri F_q hızlı yöntemler kullanarak. Polinomlar için h, g en fazla derece n, üs alma h^q mod g ile yapılabilir Ö(günlük (q)) polinom ürünleri kullanarak kareye göre üs alma yöntem, yani Ö(n²günlük (q)) operasyonlar F_q klasik yöntemler kullanarak veya Ö(ngünlük (q) günlük (n) günlük (günlük (n))) işlemleri F_q hızlı yöntemler kullanarak.

Aşağıdaki algoritmalarda, karmaşıklıklar, aritmetik işlemlerin sayısı cinsinden ifade edilir. F_q, polinomların aritmetiği için klasik algoritmalar kullanarak.

Faktoring algoritmaları

Polinomları sonlu alanlar üzerinden çarpanlarına ayırmak için birçok algoritma aşağıdaki üç aşamayı içerir:

Karesiz çarpanlara ayırma
Farklı derece çarpanlara ayırma
Eşit derecede çarpanlara ayırma

Önemli bir istisna Berlekamp algoritması 2. ve 3. aşamaları birleştiren.

Berlekamp algoritması

Berlekamp'ın algoritması, pratikte iyi çalışan ilk çarpanlara ayırma algoritması olduğu için tarihsel olarak önemlidir. Bununla birlikte, zemin alanının elemanları üzerinde bir döngü içerir, bu da sadece küçük sonlu alanlar üzerinde uygulanabilir olduğunu ima eder. Sabit bir zemin alanı için, zaman karmaşıklığı polinomdur, ancak genel zemin alanları için karmaşıklık, zemin alanının boyutunda üsteldir.

Karesiz çarpanlara ayırma

Algoritma bir karesiz Katsayıları sonlu alandan gelen polinomlar için çarpanlara ayırma F_q düzenin q = p^m ile p bir asal. Bu algoritma öncelikle türev ve sonra polinomun gcd'sini ve türevini hesaplar. Bir değilse, türevin sıfır olmaması koşuluyla, gcd tekrar orijinal polinomlara bölünür (sonlu alanlar üzerinde tanımlanan sabit olmayan polinomlar için var olan bir durum).

Bu algoritma, bir polinomun türevi sıfır ise, o zaman bir polinom olduğu gerçeğini kullanır. x^p, yani katsayılar aitse F_p, pikame edilerek elde edilen polinomun inci kuvveti x tarafından x^1/p. Katsayılar ait değilse F_p, psıfır türevi olan bir polinomun. kökü, aynı ikame ile elde edilir. xtersini uygulayarak tamamlandı Frobenius otomorfizmi katsayılara.

Bu algoritma aynı zamanda bir alan üzerinde de çalışır. karakteristik sıfır, tek farkla, burada talimat bloklarına asla girmemesi pinci kökler hesaplanır. Ancak bu durumda, Yun algoritması düşük dereceli polinomların en büyük ortak bölenlerini hesapladığı için çok daha verimlidir. Bunun bir sonucu, bir polinomu tamsayılar üzerinden çarpanlarına ayırırken, aşağıdaki algoritmanın kullanılmamasıdır: ilk önce tamsayılar üzerinde karesiz çarpanlara ayırma hesaplanır ve elde edilen polinomları çarpanlara ayırmak için bir p kare içermeyen modulo olarak kalacak şekilde p.

Algoritma: SFF (Karesiz Ayrıştırma) Giriş: Bir monik polinom f içinde F_q[x] nerede q = p^m    Çıktı: Karesiz çarpanlara ayırma f    R ← 1 # Yap w tüm faktörlerin ürünü (çokluksuz) olmak f # çokluğa sahip olanlar ile bölünemez p    c ← gcd(f, f′)    w ← f/c        # Adım 1: Tüm faktörleri belirleyin w    ben←1     süre w ≠ 1 yapmak        y ← gcd(w, c)        fac ← w/y        R ← R·fac^ben        w ← y; c ← c/y; ben ← i + 1     bitince    # c artık kalan faktörlerin (çokluklu) ürünüdür f       # Adım 2: Özyinelemeyi kullanarak kalan tüm faktörleri tanımlayın # Bunların, f ile bölünebilen çokluğa sahip olanlar p    Eğer c ≠ 1 sonra        c ← c^1/p        R ← R·SFF(c)^p    eğer biterse        Çıktı(R)

Fikir, tüm indirgenemez faktörlerin ürününü belirlemektir. f aynı çeşitlilikle. Bu iki basamakta yapılır. İlk adım, biçimsel türevini kullanır. f ile bölünemeyen çokluklu tüm faktörleri bulmak p. İkinci adım, kalan faktörleri tanımlar. Geri kalan tüm faktörlerin çokluğu olduğundan p, onların güçleri oldukları anlamına gelir pbiri basitçe alabilir p-inci karekök ve özyineleme uygular.

Karesiz çarpanlara ayırma örneği

İzin Vermek

{ displaystyle f = x ^ {11} + 2x ^ {9} + 2x ^ {8} + x ^ {6} + x ^ {5} + 2x ^ {3} + 2x ^ {2} +1 içinde mathbf {F} _ {3} [x],}

alan üzerinde üç unsurla çarpanlarına ayrılacaktır.

Algoritma önce hesaplar

{ displaystyle c = gcd (f, f ') = x ^ {9} + 2x ^ {6} + x ^ {3} +2.}

Türev sıfır olmadığı için elimizde $w = f / c = x 2 + 2$ ve while döngüsüne giriyoruz. Bir döngüden sonra elimizde $y = x + 2$ , $z = x + 1$ ve $R = x + 1$ güncellemelerle $ben = 2$ , $w = x + 2$ ve $c = x 8 + x 7 + x 6 + x 2 + x +1$ . Döngü boyunca ikinci kez verir $y = x + 2$ , $z = 1$ , $R = x + 1$ güncellemelerle $ben = 3$ , $w = x + 2$ ve $c = x 7 + 2 x 6 + x + 2$ . Döngü boyunca üçüncü kez de değişmez $R$ . Döngü boyunca dördüncü kez $y = 1$ , $z = x + 2$ , $R = (x + 1)(x + 2) 4$ güncellemelerle $ben = 5$ , $w = 1$ ve $c = x 6 + 1$ . Dan beri w = 1, while döngüsünden çıkıyoruz. Dan beri c ≠ 1, mükemmel bir küp olmalı. Küp kökü c, değiştirilerek elde edilir x³ tarafından x dır-dir x² + 1'dir ve karesiz yordamı yinelemeli olarak çağırmak, kare içermeyen olduğunu belirler. Bu nedenle, onu küp haline getirip değeriyle birleştirerek R bu noktaya kadar karesiz ayrışım verir

{ displaystyle f = (x + 1) (x ^ {2} +1) ^ {3} (x + 2) ^ {4}.}

Farklı derece çarpanlara ayırma

Bu algoritma, karesiz bir polinomu, indirgenemez faktörlerinin tümü aynı dereceye sahip olan bir polinomların ürününe böler. İzin Vermek f ∈ F_q[x] derece n çarpanlarına ayrılacak polinom olun.

Algoritma Farklı derece çarpanlara ayırma (DDF) Giriş: Monik karesiz bir polinom f ∈ F_q[x]    Çıktı: Tüm çiftlerin kümesi (g, d), öyle ki f indirgenemez bir derece faktörüne sahiptir d ve g tüm monik indirgenemez faktörlerin ürünüdür f derece d.    Başla         ${ displaystyle i: = 1; qquad S: = boşküme, qquad f ^ {*}: = f;}$         süre  ${ displaystyle deg f ^ {*} geq 2i}$  yapmak              ${ displaystyle g = gcd (f ^ {*}, x ^ {q ^ {i}} - x)}$             Eğer g ≠ 1, sonra                  ${ displaystyle S: = S fincan {(g, i)}}$ ;                f * := f */g;            eğer biterse            ben := ben+1;        bitince;        Eğer f * ≠ 1, sonra  ${ displaystyle S: = S fincan {(f ^ {*}, deg f ^ {*})}}$ ;        Eğer S = ∅            sonra geri dön {(f, 1)}            yoksa geri dön S    Son

Algoritmanın doğruluğu aşağıdakilere dayanmaktadır:

Lemma. İçin ben ≥ 1 polinom
${ displaystyle x ^ {q ^ {i}} - x in mathbf {F} _ {q} [x]}$
tüm tekli indirgenemez polinomların ürünüdür F_q[x] derecesi bölünen ben.

İlk bakışta, girdi polinomunun derecesinde üssel olan bir derecedeki polinomların OBEB'sini hesaplamayı içerdiğinden, bu verimli değildir. ancak

{ displaystyle g = gcd sol (f ^ {*}, x ^ {q ^ {i}} - x sağ)}

ile değiştirilebilir

{ displaystyle g = gcd sol (f ^ {*}, sol (x ^ {q ^ {i}} - x mod f ^ {*} sağ) sağ).}

Bu nedenle şunları hesaplamalıyız:

{ displaystyle x ^ {q ^ {i}} - x mod f ^ {*},}

iki yöntem vardır:

Yöntem I. Değerinden başlayın
${ displaystyle x ^ {q ^ {i-1}} mod f ^ {*}}$
önceki adımda hesaplanır ve hesaplanır q-th güç modülü yeni f *, kullanma kareye göre üs alma yöntem. Bunun ihtiyacı var
${ Displaystyle O sol ( log (q) deg (f) ^ {2} sağ)}$
aritmetik işlemler F_q her adımda ve dolayısıyla
${ Displaystyle O sol ( log (q) deg (f) ^ {3} sağ)}$
tüm algoritma için aritmetik işlemler.

Yöntem II. Gerçeğini kullanarak q-th güç, üzerinde doğrusal bir haritadır F_q matrisini şu şekilde hesaplayabiliriz:
${ Displaystyle O sol ( deg (f) ^ {2} ( log (q) + deg (f)) sağ)}$
operasyonlar. Sonra döngünün her yinelemesinde, bir matrisin çarpımını bir vektöre göre hesaplayın ( Ö(derece (f)²) operasyonlar). Bu, içinde toplam operasyon sayısını tetikler. F_q hangisi
${ displaystyle O sol ( deg (f) ^ {2} ( log (q) + deg (f)) sağ).}$
Dolayısıyla bu ikinci yöntem daha etkilidir ve genellikle tercih edilir. Ayrıca, bu yöntemde hesaplanan matris, çoğu algoritma tarafından eşit derecede çarpanlara ayırma için kullanılır (aşağıya bakın); böylece farklı derecelerde çarpanlara ayırma için kullanılması daha fazla hesaplama süresinden tasarruf sağlar.

Eşit derecede çarpanlara ayırma

Cantor-Zassenhaus algoritması

Bu bölümde, tekli karesiz tek değişkenli polinomun çarpanlara ayrılmasını ele alıyoruz. f, derece n, sonlu bir alan üzerinde F_q, hangisi r ≥ 2 çift ayrı indirgenemez faktör ${ displaystyle f_ {1}, ldots, f_ {r}}$ her derece d.

Önce Cantor ve Zassenhaus (1981) tarafından bir algoritma ve ardından biraz daha iyi karmaşıklığa sahip bir varyant tanımlıyoruz. Her ikisi de çalışma süresi rastgele seçimlere bağlı olan olasılıklı algoritmalardır (Las Vegas algoritmaları ) ve iyi bir ortalama çalışma süresine sahip. Bir sonraki bölümde, aynı zamanda eşit dereceli bir çarpanlara ayırma algoritması olan, ancak deterministik olan Shoup (1990) tarafından hazırlanan bir algoritmayı açıklayacağız. Tüm bu algoritmalar tek bir sıra gerektirir q katsayılar alanı için. Daha fazla çarpanlara ayırma algoritması için bkz. Knuth'un kitabı Bilgisayar Programlama Sanatı hacim 2.

Algoritma Cantor – Zassenhaus algoritması. Giriş: Sonlu bir alan F_q tuhaf düzen q. Monik karesiz bir polinom f içinde F_q[x] derece n = rd,                 hangisi r ≥ Her derece için 2 indirgenemez faktör d    Çıktı: Monik indirgenemez faktörler kümesi f.

    Faktörler: = {f}; while Boyut (Faktörler) < r yap, seç h içinde F_q[x] derece ile (h) < n rastgele;  ${ displaystyle g: = h ^ { frac {q ^ {d} -1} {2}} - 1 { pmod {f}}}$         her biri için sen Derece ile Faktörlerde (sen) > d do if gcd (g, sen) ≠ 1 ve gcd (g, sen) ≠ sen, sonra Faktörler: = Faktörler ${ displaystyle , setminus , {u } cup {( gcd (g, u), u / gcd (g, u)) }}$ ; endif; sonunda dönüş Faktörleri.

Bu algoritmanın doğruluğu, yüzüğün F_q[x]/f alanların doğrudan bir ürünüdür F_q[x]/f_ben nerede f_ben indirgenemez faktörlerle çalışır f. Tüm bu alanların sahip olduğu gibi q^d elemanlar, bileşeni g bu alanlardan herhangi birinde olasılıkla sıfırdır

{ displaystyle { frac {q ^ {d} -1} {2q ^ {d}}} sim { tfrac {1} {2}}.}

Bu, polinom gcd (g, sen) faktörlerin ürünüdür g bunun için bileşeni g sıfırdır.

Algoritmanın while döngüsünün ortalama yineleme sayısının daha az olduğu gösterilmiştir. ${ displaystyle 2.5 log _ {2} r}$ , ortalama aritmetik işlem sayısı verir F_q hangisi ${ displaystyle O (dn ^ {2} log (r) log (q))}$ .^[2]

Tipik durumda dgünlük (q) > n, bu karmaşıklık azaltılabilir

{ Displaystyle O (n ^ {2} ( günlük (r) günlük (q) + n))}

seçerek h doğrusal haritanın çekirdeğinde

{ displaystyle v ila v ^ {q} -v { pmod {f}}}

ve talimatı değiştirmek

{ displaystyle g: = h ^ { frac {q ^ {d} -1} {2}} - 1 { pmod {f}}}

tarafından

{ displaystyle g: = h ^ { frac {q-1} {2}} - 1 { pmod {f}}.}

Geçerlilik kanıtı, alanların doğrudan çarpımını değiştirerek yukarıdakiyle aynıdır. F_q[x]/f_ben alt alanlarının doğrudan çarpımı ile q elementler. Karmaşıklık içinde ayrışıyor ${ displaystyle O (n ^ {2} günlük (r) günlük (q))}$ algoritmanın kendisi için ${ displaystyle O (n ^ {2} ( log (q) + n))}$ Doğrusal haritanın matrisinin hesaplanması için (zaten karesiz çarpanlara ayırmada hesaplanmış olabilir) ve Ö(n³) çekirdeğini hesaplamak için. Bu algoritmanın, faktörlerin aynı derecede olmaması durumunda da çalıştığı not edilebilir (bu durumda sayı r while döngüsünü durdurmak için gerekli olan faktör sayısı, çekirdeğin boyutu olarak bulunur). Yine de, bu algoritmayı kullanmadan önce karesiz çarpanlara ayırma yapılırsa karmaşıklık biraz daha iyidir ( n karesiz çarpanlara ayırma ile azalabilir, bu kritik adımların karmaşıklığını azaltır).

Victor Shoup'un algoritması

Önceki bölümün algoritmaları gibi, Victor Shoup algoritması eşit dereceli bir çarpanlara ayırma algoritmasıdır.^[3] Onlardan farklı olarak deterministik bir algoritmadır. Bununla birlikte, pratikte, önceki bölümün algoritmalarından daha az verimlidir. Shoup algoritması için, girdi, asal alanlar üzerinden polinomlarla sınırlıdır F_p.

En kötü durum zaman karmaşıklığı Shoup algoritmasının bir faktörü var ${ displaystyle { sqrt {p}}.}$ Üstel olmasına rağmen, bu karmaşıklık, önceki deterministik algoritmalardan (Berlekamp'ın algoritması) çok daha iyidir. $p$ faktör olarak. Bununla birlikte, hesaplama süresinin üstel olduğu ve algoritmanın ortalama zaman karmaşıklığının polinom olduğu çok az polinom vardır. ${ displaystyle d log (p),}$ nerede $d$ polinomun derecesidir ve $p$ zemin alanının elemanlarının sayısıdır.

İzin Vermek g = g₁ ... g_k istenen çarpanlara ayırma, burada g_ben farklı monik indirgenemez derece polinomlarıdır d. İzin Vermek n = derece (g) = kd. Biz düşünüyoruz yüzük R = F_q[x]/g ve ayrıca şununla belirt x resmi x içinde R. Yüzük R alanların doğrudan çarpımıdır R_ben = F_q[x]/g_benve biz ile ifade ediyoruz p_ben doğal homomorfizm -den R üstüne R_ben. Galois grubu nın-nin R_ben bitmiş F_q düzenin döngüselidir dtarafından oluşturulan alan otomorfizmi sen → sen^p. Bunun köklerinin g_ben içinde R_ben vardır

{ displaystyle p_ {i} (x), p_ {i} (x ^ {q}), p_ {i} sol (x ^ {q ^ {2}} sağ), p_ {i} sol ( x ^ {q ^ {d-1}} sağ).}

Önceki algoritmada olduğu gibi, bu algoritma aynı alt cebir B nın-nin R olarak Berlekamp algoritması, bazen "Berlekamp alt sayfası" olarak adlandırılır ve şu şekilde tanımlanır:

{ displaystyle { begin {align} B & = left { alpha in R : p_ {1} ( alpha), cdots, p_ {k} ( alpha) in mathbf {F} _ {q} right } & = {u in R : u ^ {q} = u } end {hizalı}}}

Bir alt küme S nın-nin B söylendi ayırma seti her 1 ≤ içinben < j ≤ k var s ∈ S öyle ki ${ displaystyle p_ {i} (s) neq p_ {j} (s)}$ . Önceki algoritmada, bir ayırma kümesi, aşağıdaki unsurların rastgele seçilmesiyle oluşturulur. S. Shoup'un algoritmasında, ayırma kümesi aşağıdaki şekilde oluşturulur. İzin Vermek s içinde R[Y] öyle ol

{ displaystyle { başlar {hizalı} s & = (Yx) sol (Yx ^ {q} sağ) cdots sol (Yx ^ {q ^ {d-1}} sağ) & = s_ { 0} + cdots + s_ {d-1} Y ^ {d-1} + Y ^ {d} end {hizalı}}}

Sonra ${ displaystyle {s_ {0}, noktalar, s_ {d-1} }}$ ayırıcı bir settir çünkü ${ displaystyle p_ {i} (s) = g_ {i}}$ için ben =1, ..., k (iki monik polinom aynı köklere sahiptir). Olarak g_ben her bir farklı dizin çifti için (ben, j), katsayılardan en az biri s_h tatmin edecek ${ displaystyle p_ {i} (s_ {h}) neq p_ {j} (s_ {h}).}$

Ayırıcı bir kümeye sahip olan Shoup'un algoritması, önceki bölümün son algoritması olarak, sadece "rastgele seç" komutunu değiştirerek ilerler. h doğrusal haritanın çekirdeğinde ${ displaystyle v ila v ^ {q} -v { pmod {f}}}$ "göre" seçin h + ben ile h içinde S ve ben {1, ... içinde k−1}".

Zaman karmaşıklığı

Önceki bölümlerde anlatıldığı gibi, sonlu alanlar üzerindeki çarpanlara ayırma için, rastgele algoritmalar polinom zaman karmaşıklığı (örneğin Cantor-Zassenhaus algoritması). Bir polinom ortalama karmaşıklığı olan deterministik algoritmalar da vardır (örneğin Shoup'un algoritması).

Çok terimli en kötü durum karmaşıklığına sahip deterministik bir algoritmanın varlığı hala açık bir sorundur.

Rabin'in indirgenemezlik testi

Farklı derecelerde çarpanlara ayırma algoritması gibi, Rabin'in algoritması^[4] yukarıda belirtilen Lemma'ya dayanmaktadır. Farklı derecelerde çarpanlara ayırma algoritması her d giriş polinomunun derecesinin yarısından fazla değil. Rabin'in algoritması, faktörlerin daha az dikkate alınması için gerekli olmadığından yararlanır d. Aksi takdirde, farklı derecelerde çarpanlara ayırma algoritmasına benzer. Aşağıdaki gerçeğe dayanmaktadır.

İzin Vermek p₁, ..., p_k, tüm ana bölenler nve göster ${ displaystyle n / p_ {i} = n_ {i}}$ , 1 ≤ için ben ≤ k polinom f içinde F_q[x] derece n indirgenemez F_q[x] ancak ve ancak ${ displaystyle gcd sol (f, x ^ {q ^ {n_ {i}}} - x sağ) = 1}$ , 1 ≤ içinben ≤ k, ve f böler ${ displaystyle x ^ {q ^ {n}} - x}$ . Aslında, eğer f bölünmeyen bir derece faktörüne sahiptir n, sonra f bölünmez ${ displaystyle x ^ {q ^ {n}} - x}$ ; Eğer f derece bölme faktörüne sahiptir n, daha sonra bu faktör en az birini böler ${ displaystyle x ^ {q ^ {n_ {i}}} - x.}$

Algoritma Rabin İndirgenemezlik Testi Giriş: Tekli bir polinom f içinde F_q[x] derece n,         p₁, ..., p_k tüm farklı asal bölenler n.    Çıktı: Ya "f indirgenemez "veya"f indirgenebilir ". için j = 1 ila k yapmak          ${ displaystyle n_ {j} = n / p_ {j}}$ ;    için ben = 1 ila k yapmak          ${ displaystyle h: = x ^ {q ^ {n_ {i}}} - x { bmod {f}}}$ ;        g : = gcd (f, h);        Eğer g ≠ 1, sonra geri dön "f indirgenebilir " ve dur;    sonu için;     ${ displaystyle g: = x ^ {q ^ {n}} - x { bmod {f}}}$ ;    Eğer g = 0, sonra geri dön "f indirgenemez ", yoksa geri dön "f indirgenebilir "

Bu algoritmanın temel fikri hesaplamaktır ${ displaystyle x ^ {q ^ {n_ {i}}} { bmod {f}}}$ en küçüğünden başlayarak ${ displaystyle n_ {1}, ldots, n_ {k}}$ tekrarlayan karesini alarak veya Frobenius otomorfizmi ve sonra muhabir gcd'yi almak için. Temel polinom aritmetiğini kullanarak, Frobenius otomorfizm ihtiyaçlarının matrisinin hesaplanması ${ displaystyle O (n ^ {2} (n + log q))}$ operasyonlar F_q, hesaplanması

{ displaystyle x ^ {q ^ {n_ {i}}} - x { pmod {f}}}

ihtiyaçlar Ö(n³) daha fazla işlem ve algoritmanın kendisinin ihtiyacı Ö(kn²) işlemler, toplam ${ displaystyle O (n ^ {2} (n + log q))}$ operasyonlar F_q. Hızlı aritmetik kullanma (karmaşıklık ${ displaystyle O (n log n)}$ çarpma ve bölme için ve ${ displaystyle O (n ( log n) ^ {2})}$ GCD hesaplaması için), hesaplama ${ displaystyle x ^ {q ^ {n_ {i}}} - x { bmod {f}}}$ tekrarlanan kareye göre ${ displaystyle O (n ^ {2} log n log q)}$ ve algoritmanın kendisi ${ displaystyle O (kn ( log n) ^ {2})}$ , toplam veren ${ displaystyle O (n ^ {2} log n log q)}$ operasyonlar F_q.

Ayrıca bakınız

Referanslar

KEMPFERT, H (1969) Üzerinde Polinomların Ayrıştırılması Matematik Bölümü, Ohio Eyalet Üniversitesi, Columbus, Ohio 43210
Shoup, Victor (1996) Sonlu Alanlar Üzerinde Pürüzsüzlük ve Faktoring Polinomları Toronto Üniversitesi Bilgisayar Bilimleri Bölümü
Von Zur Gathen, J.; Panario, D. (2001). Polinomları Sonlu Alanlar Üzerinde Faktoring: Bir Araştırma. Sembolik Hesaplama Dergisi, Cilt 31, Sayılar 1-2, Ocak 2001, 3–17.
Gao Shuhong, Panario Daniel,İndirgenemez Polinomların Sonlu Alanlar Üzerinde Test Edilmesi ve Oluşturulması Matematik Bilimleri Bölümü, Clemson Üniversitesi, Güney Karolina, 29634-1907, ABD. ve Toronto Üniversitesi Bilgisayar Bilimleri Bölümü, Kanada M5S-1A4
Shoup, Victor (1989) Sonlu Alanlar Üzerinden İndirgenemez Polinomları Bulmak İçin Yeni Algoritmalar Bilgisayar Bilimleri Bölümü Wisconsin Üniversitesi - Madison
Geddes, Keith O.; Czapor, Stephen R .; Labahn, George (1992). Bilgisayar cebiri için algoritmalar. Boston, MA: Kluwer Academic Publishers. s. xxii + 585. ISBN 0-7923-9259-0.

Dış bağlantılar

Bazı indirgenemez polinomlar http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf
Alan ve Galois Teorisi:http://www.jmilne.org/math/CourseNotes/FT.pdf
Galois Alanı:http://designtheory.org/library/encyc/topics/gf.pdf
Polinomları sonlu alanlar üzerinde çarpanlara ayırma: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf

Notlar

^ Christophe Reutenauer, Mots circulaires ve polinomlar indirgenemez, Ann. Sci. matematik Quebec, cilt 12, no 2, s. 275-285
^ Flajolet, Philippe; Steayaert, Jean-Marc (1982), Otomata, Diller ve Programlama, Bilgisayarda Ders Notları. Sci., 140, Springer, s. 239–251, doi:10.1007 / BFb0012773, ISBN 978-3-540-11576-2
^ Victor Shoup, Polinomları sonlu alanlar üzerinde çarpanlara ayırmanın deterministik karmaşıklığı hakkında, Bilgi İşlem Mektupları 33: 261-267, 1990
^ Rabin, Michael (1980). "Sonlu alanlarda olasılık algoritmaları". Bilgi İşlem Üzerine SIAM Dergisi. 9 (2): 273–280. CiteSeerX 10.1.1.17.5653. doi:10.1137/0209024.

[1] Christophe Reutenauer, Mots circulaires ve polinomlar indirgenemez, Ann. Sci. matematik Quebec, cilt 12, no 2, s. 275-285

[2] Flajolet, Philippe; Steayaert, Jean-Marc (1982), Otomata, Diller ve Programlama, Bilgisayarda Ders Notları. Sci., 140, Springer, s. 239–251, doi:10.1007 / BFb0012773, ISBN 978-3-540-11576-2

[3] Victor Shoup, Polinomları sonlu alanlar üzerinde çarpanlara ayırmanın deterministik karmaşıklığı hakkında, Bilgi İşlem Mektupları 33: 261-267, 1990

[4] Rabin, Michael (1980). "Sonlu alanlarda olasılık algoritmaları". Bilgi İşlem Üzerine SIAM Dergisi. 9 (2): 273–280. CiteSeerX 10.1.1.17.5653. doi:10.1137/0209024.

[1]

[2]

[3]

[4]