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

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

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

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

पृष्ठभूमि

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

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

एक परिमित क्षेत्र या गैल्वा क्षेत्र एक विक्त के साथ एक क्षेत्र है: परिमित क्रम (तत्वों की संख्या)। परिमित क्षेत्र की कोटि हमेशा एक अभाज्य संख्या या अभाज्य की शक्ति होती है। प्रत्येक प्रधान शक्ति के लिए q = p^r, समरूपता तक q तत्वों के साथ ठीक एक परिमित क्षेत्र मौजूद है। इस फ़ील्ड को GF(q) या 'F' के रूप में दर्शाया गया है_q. यदि p अभाज्य है, तो GF(p) क्रम p का अभाज्य क्षेत्र है; यह अवशेष वर्ग का क्षेत्र है# सर्वांगसमता वर्ग मॉड्यूलो p का छल्ला, और इसके p तत्वों को 0, 1, ..., p−1 के रूप में दर्शाया गया है। इस प्रकार {{nowrap|1=a = b}जीएफ (पी) में } का मतलब वही है a ≡ b (mod p).

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

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

इरेड्यूसिबल बहुपद हमें गैर-प्रमुख क्रम के परिमित क्षेत्रों का निर्माण करने की अनुमति देते हैं। वास्तव में, एक अभाज्य घात q के लिए, मान लीजिए 'F'_q क्यू तत्वों के साथ परिमित क्षेत्र बनें, समरूपता के लिए अद्वितीय। डिग्री n का एक बहुपद f एक से अधिक है, जो 'F' पर अप्रासंगिक है_q, डिग्री n के एक क्षेत्र विस्तार को परिभाषित करता है जो q के साथ क्षेत्र के लिए आइसोमॉर्फिक हैⁿ तत्व: इस विस्तार के तत्व n से कम डिग्री वाले बहुपद हैं; 'एफ' के एक तत्व द्वारा जोड़, घटाव और गुणा_q वे बहुपद हैं; दो तत्वों का उत्पाद बहुपद के रूप में उनके उत्पाद के एफ द्वारा विभाजन का शेष है; एक तत्व के व्युत्क्रम की गणना विस्तारित GCD एल्गोरिथम द्वारा की जा सकती है (बहुपद सबसे बड़ा सामान्य विभाजक देखें)।

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

परिमित क्षेत्रों पर इरेड्यूसिबल बहुपद भी फीडबैक शिफ्ट रजिस्टरों और एफ पर असतत लघुगणक का उपयोग करके छद्म यादृच्छिक संख्या जनरेटर के लिए उपयोगी होते हैं।_2ⁿ.

F पर डिग्री n के इरेड्यूसिबल मोनिक बहुपदों की संख्या_q नेकलेस की संख्या है (कॉम्बिनेटरिक्स) # एपेरियोडिक नेकलेस, नेकलेस पॉलीनोमियल द्वारा दिया गया है। मोरो का नेकलेस-काउंटिंग फंक्शन एम_q(एन)। बारीकी से संबंधित हार समारोह एन_q(एन) डिग्री एन के मोनिक बहुपदों की गणना करता है जो प्राथमिक हैं (एक अलघुकरणीय की शक्ति); या वैकल्पिक रूप से सभी डिग्री d के अलघुकरणीय बहुपद जो n को विभाजित करते हैं।^[1]

उदाहरण

बहुपद P = x⁴ + 1 Q पर अलघुकरणीय है लेकिन किसी परिमित क्षेत्र पर नहीं।

एफ के किसी भी फील्ड एक्सटेंशन पर₂, 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).$

जटिलता

बहुपद फैक्टरिंग एल्गोरिदम मूल बहुपद संचालन का उपयोग करते हैं जैसे कि उत्पाद, डिवीजन, जीसीडी, एक बहुपद मॉडुलो की शक्तियाँ, आदि। एक गुणन एल्गोरिथ्म # बहुपद के दो बहुपदों का बहुपद गुणन अधिकतम एन बिग ओ नोटेशन में किया जा सकता है। ओ (एन)²) एफ में संचालन_q शास्त्रीय अंकगणित का उपयोग करते हुए, या O(nlog(n) log(log(n)) ) संचालन 'F' में_q गुणन एल्गोरिथ्म का उपयोग करना # बड़े इनपुट के लिए तेज़ गुणन एल्गोरिदम | तेज अंकगणित। एक यूक्लिडियन विभाजन (शेष के साथ विभाजन) एक ही समय सीमा के भीतर किया जा सकता है। डिग्री के दो बहुपदों के बीच एक बहुपद के सबसे बड़े सामान्य विभाजक की लागत को O(n) के रूप में लिया जा सकता है²) एफ में संचालन_q शास्त्रीय तरीकों का उपयोग करना, या O(nlog²(n) 'F' में लॉग(लॉग(n)) ऑपरेशंस_q तेज़ तरीकों का उपयोग करना। अधिक से अधिक n डिग्री वाले बहुपदों h, g के लिए, घातांक h^q mod g को O(log(q)) बहुपद गुणनफलों के साथ किया जा सकता है, जिसमें वर्ग विधि द्वारा घातांक का उपयोग किया जाता है, अर्थात O(n)²लॉग (क्यू)) संचालन 'एफ' में_q शास्त्रीय तरीकों का उपयोग करना, या 'एफ' में ओ (एनलॉग (क्यू) लॉग (एन) लॉग (लॉग (एन))) संचालन_q तेज़ तरीकों का उपयोग करना।

अनुवर्ती एल्गोरिदम में, एफ में अंकगणितीय परिचालनों की संख्या के संदर्भ में जटिलताओं को व्यक्त किया जाता है_q, बहुपदों के अंकगणित के लिए शास्त्रीय एल्गोरिदम का उपयोग करना।

फैक्टरिंग एल्गोरिदम

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

#वर्ग-मुक्त गुणनखंड|वर्ग-मुक्त गुणनखंड
#अलग-डिग्री गुणनखंड|अलग-डिग्री गुणनखंड
# समान-डिग्री गुणनखंड|समान-डिग्री गुणनखंड

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

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

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

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

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

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

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

'एल्गोरिदम': 'एसएफएफ' (स्क्वायर-फ्री फैक्टराइजेशन)
    'इनपुट': 'एफ' में एक मोनिक बहुपद एफ_q[एक्स] जहां क्यू = पी^मी
    'आउटपुट': f का वर्ग-मुक्त गुणनखंडन
    आर ← 1
   
    # डब्ल्यू को एफ के सभी कारकों का उत्पाद (बहुलता के बिना) बनाएं
    # बहुलता p से विभाज्य नहीं है
    सी ← 'जीसीडी' (एफ, एफ')
    डब्ल्यू ← एफ/सी
   
    # चरण 1: डब्ल्यू में सभी कारकों की पहचान करें
    मैं ← 1
    'जबकि' डब्ल्यू ≠ 1 'करो'
        वाई ← 'जीसीडी' (डब्ल्यू, सी)
        एफएसी ← डब्ल्यू / वाई
        आर ← आर · तथ्य^{मैं
        डब्ल्यू ← वाई; सी ← सी / वाई; मैं ← मैं + 1
    'अंत जबकि'
    # c अब f के शेष कारकों का गुणनफल (बहुलता के साथ) है
   
    # चरण 2: पुनरावर्तन का उपयोग करके शेष सभी कारकों की पहचान करें
    # ध्यान दें कि ये f के कारक हैं जिनकी बहुलता p से विभाज्य है
    'अगर' सी ≠ 1 'तो'
        सी ← सी^{1/पैसा}
        आर ← आर·'एसएफएफ'(सी)^{पी</सुप>
    'अगर अंत'
   
    'आउटपुट' (आर)}}

विचार यह है कि समान बहुलता वाले 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$ और हम while पाश में प्रवेश करते हैं। एक लूप के बाद हमारे पास है $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$ , यह एक पूर्ण घन होना चाहिए। का घनमूल $c$ , प्रतिस्थापित करके प्राप्त किया गया $x 3$ द्वारा $x$ है $x 2 + 1$ , और वर्ग-मुक्त प्रक्रिया को पुनरावर्ती रूप से कॉल करना यह निर्धारित करता है कि यह वर्ग-मुक्त है। इसलिए, इसे घन करना और इसे के मूल्य के साथ जोड़ना $R$ उस बिंदु पर वर्ग-मुक्त अपघटन देता है

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

अलग डिग्री गुणनखंड

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

एल्गोरिथम डिस्टिक्ट-डिग्री फ़ैक्टराइज़ेशन (DDF)
    इनपुट: एक मोनिक वर्ग-मुक्त बहुपद   $f \in F q [x]$ 
    आउटपुट: सभी जोड़ियों का सेट  $(g, d)$ , ऐसा है कि              
 $f$  डिग्री का एक अप्रासंगिक कारक है  $d$  और

$g$ के सभी मोनिक इरेड्यूसिबल कारकों का उत्पाद है $f$ डिग्री $d$ .

    शुरू

$i:=1;\qquad S:=\emptyset ,\qquad f^{*}:=f;$ जबकि $\deg f^{*}\geq 2i$ करना

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

अगर $g \neq 1$ , तब

 $S:=S\cup \{(g,i)\}$ ;

$f^{*}:=f^{*}/g$ अगर अंत $i := i + 1;$

        समाप्त जबकि;
        अगर  $f^{*}\neq 1$ , तब  $S:=S\cup \{(f^{*},\deg f^{*})\}$ ;
        अगर  $S=\emptyset$ , फिर लौटें  ${(f, 1)}$ ,
            वरना लौट जाओ  $S$ 
    अंत

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

<ब्लॉककोट>लेम्मा. i के लिए ≥ 1 बहुपद

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

एफ में सभी मोनिक इरेड्यूसबल बहुपदों का उत्पाद है_q[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^{*},

दो तरीके हैं:

विधि I. के मान से प्रारंभ करें
$x^{q^{i-1}}\mod f^{*}$

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

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

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

$O\left(\log(q)\deg(f)^{3}\right)$
संपूर्ण एल्गोरिथम के लिए अंकगणितीय संक्रियाएं।

<ब्लॉककोट>विधि II. इस तथ्य का उपयोग करते हुए कि qवीं शक्ति 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).

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

समान-डिग्री गुणनखंड

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

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

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

'एल्गोरिदम' कैंटर-ज़सेनहॉस एल्गोरिथम।
    'इनपुट:' एक परिमित क्षेत्र 'एफ'_q विषम क्रम का क्यू।
           'एफ' में एक मोनिक वर्ग मुक्त बहुपद एफ_q[x] डिग्री n = rd,
                जिसमें डिग्री डी के प्रत्येक आर ≥ 2 अपरिवर्तनीय कारक हैं
    'आउटपुट:' f के मोनिक इरेड्यूसिबल कारकों का सेट।

    गुणनखंड := {f};
    'जबकि' आकार (कारक) <आर 'करो',
        'एफ' में एच चुनें_q[x] डिग्री के साथ (ज) < n यादृच्छिक पर;

$g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}$ प्रत्येक u के लिए deg(u) > d वाले गुणकों में करें

            अगर gcd(g, u) ≠ 1 और gcd(g, u) ≠ u, तो
                कारक:= कारक $\,\setminus \,\{u\}\cup \{(\gcd(g,u),u/\gcd(g,u))\}$ ;
            अगर अंत
    हमेशा के लिए

    वापसी कारक

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

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

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

यह दिखाया गया है कि एल्गोरिथम के जबकि लूप के पुनरावृत्तियों की औसत संख्या से कम है $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}}.

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

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

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

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

चलो जी = जी₁ ... जी_kवांछित गुणनखंड हो, जहाँ g_iडिग्री डी के विशिष्ट मोनिक इरेड्यूसबल बहुपद हैं। चलो एन = डिग्री (जी) = केडी। हम वलय (गणित) पर विचार करते हैं R = 'F'_q[x]/g और x द्वारा R में x की छवि को भी निरूपित करें। रिंग R फ़ील्ड R का प्रत्यक्ष उत्पाद है_i= 'एफ'_q[एक्स] / जी_i, और हम पी द्वारा निरूपित करते हैं_iR से R पर प्राकृतिक समरूपता_i. द गाल्वा समूह ऑफ़ आर_i'एफ' से अधिक_q क्रम d का चक्रीय है, जो फील्ड ऑटोमोर्फिज्म u → u द्वारा उत्पन्न होता है^{पी</सुप>. यह इस प्रकार है कि जी की जड़ें_iआर में_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 के समान subalgebra 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अलग-अलग इंडेक्स (i, j) की प्रत्येक जोड़ी के लिए जोड़ीदार अलग-अलग हैं, कम से कम गुणांक एस में से एक_hसंतुष्ट करेगा $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 का परीक्षण करता है जो इनपुट बहुपद के आधे से अधिक डिग्री नहीं है। राबिन का एल्गोरिदम लाभ उठाता है कि कम डी पर विचार करने के लिए कारकों की आवश्यकता नहीं होती है। अन्यथा, यह विशिष्ट-डिग्री गुणनखंड एल्गोरिथम के समान है। यह निम्नलिखित तथ्य पर आधारित है।

चलो पी₁, ..., पी_k, n के सभी प्रधान विभाजक हों, और निरूपित करें $n/p_{i}=n_{i}$ , 'F' में 1 ≤ i ≤ k बहुपद f के लिए_q[x] की डिग्री n 'F' में अलघुकरणीय है_q[एक्स] अगर और केवल अगर $\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.$ एल्गोरिथम राबिन इरेड्यूसबिलिटी टेस्ट

    इनपुट: एफ में एक मोनिक बहुपद एफ_q[एक्स] डिग्री एन,
        पी₁, ..., पी_kn के सभी विशिष्ट प्रधान भाजक।
    'आउटपुट': या तो f इर्रिड्यूसिबल है या f रिड्यूसिबल है।

    'for' j = 1 to k 'do'         
 $n_{j}=n/p_{j}$ ;
    for i = 1 to k करना         
 $h:=x^{q^{n_{i}}}-x{\bmod {f}}$ ;
        जी: = जीसीडी (एफ, एच);
        'अगर' जी ≠ 1, 'फिर वापसी' च कम हो जाती है 'और बंद करो';
    'के लिए अंत';

$g:=x^{q^{n}}-x{\bmod {f}}$ ;

    अगर g = 0, तो रिटर्न f इर्रिड्यूसिबल है,
        अन्यथा वापसी एफ कम करने योग्य है

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

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

ओ की जरूरत है (एन³) आगे के संचालन, और एल्गोरिथम को स्वयं O(kn²) संचालन, कुल दे रहा है $O(n^{2}(n+\log q))$ एफ में संचालन_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)$ एफ में संचालन_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