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

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

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

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

भूमिका

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

Main article: परिमित क्षेत्र

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

परिमित क्षेत्र या गैलोज़ क्षेत्र एक परिमित क्रम (तत्वों की संख्या) वाला क्षेत्र है। परिमित क्षेत्र का क्रम सदैव अभाज्य संख्या या अभाज्य संख्या की घात होता है। प्रत्येक अभाज्य घात 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 द्वारा विभाजन का शेष है। तत्व के व्युत्क्रम की गणना विस्तारित gcd एल्गोरिथ्म द्वारा की जा सकती है। जिसके लिए बीजगणितीय विस्तार का अंकगणित देखें।

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

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

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

उदाहरण

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

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

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

समिश्रता

बहुपद गुणनखंड एल्गोरिदम आधारिक बहुपद संचालन जैसे उत्पाद, विभाजन, gcd एक बहुपद मॉडुलो की घातयों का उपयोग करते हैं। प्रारम्भिक अंकगणित का उपयोग करके 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 में अंकगणितीय संचालन की संख्या के संदर्भ में समिश्रताएं व्यक्त की जाती हैं।

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

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

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

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

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

Main article: बेर्लेकैंप का एल्गोरिदम

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

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

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

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

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

Algorithm: SFF (Square-Free Factorization)
    Input: A monic polynomial f in Fq[x] where q = pm
    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 ← gcd(f, f′)
    w ← f/c 
   
    # Step 1: Identify all factors in w
    i ← 1 
    while w ≠ 1 do
        y ← gcd(w, c)
        fac ← w / y
        R ← R · faci
        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 ← c1/p
        R ← R·SFF(c)p
    end if 
   
    Output(R)

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

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

माना कि

$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 है और हम व्हील लूप में प्रवेश करते हैं। व्हील लूप के बाद हमारे पास y = x + 2, z = x + 1 और R = x + 1 के साथ i = 2, w = x + 2 और c = x⁸ + x⁷ + x⁶ + x²+x+1 है। व्हील लूप के माध्यम से दूसरी बार y = x + 2, z = 1, R = x + 1 के साथ i = 3, w = x + 2 और c = x⁷ + 2x⁶ + x + 2 के माध्यम से देता है। तीसरी बार के माध्यम से व्हील लूप भी R नहीं परिवर्तित होता है। चौथी बार व्हील लूप के माध्यम से हमें y = 1, z = x + 2, R = (x + 1)(x + 2)⁴ के साथ i = 5, w = 1 और c = x⁶ + 1 प्राप्त होता है चूंकि w = 1, हम व्हील लूप से बाहर निकलते हैं। चूँकि c ≠ 1, यह एक पूर्ण घन होना चाहिए और x³ को x से प्रतिस्थापित करके प्राप्त c का घनमूल x² + 1 है और वर्ग-मुक्त प्रक्रिया को पुनरावर्ती रूप से कॉल करके यह निर्धारित करता है कि यह वर्ग-मुक्त है। इसलिए इसे R के मान के साथ उस बिंदु पर संयोजित करना वर्ग-मुक्त अपघटन देता है:

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

विशिष्ट घात गुणनखंडन

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

Algorithm Distinct-degree factorization(DDF)
    Input: A monic square-free polynomial f ∈ Fq[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]$

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

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

हालाँकि,

$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 घात F_q पर एक रैखिक मानचित्र है हम इसके आव्यूह की गणना कर सकते हैं:

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

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

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

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

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

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

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

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

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

Algorithm Cantor–Zassenhaus algorithm.
    Input: A finite field Fq of odd order q.
           A monic square free polynomial f in Fq[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 Fq[x] with deg(h) < n at random;
        
        for each u in Factors with deg(u) > d do
            if gcd(g, u) ≠ 1 and gcd(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}}.$

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

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

विशिष्ट स्थिति में जहां 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}}.$

वैधता का प्रमाण उपरोक्त के समान है।

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

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

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

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

मान लीजिए कि g = g1 ... gk वांछित गुणनखंड है, जहां gⁱ घात d के विशिष्ट मोनिक अलघुकरणीय बहुपद हैं। माना कि n = deg(g) = kd वलय R = F_q[x]/g पर विचार करते हैं और R में x की छवि को x द्वारा भी निरूपित करते हैं। वलय R क्षेत्र R_i = F_q[x]/g_i, का प्रत्यक्ष उत्पाद है और हम प्राकृतिक p_i द्वारा निरूपित करते हैं R से R_i पर समाकारिता F_q पर R_i का गाल्वा क्षेत्र समूह क्रम d का चक्रीय है जो क्षेत्र स्वसमाकृतिकता u → u^p द्वारा उत्पन्न होता है। इससे पता चलता है कि R_i में g_i के मूल हैं:

$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 के लिए दो मोनिक बहुपदों की घातें समान हैं जैसा कि g_i अलग-अलग सारणी (i, j) की प्रत्येक जोड़ी के लिए अलग-अलग हैं जो कम से कम एक गुणांक $p_{i}(s_{h})\neq p_{j}(s_{h})$ को संतुष्ट करता है।

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

समय सम्मिश्रता

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

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

राबिन की अपरिवर्तनीयता का परीक्षण

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

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

Algorithm Rabin Irreducibility Test
    Input: A monic polynomial f in Fq[x] of degree n, 
        p1, ..., pk 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 := gcd(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}$ से प्रारम्भ करके, बार-बार वर्ग करके या परिमित क्षेत्र फ्रोबेनियस स्वसमाकृतिकता का उपयोग करके पुनः संवाददाता gcd प्राप्त करने के लिए प्रारंभिक बहुपद अंकगणित का उपयोग करते हुए, फ्रोबेनियस स्वसमाकृतिकता के आव्यूह की गणना के लिए Fq में फलन $O(n^{2}(n+\log q))$ की आवश्यकता होती है।

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

इसमे प्रायः O(n³) संक्रियक की आवश्यकता होती है और एल्गोरिथ्म को स्वयं O(kn²) संक्रियक की आवश्यकता होती है क्योकि F_q में कुल $O(n^{2}(n+\log q))$ संक्रियक होते है। गुणन और विभाजन के लिए अंकगणित सम्मिश्रता $O(n\log n)$ और GCD गणना के लिए $O(n(\log n)^{2})$ का उपयोग करके $x^{q^{n_{i}}}-x{\bmod {f}}$ की गणना करते है जहाँ वर्ग $O(n^{2}\log n\log q)$ और एल्गोरिथ्म स्वयं $O(kn(\log n)^{2})$ संक्रियक है क्योकि F_q में कुल $O(n^{2}(n+\log 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.

बाहरी संबंध

• 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