परिमित क्षेत्रों पर बहुपदों का गुणनखंडन

गणित और कंप्यूटर बीजगणित में एक बहुपद के गुणनखंड में इसे अलघुकरणीय कारकों के उत्पाद में विघटित करना सम्मिलित है। यह अपघटन सैद्धांतिक रूप से संभव है और किसी भी क्षेत्र में गुणांक वाले बहुपदों के लिए अद्वितीय है, लेकिन एक एल्गोरिदम के माध्यम से कारक की गणना की स्वीकृति देने के लिए गुणांक के क्षेत्र पर जटिल प्रतिबंधों की आवश्यकता होती है। गणना में एल्गोरिदम को केवल बहुपदों के लिए परिमित क्षेत्र में गुणांक के साथ परिमेय के क्षेत्र में या उनमें से किसी एक के साथ परिमित रूप से उत्पन्न क्षेत्र विस्तार के लिए निर्मित किया गया है।

परिमेय संख्याओं पर बहुचर बहुपदों की स्थिति के सहित सभी गुणनखंडन एल्गोरिदम की इस स्थिति में समस्या को अपेक्षाकृत कम करते हैं जिसके लिए बहुपद गुणनखंड देखें। इसका उपयोग परिमित क्षेत्रों के विभिन्न अनुप्रयोगों जैसे कि कोडिंग सिद्धांत (चक्रीय अतिरेक कोड और बीसीएच कोड), क्रिप्टोग्राफी ( दीर्घवृत्तीय वक्रों के माध्यम से सार्वजनिक कुंजी क्रिप्टोग्राफी) और कम्प्यूटेशनल संख्या सिद्धांत के लिए भी किया जाता है।

परिमित क्षेत्र में गुणांक की स्थिति में के बहुचर बहुपदों के गुणनखंडन में कोई विशिष्टता नहीं होती है। इस लेख में केवल एक चर वाले बहुपदों पर विचार किया जाता है।

भूमिका

परिमित क्षेत्र

परिमित क्षेत्रों के सिद्धांत प्रायः जिनकी उत्पत्ति गॉस और गैलोज़ के कार्यों में देखी जा सकती है, गॉस ने गणित की विभिन्न शाखाओं में एक भूमिका निभाई है। गणित और विज्ञान जैसे कंप्यूटर विज्ञान के अन्य विषयों में अवधारणा की प्रयोज्यता के कारण परिमित क्षेत्रों में रुचि का पुनरुत्थान हुआ है और यह आंशिक रूप से कोडिंग सिद्धांत और क्रिप्टोग्राफी में महत्वपूर्ण अनुप्रयोगों के कारण है। परिमित क्षेत्रों के अनुप्रयोग क्रिप्टोग्राफी, कंप्यूटर बीजगणित और कोडिंग सिद्धांत में इनमें से कुछ विकास प्रस्तुत करते हैं।

परिमित क्षेत्र या गैलोज़ क्षेत्र एक परिमित क्रम (तत्वों की संख्या) वाला क्षेत्र है। परिमित क्षेत्र का क्रम सदैव अभाज्य संख्या या अभाज्य संख्या की घात होता है। प्रत्येक अभाज्य घात q = p^r के लिए समरूपता q तत्वों के साथ ठीक एक परिमित क्षेत्र सम्मिलित है। इस क्षेत्र को GF(q) या Fq द्वारा निरूपित किया जाता है। यदि p अभाज्य है, तो GF(p) का क्रम p अभाज्य क्षेत्र है। यह शेष संख्याए मॉडुलो p का क्षेत्र है और इसके p तत्व को 0, 1, ..., p−1 दर्शाया गया है। इस प्रकार GF(p) में a = b का अर्थ a ≡ b (mod p) के समान है।

अलघुकरणीय बहुपद

माना कि F एक परिमित क्षेत्र है। सामान्य क्षेत्रों के लिए F [x] में एक गैर-निरंतर बहुपद f को F पर अप्रासंगिक कहा जाता है यदि यह धनात्मक घात के दो बहुपदों का गुणनफल नहीं है। धनात्मक घात का एक बहुपद जो F पर अप्रासंगिक नहीं है, F पर अपचयित कहलाता है।

अलघुकरणीय बहुपद हमें गैर-अभाज्य क्रम के परिमित क्षेत्रों का निर्माण करने की स्वीकृति देते हैं। वास्तव में एक अभाज्य घात q के लिए माना कि F_q तत्वों के साथ एक परिमित क्षेत्र है जो कि समरूपता तक अद्वितीय है। घात n का एक बहुपद f एक से अधिक है, जो F_q से अधिक अपरिवर्तनीय है, घात n के क्षेत्र विस्तार को परिभाषित करता है जो qⁿ तत्वों के साथ क्षेत्र के लिए समरूप है इस विस्तार के तत्व n से कम घात के बहुपद हैं, घटाव और गुणा F_q के एक तत्व द्वारा बहुपदों में से दो तत्वों का उत्पाद बहुपद के रूप में उनके उत्पाद के f द्वारा विभाजन का शेष है। तत्व के व्युत्क्रम की गणना विस्तारित जीसीडी एल्गोरिथ्म द्वारा की जा सकती है। जिसके लिए बीजगणितीय विस्तार का अंकगणित देखें।

यह इस प्रकार है कि गैर अभाज्य क्रम के परिमित क्षेत्र में गणना करने के लिए एक अलघुकरणीय बहुपद उत्पन्न करने की आवश्यकता होती है। इसके लिए सामान्य विधि यादृच्छिक रूप से एक बहुपद लेना है और इसे अप्रासंगिकता के लिए परीक्षण करना है। क्षेत्र में गुणा की दक्षता के लिए xn + ax + b के आकार के बहुपदों की खोज करना सामान्य है।^{[citation needed]}

परिमित क्षेत्रों पर अलघुकरणीय बहुपद भी पुनर्निवेशन विस्थापन पंजी और F₂ⁿ पर असतत लघुगणक का उपयोग करके छद्म यादृच्छिक संख्या निर्माण के लिए उपयोगी होते हैं।

F_q पर घात n के अलघुकरणीय मोनिक बहुपदों की संख्या एपरियोडिक नेकलेस की संख्या है, जो मोरो के नेकलेस-गणना फलन Mq(n) द्वारा दी गई है। सूक्ष्मता से संबंधित नेकलेस फलन Nq(n) घात n के मोनिक बहुपदों की गणना करता है जो प्राथमिक (अलघुकरणीय की घात) या वैकल्पिक रूप से सभी घात d के अलघुकरणीय बहुपद है जो n को विभाजित करते हैं।^[1]

उदाहरण

बहुपद P = x⁴ + 1, Q पर अप्रासंगिक है लेकिन किसी परिमित क्षेत्र पर अप्रासंगिक नहीं है:

किसी भी क्षेत्र विस्तार पर F₂ ,P = (x + 1)⁴ है।
प्रत्येक दूसरे परिमित क्षेत्र में -1, 2 और -2 में से कम से कम एक वर्ग है क्योंकि दो गैर-वर्गों का गुणनफल एक वर्ग है और इसलिए हमारे पास है:

यदि $-1=a^{2},$ तब $P=(x^{2}+a)(x^{2}-a).$
यदि $2=b^{2},$ तब $P=(x^{2}+bx+1)(x^{2}-bx+1).$
यदि $-2=c^{2},$ तब $P=(x^{2}+cx-1)(x^{2}-cx-1).$

समिश्रता

बहुपद गुणनखंड एल्गोरिदम आधारिक बहुपद संचालन जैसे उत्पाद, विभाजन, जीसीडी एक बहुपद मॉडुलो की घातयों का उपयोग करते हैं। प्रारम्भिक अंकगणित का उपयोग करके f_q में O(n²) संचालन में अधिकतम n घात के दो बहुपदों का गुणा किया जा सकता है या O(nlog(n) log(log(n)) अंकगणित का उपयोग करके F_q में संचालन का यूक्लिडियन विभाजन (शेष के साथ विभाजन) एक ही समय सीमा के भीतर किया जा सकता है। अधिक से अधिक घात के दो बहुपदों के बीच एक बहुपद महानतम विभाजक की लागत प्रारम्भिक विधियों का उपयोग करके F_q में O(n²) संचालन के रूप में या F_q का उपयोग करके O(nlog(n) log(log(n)) संचालन के रूप में प्राप्त की जा सकती है। बहुपदों h, g की घात के लिए अधिकतम n घातांक h^q mod g को O(log(q)) बहुपद उत्पादों के साथ किया जा सकता है, वर्ग विधि द्वारा घातांक का उपयोग करके, जो प्रारम्भिक विधियों या O(nlog(q)log(n) log(log(n))) का विभिन्न प्रकार से उपयोग करके F_q में O(n²log(q)) संचालन है। अनुवर्ती एल्गोरिदम में बहुपदों के अंकगणित के लिए प्रारम्भिक एल्गोरिदम का उपयोग करते हुए F_q में अंकगणितीय संचालन की संख्या के संदर्भ में समिश्रताएं व्यक्त की जाती हैं।

गुणनखंड एल्गोरिथ्म

परिमित क्षेत्रों पर बहुपदों की गुणनखंड के लिए कई एल्गोरिदम में निम्नलिखित तीन चरण सम्मिलित हैं:

वर्ग मुक्त गुणनखंड
विशिष्ट घात गुणनखंडन
समान-घात गुणनखंडन

एक महत्वपूर्ण अपवाद बेर्लेकैंप का एल्गोरिथम है, जो चरण 2 और 3 को जोड़ता है।

बेर्लेकैंप का एल्गोरिथम

बेर्लेकैंप का एल्गोरिथम ऐतिहासिक रूप से महत्वपूर्ण है क्योंकि यह पहला गुणनखंड एल्गोरिथम है, जो गणना में अच्छी तरह से कार्य करता है। हालाँकि इसमें जमीनी क्षेत्र के तत्वों पर एक लूप होता है, जिसका तात्पर्य है कि यह केवल छोटे परिमित क्षेत्रों पर ही व्यावहारिक है। एक निश्चित सतह क्षेत्र के लिए इसकी समय समिश्रता बहुपद है, लेकिन सामान्य सतह क्षेत्र के लिए जटिलता सतह क्षेत्र के आकार में घातीय है।

वर्ग मुक्त गुणनखंड

एल्गोरिद्म उन बहुपदों के लिए एक वर्ग-मुक्त गुणनखंडन निर्धारित करता है जिनके गुणांक p, a अभाज्य के साथ क्रम q = p^m के परिमित क्षेत्र F_q से आते हैं। यह एल्गोरिदम पहले व्युत्पन्न को निर्धारित करता है और फिर बहुपद और उसके व्युत्पन्न के gcd की गणना करता है। यदि यह एक नहीं है तो gcd को फिर से मूल बहुपद में विभाजित किया जाता है, परंतु व्युत्पन्न शून्य न हो ऐसी स्थिति मे जो परिमित क्षेत्रों पर परिभाषित गैर-निरंतर बहुपदों के लिए सम्मिलित है।

यह एल्गोरिथ्म इस तथ्य का उपयोग करता है कि यदि बहुपद का व्युत्पन्न शून्य है तो यह x^p में एक बहुपद है, जो कि यदि गुणांक F_p से संबंधित है, तो x द्वारा x^1/p को प्रतिस्थापित करके प्राप्त बहुपद की p^th घात गुणांक F_p से संबंधित नहीं हैं, तो शून्य अवकलज वाले बहुपद का p^th मूल x पर उसी प्रतिस्थापन द्वारा प्राप्त किया जाता है, जिसे गुणांकों के लिए फ्रोबेनियस स्वसमाकृतिकता के व्युत्क्रम को प्रयुक्त करके पूरा किया जाता है।^{[citation needed]}

यह एल्गोरिदम विशेषता शून्य के क्षेत्र में भी काम करता है, केवल अंतर के साथ कि यह कभी भी निर्देशों के ब्लॉक में प्रवेश नहीं करता है जहां p^th जड़ों की गणना की जाती है। हालांकि, इस मामले में, यूं का एल्गोरिदम अधिक कुशल है क्योंकि यह कम घात के बहुपदों के सबसे बड़े सामान्य विभाजक की गणना करता है। एक परिणाम यह है कि जब पूर्णांकों पर एक बहुपद का गुणनखंड किया जाता है तो निम्न एल्गोरिथम का उपयोग नहीं किया जाता है जो पहले पूर्णांकों पर वर्ग-मुक्त गुणनखंडन की गणना करता है, और परिणामी बहुपदों का गुणनखंड करने के लिए, एक पी चुनता है जैसे कि वे वर्ग-मुक्त मॉड्यूलो p रहते हैं।

Algorithm: SFF (Square-Free Factorization)
    Input: A monic polynomial f in F_q[x] where q = p^m
    Output: Square-free factorization of f
    R ← 1
   
    # Make w be the product (without multiplicity) of all factors of f that have 
    # multiplicity not divisible by p
    c ← जीसीडी(f, f′)
    w ← f/c 
   
    # Step 1: Identify all factors in w
    i ← 1 
    while w ≠ 1 do
        y ← जीसीडी(w, c)
        fac ← w / y
        R ← R · facⁱ
        w ← y; c ← c / y; i ← i + 1 
    end while
    # c is now the product (with multiplicity) of the remaining factors of f
   
    # Step 2: Identify all remaining factors using recursion
    # Note that these are the factors of f that have multiplicity divisible by p
    if c ≠ 1 then
        c ← c^1/p
        R ← R·SFF(c)^p
    end if 
   
    Output(R)

विचार यह है कि समान बहुलता वाले f के सभी अलघुकरणीय कारकों के गुणनफल की पहचान की जाए। यह दो चरणों में किया जाता है। पहला कदम f के औपचारिक व्युत्पन्न का उपयोग करता है ताकि बहुलता वाले सभी कारकों को पी से विभाजित न किया जा सके। दूसरा चरण शेष कारकों की पहचान करता है। जैसा कि शेष सभी कारकों में p से विभाज्य बहुलता है, जिसका अर्थ है कि वे p की घातयाँ हैं, कोई भी केवल pth वर्गमूल ले सकता है और पुनरावर्तन लागू कर सकता है।

वर्ग मुक्त गुणनखंड का उदाहरण

माना कि

f=x^{11}+2x^{9}+2x^{8}+x^{6}+x^{5}+2x^{3}+2x^{2}+1\in \mathbf {F} _{3}[x],

तीन तत्वों के साथ क्षेत्र में फ़ैक्टर होना।

एल्गोरिदम पहले गणना करता है

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

चूंकि व्युत्पन्न गैर-शून्य है, हमारे पास $w = f / c = x 2 + 2$ है और हम लूप में प्रवेश करते हैं। एक लूप के बाद हमारे पास $y = x + 2$ , $z = x + 1$ और $R = x + 1$ अपडेट के साथ $i = 2$ , $w = x + 2$ और $c = x 8 + x 7 + x 6 + x 2 + x +1$ है। लूप के माध्यम से दूसरी बार $y = x + 2$ , $z = 1$ , $R = x + 1$ , अपडेट के साथ $i = 3$ , $w = x + 2$ और $c = x 7 + 2 x 6 + x + 2$ . के माध्यम से देता है। तीसरी बार के माध्यम से लूप भी R नहीं बदलता है। चौथी बार लूप के माध्यम से हमें $y = 1$ , $z = x + 2$ , $R = (x + 1)(x + 2) 4$ , अपडेट के साथ $i = 5$ , $w = 1$ और $c = x 6 + 1$ चूंकि w = 1, हम while लूप से बाहर निकलते हैं। चूँकि $c \neq 1$ , यह एक पूर्ण घन होना चाहिए। $x 3$ को $x$ से प्रतिस्थापित करके प्राप्त $c$ का घनमूल $x 2 + 1$ है, और वर्ग-मुक्त प्रक्रिया को पुनरावर्ती रूप से कॉल करना यह निर्धारित करता है कि यह वर्ग-मुक्त है। इसलिए, इसे घना करना और इसे $R$ के मान के साथ उस बिंदु पर संयोजित करना वर्ग-मुक्त अपघटन देता है

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

अलग घात गुणनखंड

यह एल्गोरिथम एक वर्ग-मुक्त बहुपद को बहुपदों के एक उत्पाद में विभाजित करता है, जिनके अलघुकरणीय कारकों में समान घात होती है। मान लीजिए $f \in F q [x]$ घात $n$ का गुणनखंड किया जाने वाला बहुपद है।

Algorithm Distinct-degree factorization(DDF)
    Input: A monic square-free polynomial  f ∈ F_q[x]
    Output: The set of all pairs (g, d), such that 
             f has an irreducible factor of degree d and
             g is the product of all monic irreducible factors of f of degree d.
    Begin
        
        while  do 
            
            if g ≠ 1, then 
                ;
                
            end if
            i := i + 1;
        end while;
        if , then ;
        if , then return {(f, 1)},
            else return S
    End

एल्गोरिथ्म की शुद्धता निम्नलिखित पर आधारित है:

लेम्मा i ≥ 1 के लिए बहुपद

x^{q^{i}}-x\in \mathbf {F} _{q}[x]

Fq [x] में सभी मोनिक अलघुकरणीय बहुपदों का गुणनफल है, जिसकी घात i को विभाजित करती है।

पहली नज़र में, यह कुशल नहीं है क्योंकि इसमें उस घात के बहुपदों के जीसीडी की गणना करना सम्मिलित है जो इनपुट बहुपद की घात में घातीय है। हालाँकि,

g=\gcd \left(f^{*},x^{q^{i}}-x\right)

द्वारा प्रतिस्थापित किया जा सकता है

g=\gcd \left(f^{*},\left(x^{q^{i}}-x\mod f^{*}\right)\right).

इसलिए, हमें गणना करनी होगी:

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

दो तरीके हैं:

विधि 1. के मान से प्रारंभ करें

x^{q^{i-1}}\mod f^{*}

वर्ग विधि द्वारा घातांक का उपयोग करते हुए, पिछले चरण में गणना की गई और इसकी qth घात मॉड्यूलो नई f * की गणना करने के लिए। इसकी जरूरत है

O\left(\log(q)\deg(f)^{2}\right)

प्रत्येक चरण में F_q में अंकगणितीय संचालन और इस प्रकार

O\left(\log(q)\deg(f)^{3}\right)

संपूर्ण एल्गोरिथम के लिए अंकगणितीय संक्रियाएं।

विधि 2. इस तथ्य का उपयोग करते हुए कि qth घात Fq पर एक रैखिक नक्शा है, हम इसके आव्यूह की गणना कर सकते हैं

O\left(\deg(f)^{2}(\log(q)+\deg(f))\right)

संचालन। फिर लूप के प्रत्येक पुनरावृत्ति पर, एक वेक्टर द्वारा एक आव्यूह के उत्पाद की गणना करें (O(deg(f)2) संचालन के साथ)। यह F_q में कुल संचालन को प्रेरित करता है जो है

O\left(\deg(f)^{2}(\log(q)+\deg(f))\right).

इस प्रकार यह दूसरी विधि अधिक कुशल है और आमतौर पर पसंद की जाती है। इसके अलावा, इस पद्धति में जिस आव्यूह की गणना की जाती है, उसका उपयोग अधिकांश एल्गोरिदम द्वारा समान-घात गुणनखंड के लिए किया जाता है (नीचे देखें); इस प्रकार इसे विशिष्ट-घात गुणनखंडन के लिए उपयोग करने से आगे कंप्यूटिंग समय की बचत होती है।

समान-घात गुणनखंड

कैंटर-ज़सेनहॉस एल्गोरिथम

इस खंड में, हम एक परिमित क्षेत्र F_q पर, घात n के एक मोनिक स्क्वायरफ्री यूनीवेरिएट बहुपद f के गुणन पर विचार करते हैं, जिसमें $r \geq 2$ जोड़ीदार अलग-अलग इर्रेड्यूबल कारक $f_{1},\ldots ,f_{r}$ प्रत्येक घात d हैं।

हम पहले कैंटर और ज़ैसेनहॉस (1981) द्वारा एक एल्गोरिथ्म का वर्णन करते हैं और फिर एक वेरिएंट जिसमें थोड़ी बेहतर जटिलता है। दोनों संभाव्य एल्गोरिदम हैं जिनके चलने का समय यादृच्छिक विकल्पों (लास वेगास एल्गोरिदम) पर निर्भर करता है, और एक अच्छा औसत चलने का समय है। अगले भाग में हम शौप (1990) द्वारा एक एल्गोरिथम का वर्णन करते हैं, जो एक समान-घात गुणनखंड एल्गोरिथम भी है, लेकिन नियतात्मक है। इन सभी एल्गोरिदम को गुणांक के क्षेत्र के लिए विषम क्रम q की आवश्यकता होती है। अधिक गुणनखंडन एल्गोरिदम के लिए उदाहरण देखें नुथ की पुस्तक द आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग वॉल्यूम 2।

Algorithm Cantor–Zassenhaus algorithm.
    Input: A finite field F_q of odd order q.
           A monic square free polynomial f in F_q[x] of degree n = rd, 
                which has r ≥ 2 irreducible factors each of degree d
    Output: The set of monic irreducible factors of f.

    Factors := {f};
    while Size(Factors) < r do,
        Choose h in F_q[x] with deg(h) < n at random;
        
        for each u in Factors with deg(u) > d do
            if जीसीडी(g, u) ≠ 1 and जीसीडी(g, u) ≠ u, then
                Factors:= Factors;
            endif
    endwhile

    return Factors

इस एल्गोरिथम की शुद्धता इस तथ्य पर निर्भर करती है कि रिंग F_q[x]/f क्षेत्र F_q[x]/f का एक प्रत्यक्ष उत्पाद है जहां f के अलघुकरणीय कारकों पर चलता है। चूँकि इन सभी क्षेत्रों में q^d तत्व हैं, इनमें से किसी भी क्षेत्र में g का घटक प्रायिकता के साथ शून्य है

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

इसका तात्पर्य है कि बहुपद जीसीडी (g, u) G के कारकों का उत्पाद है जिसके लिए g का घटक शून्य है।

यह दिखाया गया है कि एल्गोरिदम के जबकि लूप के पुनरावृत्तियों की औसत संख्या $2.5\log _{2}r$ से कम है, जो F_q में अंकगणितीय संचालन की औसत संख्या देता है जो $O(dn^{2}\log(r)\log(q))$ है।^[2]

विशिष्ट मामले में जहां dlog(q) > n, इस जटिलता को कम किया जा सकता है

O(n^{2}(\log(r)\log(q)+n))

रेखीय मानचित्र के कर्नेल में h चुनकर

v\to v^{q}-v{\pmod {f}}

और निर्देश की जगह

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

द्वारा

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

वैधता का प्रमाण उपरोक्त के समान है, फ़ील्ड Fq[x]/fi के प्रत्यक्ष उत्पाद को q तत्वों के साथ उनके उपक्षेत्रों के प्रत्यक्ष उत्पाद द्वारा प्रतिस्थापित करना। एल्गोरिथ्म के लिए $O(n^{2}\log(r)\log(q))$ में जटिलता विघटित है, रैखिक के आव्यूह की गणना के लिए $O(n^{2}(\log(q)+n))$ (जो पहले से ही वर्ग-मुक्त गुणनखंड में गणना की जा सकती है) और इसके कर्नेल की गणना के लिए O(n3)। यह ध्यान दिया जा सकता है कि यह एल्गोरिथम तब भी काम करता है जब कारकों में समान घात नहीं होती है (इस मामले में कारकों की संख्या आर, जबकि लूप को रोकने के लिए आवश्यक है, कर्नेल के आयाम के रूप में पाया जाता है)। फिर भी, यदि इस एल्गोरिथम का उपयोग करने से पहले वर्ग-मुक्त गुणनखंडन किया जाता है, तो जटिलता थोड़ी बेहतर होती है (चूंकि n वर्ग-मुक्त गुणनखंडन के साथ घट सकता है, इससे महत्वपूर्ण चरणों की जटिलता कम हो जाती है)।

विक्टर शौप का एल्गोरिथम

पूर्ववर्ती खंड के एल्गोरिदम की तरह, विक्टर शौप का एल्गोरिदम एक समान-घात गुणनखंडन एल्गोरिदम है।^[3] उनके विपरीत, यह एक नियतात्मक एल्गोरिथम है। हालांकि, व्यवहार में, पिछले अनुभाग के एल्गोरिदम की तुलना में यह कम कुशल है। शौप के एल्गोरिद्म के लिए इनपुट अभाज्य क्षेत्रों F_p पर बहुपदों तक सीमित है।

शौप के एल्गोरिथ्म की सबसे खराब स्थिति समय जटिलता में एक कारक ${\sqrt {p}}$ है हालांकि घातीय, यह जटिलता पिछले नियतात्मक एल्गोरिदम (बेर्लेकैंप के एल्गोरिथ्म) से बहुत बेहतर है, जिसमें एक कारक के रूप में $p$ है। हालाँकि, बहुत कम बहुपद हैं जिनके लिए कंप्यूटिंग समय घातीय है और एल्गोरिथम की औसत समय जटिलता $d\log(p),$ में बहुपद है जहाँ $d$ बहुपद की घात है, और $p$ तत्वों की संख्या है जमीन के मैदान का।

मान लीजिए g = g1 ... gk वांछित गुणनखंड है, जहां gi घात d के विशिष्ट मोनिक अलघुकरणीय बहुपद हैं। चलो n = घात (जी) = केडी। हम वलय R = Fq[x]/g पर विचार करते हैं और R में x की छवि को x द्वारा भी निरूपित करते हैं। वलय R फ़ील्ड्स Ri = Fq[x]/gi का प्रत्यक्ष उत्पाद है, और हम प्राकृतिक पाई द्वारा निरूपित करते हैं R से Ri पर समाकारिता Fq पर Ri का Galois समूह आदेश d का चक्रीय है, जो फ़ील्ड ऑटोमोर्फिज़्म u → up द्वारा उत्पन्न होता है। इससे पता चलता है कि Ri में gi के मूल हैं

p_{i}(x),p_{i}(x^{q}),p_{i}\left(x^{q^{2}}\right),\ldots ,p_{i}\left(x^{q^{d-1}}\right).

पिछले एल्गोरिथम की तरह, यह एल्गोरिथम R के समान सबलजेब्रा B का उपयोग बर्लेकैंप के एल्गोरिथम के रूप में करता है, जिसे कभी-कभी "बेर्लेकैंप सबएजब्रा" कहा जाता है और इसे परिभाषित किया जाता है

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

B के एक उपसमुच्चय S को पृथक्कारी समुच्चय कहा जाता है, यदि प्रत्येक 1 ≤ i < j ≤ k के लिए s ∈ S ऐसा सम्मिलित हो कि $p_{i}(s)\neq p_{j}(s)$ पूर्ववर्ती एल्गोरिथम में, S के तत्वों को यादृच्छिक रूप से चुनकर एक अलग समुच्चय का निर्माण किया जाता है। शौप के एल्गोरिथ्म में, अलग करने वाले समुच्चय का निर्माण निम्नलिखित तरीके से किया जाता है। मान लीजिए R[Y] में s ऐसा है कि

{\begin{aligned}s&=(Y-x)\left(Y-x^{q}\right)\cdots \left(Y-x^{q^{d-1}}\right)\\&=s_{0}+\cdots +s_{d-1}Y^{d-1}+Y^{d}\end{aligned}}

फिर $\{s_{0},\dots ,s_{d-1}\}$ एक अलग समुच्चय है क्योंकि $p_{i}(s)=g_{i}$ i =1, ..., k के लिए (दो मोनिक बहुपदों की जड़ें समान हैं)। जैसा कि जीआई अलग-अलग इंडेक्स (i, j) की प्रत्येक जोड़ी के लिए अलग-अलग हैं, कम से कम एक गुणांक $p_{i}(s_{h})\neq p_{j}(s_{h}).$ को संतुष्ट करेगा।

एक अलग समुच्चय होने के बाद, शौप का एल्गोरिथ्म पूर्ववर्ती खंड के अंतिम एल्गोरिथ्म के रूप में आगे बढ़ता है, बस निर्देश को बदलकर रैखिक मानचित्र के कर्नेल में यादृच्छिक एच पर चुनें $v\to v^{q}-v{\pmod {f}}$ h + i चुनें जिसमें h in S और i in {1, ..., k−1} हो।

समय जटिलता

जैसा कि पिछले अनुभागों में वर्णित है, परिमित क्षेत्रों पर गुणनखंडन के लिए, बहुपद समय जटिलता के यादृच्छिक एल्गोरिदम हैं (उदाहरण के लिए कैंटर-ज़ासेनहॉस एल्गोरिथम) बहुपद औसत जटिलता के साथ नियतात्मक एल्गोरिदम भी हैं, उदाहरण के लिए शौप का एल्गोरिथ्म।

एक बहुपद सबसे खराब स्थिति वाली जटिलता के साथ एक नियतात्मक एल्गोरिथ्म का अस्तित्व अभी भी एक विवृत समस्या है।

राबिन की इरेड्यूसिबिलिटी का परीक्षण

विशिष्ट-घात गुणनखंड एल्गोरिथम की तरह, राबिन का एल्गोरिथम ऊपर बताए गए लेम्मा पर आधारित है।^[4] डिस्टिक्ट-घात फ़ैक्टराइज़ेशन एल्गोरिथम प्रत्येक d का परीक्षण करता है जो इनपुट बहुपद के आधे से अधिक घात नहीं है। राबिन का एल्गोरिदम लाभ उठाता है कि कम डी पर विचार करने के लिए कारकों की आवश्यकता नहीं होती है। अन्यथा, यह विशिष्ट-घात गुणनखंड एल्गोरिथम के समान है। यह निम्नलिखित तथ्य पर आधारित है।

$n/p_{i}=n_{i}$ , 1 ≤ i ≤ k बहुपद f के लिए Fq[x] में घात n, Fq[x] में अप्रासंगिक है यदि और केवल यदि $\gcd \left(f,x^{q^{n_{i}}}-x\right)=1$ , 1 ≤ i ≤ k के लिए, और f, $x^{q^{n}}-x$ को विभाजित करता है। वास्तव में, यदि f में n को विभाजित न करने वाली घात का कारक है, तो f x^{q^n}-x को विभाजित नहीं करता है; यदि f में n को विभाजित करने वाला गुणक है तो यह गुणक $x^{q^{n_{i}}}-x.$ में से कम से कम एक को विभाजित करता है।

Algorithm Rabin Irreducibility Test
    Input: A monic polynomial f in F_q[x] of degree n, 
        p₁, ..., p_k all distinct prime divisors of n.
    Output: Either "f is irreducible" or "f is reducible".

    for j = 1 to k do 
        ;
    for i = 1 to k do 
        ;
        g := जीसीडी(f, h);
        if g ≠ 1, then return "f is reducible" and STOP;
    end for;
    ;
    if g = 0, then return "f is irreducible", 
        else return "f is reducible"

इस एल्गोरिथ्म का मूल विचार गणना करना है $x^{q^{n_{i}}}{\bmod {f}}$ सबसे छोटे से शुरू $n_{1},\ldots ,n_{k}$ बार-बार वर्ग करके या परिमित क्षेत्र #Frobenius automorphisms का उपयोग करके, और फिर संवाददाता जीसीडी लेने के लिए। प्रारंभिक बहुपद अंकगणित का उपयोग करते हुए, फ्रोबेनियस ऑटोमोर्फिज्म के आव्यूह की गणना की आवश्यकता है $O(n^{2}(n+\log q))$ f में संचालन_q, की गणना

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

O(kn²) आगे के संचालन की आवश्यकता है और एल्गोरिथ्म को स्वयं O(kn²) संचालन की आवश्यकता है, Fq में कुल $O(n^{2}(n+\log q))$ संचालन देता है। तेजी से अंकगणित का उपयोग करना (जटिलता $O(n\log n)$ गुणा और भाग के लिए और $O(n(\log n)^{2})$ गणना के लिए) $x^{q^{n_{i}}}-x{\bmod {f}}$ की गणना बार-बार वर्ग करने से $O(n^{2}\log n\log q)$ है और एल्गोरिथ्म स्वयं $O(kn(\log n)^{2})$ है, जो कुल $O(n^{2}\log n\log q)$ देता है ) F_q में संचालन।

यह भी देखें

बेर्लेकैंप का एल्गोरिदम
कैंटर-ज़सेनहॉस एल्गोरिथम
बहुपद गुणनखंडन

संदर्भ

KEMPFERT,H (1969) On the Factorization of Polynomials Department of Mathematics, The Ohio State University,Columbus,Ohio 43210
Shoup,Victor (1996) Smoothness and Factoring Polynomials over Finite Fields Computer Science Department University of Toronto
Von Zur Gathen, J.; Panario, D. (2001). Factoring Polynomials Over Finite Fields: A Survey. Journal of Symbolic Computation, Volume 31, Issues 1–2, January 2001, 3--17.
Gao Shuhong, Panario Daniel,Test and Construction of Irreducible Polynomials over Finite Fields Department of mathematical Sciences, Clemson University, South Carolina, 29634–1907, USA. and Department of computer science University of Toronto, Canada M5S-1A4
Shoup, Victor (1989) New Algorithms for Finding Irreducible Polynomials over Finite Fields Computer Science Department University of Wisconsin–Madison
Geddes, Keith O.; Czapor, Stephen R.; Labahn, George (1992). Algorithms for computer algebra. Boston, MA: Kluwer Academic Publishers. pp. xxii+585. ISBN 0-7923-9259-0.

↑ Christophe Reutenauer, Mots circulaires et polynomes irreductibles, Ann. Sci. math Quebec, vol 12, no 2, pp. 275-285
↑ Flajolet, Philippe; Steayaert, Jean-Marc (1982), Automata, languages and programming, Lecture Notes in Comput. Sci., vol. 140, Aarhus: Springer, pp. 239–251, doi:10.1007/BFb0012773, ISBN 978-3-540-11576-2
↑ Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters 33:261-267, 1990
↑ Rabin, Michael (1980). "परिमित क्षेत्रों में संभाव्य एल्गोरिदम". SIAM Journal on Computing. 9 (2): 273–280. CiteSeerX 10.1.1.17.5653. doi:10.1137/0209024.

बाहरी संबंध

Some irreducible polynomials http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf
Field and Galois Theory :http://www.jmilne.org/math/CourseNotes/FT.pdf
Galois Field:http://designtheory.org/library/encyc/topics/gf.pdf
Factoring polynomials over finite fields: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf

[1] Christophe Reutenauer, Mots circulaires et polynomes irreductibles, Ann. Sci. math Quebec, vol 12, no 2, pp. 275-285

[2] Flajolet, Philippe; Steayaert, Jean-Marc (1982), Automata, languages and programming, Lecture Notes in Comput. Sci., vol. 140, Aarhus: Springer, pp. 239–251, doi:10.1007/BFb0012773, ISBN 978-3-540-11576-2

[3] Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters 33:261-267, 1990

[4] Rabin, Michael (1980). "परिमित क्षेत्रों में संभाव्य एल्गोरिदम". SIAM Journal on Computing. 9 (2): 273–280. CiteSeerX 10.1.1.17.5653. doi:10.1137/0209024.

[1]

[2]

[3]

[4]

Anonymous

Search

परिमित क्षेत्रों पर बहुपदों का गुणनखंडन

Namespaces

More

Page actions

Contents

भूमिका

परिमित क्षेत्र

अलघुकरणीय बहुपद

उदाहरण

समिश्रता

गुणनखंड एल्गोरिथ्म

बेर्लेकैंप का एल्गोरिथम

वर्ग मुक्त गुणनखंड

वर्ग मुक्त गुणनखंड का उदाहरण

अलग घात गुणनखंड

समान-घात गुणनखंड

कैंटर-ज़सेनहॉस एल्गोरिथम

विक्टर शौप का एल्गोरिथम

समय जटिलता

राबिन की इरेड्यूसिबिलिटी का परीक्षण

यह भी देखें

संदर्भ

टिप्पणियाँ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

परिमित क्षेत्रों पर बहुपदों का गुणनखंडन

भूमिका

परिमित क्षेत्र

अलघुकरणीय बहुपद

उदाहरण

समिश्रता

गुणनखंड एल्गोरिथ्म

बेर्लेकैंप का एल्गोरिथम

वर्ग मुक्त गुणनखंड

वर्ग मुक्त गुणनखंड का उदाहरण

अलग घात गुणनखंड

समान-घात गुणनखंड

कैंटर-ज़सेनहॉस एल्गोरिथम

विक्टर शौप का एल्गोरिथम

समय जटिलता

राबिन की इरेड्यूसिबिलिटी का परीक्षण

यह भी देखें

संदर्भ

टिप्पणियाँ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories