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

Latest revision as of 17:24, 30 June 2023

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

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

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

भूमिका

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

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

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

समिश्रता

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

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

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

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

एक महत्वपूर्ण अपवाद बेर्लेकैंप का एल्गोरिथम है, जो चरण 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 घातों की गणना की जाती है। हालांकि, इस स्थिति में u का एल्गोरिदम अधिक कुशल है क्योंकि यह कम घात के बहुपदों के सबसे बड़े सामान्य विभाजक की गणना करता है। एक परिणाम यह है कि जब पूर्णांकों पर एक बहुपद का गुणनखंड किया जाता है तो निम्न एल्गोरिथम का उपयोग नहीं किया जाता है जो पहले पूर्णांकों पर वर्ग-मुक्त गुणनखंडन की गणना करता है और परिणामी बहुपदों का गुणनखंड करने के लिए p को चुनता है जैसे कि वे वर्ग-मुक्त मॉड्यूलो 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 ← 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 · 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 से विभाज्य बहुलता है जिसका अर्थ है कि वे 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 + 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, हम व्हील लूप से बाहर निकलते हैं। चूँकि $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]

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).

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

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

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

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

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

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 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))$ है।^[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}}.

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

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

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

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

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

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

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

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

विशिष्ट-घात गुणनखंड एल्गोरिथम की तरह राबिन का एल्गोरिथम ऊपर बताए गए लेम्मा पर आधारित है।^[4] विशिष्ट-घात गुणनखंडन एल्गोरिथम प्रत्येक 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 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 := 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.

↑ 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

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

Namespaces

More

Page actions

Latest revision as of 17:24, 30 June 2023

Contents

भूमिका

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

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

उदाहरण

समिश्रता

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

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

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

टिप्पणियाँ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
 {{Short description|None}}
-गणित और [[कंप्यूटर बीजगणित]] में [[बहुपद]]ों के गुणनखंडन में इसे [[अलघुकरणीय बहुपद]] के [[उत्पाद (गणित)]] में विघटित करना शामिल है। यह अपघटन सैद्धांतिक रूप से संभव है और किसी भी [[क्षेत्र (गणित)]] में गुणांक वाले बहुपदों के लिए अद्वितीय है, लेकिन एक [[ कलन विधि ]] के माध्यम से कारककरण की गणना की अनुमति देने के लिए गुणांक के क्षेत्र पर मजबूत प्रतिबंधों की आवश्यकता होती है। व्यवहार में, एल्गोरिदम को केवल बहुपदों के लिए [[परिमित क्षेत्र]] में गुणांक के साथ, परिमेय के क्षेत्र में या उनमें से किसी एक के परिमित रूप से उत्पन्न क्षेत्र विस्तार के लिए डिज़ाइन किया गया है।
-परिमेय संख्याओं पर [[बहुभिन्नरूपी बहुपद]]ों के मामले सहित सभी गुणनखंडन एल्गोरिदम, इस मामले में समस्या को कम करते हैं; बहुपद गुणनखंड देखें। इसका उपयोग परिमित क्षेत्रों के विभिन्न अनुप्रयोगों के लिए भी किया जाता है, जैसे [[कोडिंग सिद्धांत]] ([[चक्रीय अतिरेक]] कोड और BCH कोड), [[क्रिप्टोग्राफी]] ([[अण्डाकार वक्र क्रिप्टोग्राफी]] के माध्यम से [[सार्वजनिक कुंजी क्रिप्टोग्राफी]]), और [[कम्प्यूटेशनल संख्या सिद्धांत]]।
+गणित और [[कंप्यूटर बीजगणित]] में एक '''[[बहुपद]] के गुणनखंड''' में इसे [[अलघुकरणीय बहुपद|अलघुकरणीय]] कारकों के उत्पाद में विघटित करना सम्मिलित है। यह अपघटन सैद्धांतिक रूप से संभव है और किसी भी [[क्षेत्र (गणित)|क्षेत्र]] में गुणांक वाले बहुपदों के लिए अद्वितीय है, लेकिन एक [[ कलन विधि |एल्गोरिदम]] के माध्यम से कारक की गणना की स्वीकृति देने के लिए गुणांक के क्षेत्र पर समिश्र प्रतिबंधों की आवश्यकता होती है। गणना में एल्गोरिदम को केवल बहुपदों के लिए परिमित क्षेत्र में गुणांक के साथ परिमेय के क्षेत्र में या उनमें से किसी एक के साथ परिमित रूप से उत्पन्न क्षेत्र विस्तार के लिए निर्मित किया गया है।
-एक परिमित क्षेत्र में गुणांक के मामले में बहुभिन्नरूपी बहुपदों के बहुभिन्नरूपी बहुपदों के गुणनखंडन में कोई विशिष्टता नहीं होती है, इस लेख में केवल एक चर वाले बहुपदों पर विचार किया जाता है।
+परिमेय संख्याओं पर [[बहुभिन्नरूपी बहुपद|बहुचर बहुपदों]] की स्थिति के सहित सभी गुणनखंडन एल्गोरिदम की इस स्थिति में समस्या को अपेक्षाकृत कम करते हैं जिसके लिए बहुपद गुणनखंड देखें। इसका उपयोग परिमित क्षेत्रों के विभिन्न अनुप्रयोगों जैसे कि [[कोडिंग सिद्धांत]] ([[चक्रीय अतिरेक]] कोड और बीसीएच कोड), [[क्रिप्टोग्राफी]] ([[अण्डाकार वक्र क्रिप्टोग्राफी|दीर्घवृत्तीय]] वक्रों के माध्यम से [[सार्वजनिक कुंजी क्रिप्टोग्राफी]]) और [[कम्प्यूटेशनल संख्या सिद्धांत]] के लिए भी किया जाता है।
-== पृष्ठभूमि ==
+परिमित क्षेत्र में गुणांक की स्थिति में के बहुचर बहुपदों के गुणनखंडन में कोई विशिष्टता नहीं होती है। इस लेख में केवल एक चर वाले बहुपदों पर विचार किया जाता है।
+== भूमिका ==
 === परिमित क्षेत्र ===
-{{main article|Finite field}}
+{{main article|परिमित क्षेत्र}}
-परिमित क्षेत्रों के सिद्धांत, जिनकी उत्पत्ति [[गॉस]] और गैलोज़ के कार्यों में देखी जा सकती है, ने गणित की विभिन्न शाखाओं में एक भूमिका निभाई है। गणित और विज्ञान जैसे कंप्यूटर विज्ञान के अन्य विषयों में अवधारणा की प्रयोज्यता के कारण परिमित क्षेत्रों में रुचि का पुनरुत्थान हुआ है और यह आंशिक रूप से कोडिंग सिद्धांत और क्रिप्टोग्राफी में महत्वपूर्ण अनुप्रयोगों के कारण है। परिमित क्षेत्रों के अनुप्रयोग क्रिप्टोग्राफी, कंप्यूटर बीजगणित और कोडिंग सिद्धांत में इनमें से कुछ विकास पेश करते हैं।
-एक परिमित क्षेत्र या गैल्वा क्षेत्र एक विक्त के साथ एक क्षेत्र है: परिमित क्रम (तत्वों की संख्या)। परिमित क्षेत्र की कोटि हमेशा एक [[अभाज्य संख्या]] या अभाज्य की शक्ति होती है। प्रत्येक प्रधान शक्ति के लिए {{nowrap|1=''q'' = ''p''<sup>''r''</sup>}}, समरूपता [[तक]] q तत्वों के साथ ठीक एक परिमित क्षेत्र मौजूद है। इस फ़ील्ड को GF(q) या 'F' के रूप में दर्शाया गया है<sub>''q''</sub>. यदि p अभाज्य है, तो GF(p) क्रम p का अभाज्य क्षेत्र है; यह अवशेष वर्ग का क्षेत्र है# सर्वांगसमता वर्ग मॉड्यूलो p का छल्ला, और इसके p तत्वों को 0, 1, ..., p−1 के रूप में दर्शाया गया है। इस प्रकार {{nowrap|1=''a'' = ''b''}जीएफ (पी) में } का मतलब वही है {{nowrap|''a'' ≡ ''b'' (mod ''p'')}}.
+परिमित क्षेत्रों के सिद्धांत प्रायः जिनकी उत्पत्ति गॉस और गैलोज़ के कार्यों में देखी जा सकती है, गॉस ने गणित की विभिन्न शाखाओं में एक भूमिका निभाई है। गणित और विज्ञान जैसे कंप्यूटर विज्ञान के अन्य विषयों में अवधारणा की प्रयोज्यता के कारण परिमित क्षेत्रों में रुचि का पुनरुत्थान हुआ है और यह आंशिक रूप से कोडिंग सिद्धांत और क्रिप्टोग्राफी में महत्वपूर्ण अनुप्रयोगों के कारण है। परिमित क्षेत्रों के अनुप्रयोग क्रिप्टोग्राफी, कंप्यूटर बीजगणित और कोडिंग सिद्धांत में इनमें से कुछ विकास प्रस्तुत करते हैं।
+परिमित क्षेत्र या गैलोज़ क्षेत्र एक परिमित क्रम (तत्वों की संख्या) वाला क्षेत्र है। परिमित क्षेत्र का क्रम सदैव [[अभाज्य संख्या]] या अभाज्य संख्या की घात होता है। प्रत्येक अभाज्य घात {{nowrap|1=''q'' = ''p''<sup>''r''</sup>}} के लिए समरूपता q तत्वों के साथ ठीक एक परिमित क्षेत्र सम्मिलित है। इस क्षेत्र को GF(q) या Fq द्वारा निरूपित किया जाता है। यदि p अभाज्य है, तो ''GF(p)'' का क्रम p अभाज्य क्षेत्र है। यह शेष संख्याए मॉडुलो p का क्षेत्र है और इसके p तत्व को 0, 1, ..., p−1 दर्शाया गया है। इस प्रकार ''GF(p)'' में a = b का अर्थ {{nowrap|''a'' ≡ ''b'' (mod ''p'')}} के समान है।
 === अलघुकरणीय बहुपद ===
-F को एक परिमित क्षेत्र होने दें। सामान्य क्षेत्रों के लिए, F [x] में एक गैर-निरंतर बहुपद f को F पर अलघुकरणीय बहुपद कहा जाता है यदि यह सकारात्मक डिग्री के दो बहुपदों का गुणनफल नहीं है। धनात्मक कोटि का एक बहुपद जो F पर अप्रासंगिक नहीं है, F पर अपचयित कहलाता है।
+माना कि F एक परिमित क्षेत्र है। सामान्य क्षेत्रों के लिए F [x] में एक गैर-निरंतर बहुपद f को F पर अप्रासंगिक कहा जाता है यदि यह धनात्मक घात के दो बहुपदों का गुणनफल नहीं है। धनात्मक घात का एक बहुपद जो F पर अप्रासंगिक नहीं है, F पर अपचयित कहलाता है।
-इरेड्यूसिबल बहुपद हमें गैर-प्रमुख क्रम के परिमित क्षेत्रों का निर्माण करने की अनुमति देते हैं। वास्तव में, एक अभाज्य घात q के लिए, मान लीजिए 'F'<sub>''q''</sub> क्यू तत्वों के साथ परिमित क्षेत्र बनें, समरूपता के लिए अद्वितीय। डिग्री n का एक बहुपद f एक से अधिक है, जो 'F' पर अप्रासंगिक है<sub>''q''</sub>, डिग्री n के एक क्षेत्र विस्तार को परिभाषित करता है जो q के साथ क्षेत्र के लिए आइसोमॉर्फिक है<sup>n</sup> तत्व: इस विस्तार के तत्व n से कम डिग्री वाले बहुपद हैं; 'एफ' के एक तत्व द्वारा जोड़, घटाव और गुणा<sub>''q''</sub> वे बहुपद हैं; दो तत्वों का उत्पाद बहुपद के रूप में उनके उत्पाद के एफ द्वारा विभाजन का शेष है; एक तत्व के व्युत्क्रम की गणना विस्तारित GCD एल्गोरिथम द्वारा की जा सकती है ([[बहुपद सबसे बड़ा सामान्य विभाजक]] देखें)।
-यह इस प्रकार है कि, गैर प्रधान क्रम के परिमित क्षेत्र में गणना करने के लिए, एक इरेड्यूसिबल बहुपद उत्पन्न करने की आवश्यकता है। इसके लिए, सामान्य विधि यादृच्छिक रूप से एक बहुपद लेना है और इसे अप्रासंगिकता के लिए परीक्षण करना है। क्षेत्र में गुणन की दक्षता के लिए, आकार x के बहुपदों की खोज करना सामान्य है<sup>n</sup> + ax + b.{{Citation needed|date=February 2014}}
-परिमित क्षेत्रों पर इरेड्यूसिबल बहुपद भी फीडबैक शिफ्ट रजिस्टरों और एफ पर [[असतत लघुगणक]] का उपयोग करके छद्म यादृच्छिक संख्या जनरेटर के लिए उपयोगी होते हैं।<sub>2<sup>''n''</sup></sub>.
+अलघुकरणीय बहुपद हमें गैर-अभाज्य क्रम के परिमित क्षेत्रों का निर्माण करने की स्वीकृति देते हैं। वास्तव में एक अभाज्य घात q के लिए माना कि F<sub>q</sub> तत्वों के साथ एक परिमित क्षेत्र है जो कि समरूपता तक अद्वितीय है। घात n का एक बहुपद f एक से अधिक है, जो F<sub>q</sub> से अधिक अपरिवर्तनीय है, घात n के क्षेत्र विस्तार को परिभाषित करता है जो q<sup>n</sup> तत्वों के साथ क्षेत्र के लिए समरूप है इस विस्तार के तत्व n से कम घात के बहुपद हैं, घटाव और गुणा F<sub>q</sub> के एक तत्व द्वारा बहुपदों में से दो तत्वों का उत्पाद बहुपद के रूप में उनके उत्पाद के f द्वारा विभाजन का शेष है। तत्व के व्युत्क्रम की गणना विस्तारित gcd एल्गोरिथ्म द्वारा की जा सकती है। जिसके लिए बीजगणितीय विस्तार का अंकगणित देखें।
-F पर डिग्री n के इरेड्यूसिबल [[मोनिक बहुपद]]ों की संख्या<sub>''q''</sub> नेकलेस की संख्या है (कॉम्बिनेटरिक्स) # एपेरियोडिक नेकलेस, नेकलेस पॉलीनोमियल द्वारा दिया गया है। मोरो का नेकलेस-काउंटिंग फंक्शन एम<sub>''q''</sub>(एन)। बारीकी से संबंधित हार समारोह एन<sub>''q''</sub>(एन) डिग्री एन के मोनिक बहुपदों की गणना करता है जो प्राथमिक हैं (एक अलघुकरणीय की शक्ति); या वैकल्पिक रूप से सभी डिग्री d के अलघुकरणीय बहुपद जो n को विभाजित करते हैं।<ref>Christophe Reutenauer, ''Mots circulaires et polynomes irreductibles'', Ann. Sci. math Quebec, vol 12, no 2, pp. 275-285</ref>
+यह इस प्रकार है कि गैर अभाज्य क्रम के परिमित क्षेत्र में गणना करने के लिए एक अलघुकरणीय बहुपद उत्पन्न करने की आवश्यकता होती है। इसके लिए सामान्य विधि यादृच्छिक रूप से एक बहुपद लेना है और इसे अप्रासंगिकता के लिए परीक्षण करना है। क्षेत्र में गुणा की दक्षता के लिए xn + ax + b के आकार के बहुपदों की खोज करना सामान्य है।{{Citation needed|date=February 2014}}
+परिमित क्षेत्रों पर अलघुकरणीय बहुपद भी पुनर्निवेशन विस्थापन पंजी और F<sub>2</sub><sup>n</sup> पर असतत लघुगणक का उपयोग करके छद्म यादृच्छिक संख्या निर्माण के लिए उपयोगी होते हैं।
+F<sub>q</sub> पर घात n के अलघुकरणीय मोनिक बहुपदों की संख्या एपरियोडिक नेकलेस की संख्या है, जो मोरो के नेकलेस-गणना फलन Mq(n) द्वारा दी गई है। सूक्ष्मता से संबंधित नेकलेस फलन Nq(n) घात n के मोनिक बहुपदों की गणना करता है जो प्राथमिक (अलघुकरणीय की घात) या वैकल्पिक रूप से सभी घात d के अलघुकरणीय बहुपद है जो n को विभाजित करते हैं।<ref>Christophe Reutenauer, ''Mots circulaires et polynomes irreductibles'', Ann. Sci. math Quebec, vol 12, no 2, pp. 275-285</ref>
 === उदाहरण ===
-बहुपद {{nowrap|1=''P'' = ''x''<sup>4</sup> + 1}} Q पर अलघुकरणीय है लेकिन किसी परिमित क्षेत्र पर नहीं।
+बहुपद {{nowrap|1=''P'' = ''x''<sup>4</sup> + 1}}, Q पर अप्रासंगिक है लेकिन किसी परिमित क्षेत्र पर अप्रासंगिक नहीं है:
-* एफ के किसी भी फील्ड एक्सटेंशन पर<sub>2</sub>, {{nowrap|1=''P'' = (''x'' + 1)<sup>4</sup>}}.
+* किसी भी क्षेत्र विस्तार पर F<sub>2</sub> ,{{nowrap|1=''P'' = (''x'' + 1)<sup>4</sup>}} है।
-* हर दूसरे परिमित क्षेत्र में, -1, 2 और -2 में से कम से कम एक वर्ग है, क्योंकि दो गैर-वर्गों का गुणनफल एक वर्ग है और इसलिए हमारे पास है
+* प्रत्येक दूसरे परिमित क्षेत्र में -1, 2 और -2 में से कम से कम एक वर्ग है क्योंकि दो गैर-वर्गों का गुणनफल एक वर्ग है और इसलिए हमारे पास है:
-# अगर <math>-1=a^2,</math> तब <math>P=(x^2+a)(x^2-a).</math>
+# यदि <math>-1=a^2,</math> तब <math>P=(x^2+a)(x^2-a).</math>
-# अगर <math>2=b^2,</math> तब <math>P=(x^2+bx+1)(x^2-bx+1).</math>
+# यदि <math>2=b^2,</math> तब <math>P=(x^2+bx+1)(x^2-bx+1).</math>
-# अगर <math>-2=c^2,</math> तब <math>P=(x^2+cx-1)(x^2-cx-1).</math>
+# यदि <math>-2=c^2,</math> तब <math>P=(x^2+cx-1)(x^2-cx-1).</math>
+=== समिश्रता ===
+बहुपद गुणनखंड एल्गोरिदम आधारिक बहुपद संचालन जैसे उत्पाद, विभाजन, gcd एक बहुपद मॉडुलो की घातयों का उपयोग करते हैं। प्रारम्भिक अंकगणित का उपयोग करके f<sub>q</sub> में O(n<sup>2</sup>) संचालन में अधिकतम n घात के दो बहुपदों का गुणा किया जा सकता है या ''O''(''n''log(''n'') log(log(''n'')) अंकगणित का उपयोग करके F<sub>q</sub> में संचालन का यूक्लिडियन विभाजन (शेष के साथ विभाजन) एक ही समय सीमा के भीतर किया जा सकता है। अधिक से अधिक घात के दो बहुपदों के बीच एक बहुपद महानतम विभाजक की लागत प्रारम्भिक विधियों का उपयोग करके F<sub>q</sub> में O(n<sup>2</sup>) संचालन के रूप में या F<sub>q</sub> का उपयोग करके ''O''(''n''log(''n'') log(log(''n'')) संचालन के रूप में प्राप्त की जा सकती है। बहुपदों h, g की घात के लिए अधिकतम n घातांक h<sup>q</sup> mod g को O(log(q)) बहुपद उत्पादों के साथ किया जा सकता है, वर्ग विधि द्वारा घातांक का उपयोग करके, जो प्रारम्भिक विधियों या O(nlog(q)log(n) log(log(n))) का विभिन्न प्रकार से उपयोग करके F<sub>q</sub> में O(n<sup>2</sup>log(q)) संचालन है। अनुवर्ती एल्गोरिदम में बहुपदों के अंकगणित के लिए प्रारम्भिक एल्गोरिदम का उपयोग करते हुए F<sub>q</sub> में अंकगणितीय संचालन की संख्या के संदर्भ में समिश्रताएं व्यक्त की जाती हैं।
+== गुणनखंड एल्गोरिथ्म ==
-=== जटिलता ===
+परिमित क्षेत्रों पर बहुपदों की गुणनखंड के लिए कई एल्गोरिदम में निम्नलिखित तीन चरण सम्मिलित हैं:
-बहुपद फैक्टरिंग एल्गोरिदम मूल बहुपद संचालन का उपयोग करते हैं जैसे कि उत्पाद, डिवीजन, जीसीडी, एक बहुपद मॉडुलो की शक्तियाँ, आदि। एक गुणन एल्गोरिथ्म # बहुपद के दो बहुपदों का बहुपद गुणन अधिकतम एन बिग ओ नोटेशन में किया जा सकता है। ओ (एन)<sup>2</sup>) एफ में संचालन<sub>''q''</sub> शास्त्रीय अंकगणित का उपयोग करते हुए, या O(nlog(n) log(log(n)) ) संचालन 'F' में<sub>''q''</sub> गुणन एल्गोरिथ्म का उपयोग करना # बड़े इनपुट के लिए तेज़ गुणन एल्गोरिदम | तेज अंकगणित। एक [[यूक्लिडियन विभाजन]] (शेष के साथ विभाजन) एक ही समय सीमा के भीतर किया जा सकता है। डिग्री के दो बहुपदों के बीच एक बहुपद के सबसे बड़े सामान्य विभाजक की लागत को O(n) के रूप में लिया जा सकता है<sup>2</sup>) एफ में संचालन<sub>''q''</sub> शास्त्रीय तरीकों का उपयोग करना, या O(nlog<sup>2</sup>(n) 'F' में लॉग(लॉग(n)) ऑपरेशंस<sub>''q''</sub> तेज़ तरीकों का उपयोग करना। अधिक से अधिक n डिग्री वाले बहुपदों h, g के लिए, घातांक h<sup>q</sup> mod g को O(log(q)) बहुपद गुणनफलों के साथ किया जा सकता है, जिसमें वर्ग विधि द्वारा घातांक का उपयोग किया जाता है, अर्थात O(n)<sup>2</sup>लॉग (क्यू)) संचालन 'एफ' में<sub>''q''</sub> शास्त्रीय तरीकों का उपयोग करना, या 'एफ' में ओ (एनलॉग (क्यू) लॉग (एन) लॉग (लॉग (एन))) संचालन<sub>''q''</sub> तेज़ तरीकों का उपयोग करना।
+# वर्ग मुक्त गुणनखंड
+# विशिष्ट घात गुणनखंडन
-अनुवर्ती एल्गोरिदम में, एफ में अंकगणितीय परिचालनों की संख्या के संदर्भ में जटिलताओं को व्यक्त किया जाता है<sub>''q''</sub>, बहुपदों के अंकगणित के लिए शास्त्रीय एल्गोरिदम का उपयोग करना।
+# समान-घात गुणनखंडन
-== फैक्टरिंग एल्गोरिदम ==
-परिमित क्षेत्रों पर बहुपदों की फैक्टरिंग के लिए कई एल्गोरिदम में निम्नलिखित तीन चरण शामिल हैं:
-# #वर्ग-मुक्त गुणनखंड|वर्ग-मुक्त गुणनखंड
-# #अलग-डिग्री गुणनखंड|अलग-डिग्री गुणनखंड
-# # समान-डिग्री गुणनखंड|समान-डिग्री गुणनखंड
 एक महत्वपूर्ण अपवाद बेर्लेकैंप का एल्गोरिथम है, जो चरण 2 और 3 को जोड़ता है।
 === बेर्लेकैंप का एल्गोरिथम ===
-{{main article|Berlekamp's algorithm}}
+{{main article|बेर्लेकैंप का एल्गोरिदम}}
-बेर्लेकैंप का एल्गोरिथम ऐतिहासिक रूप से महत्वपूर्ण है क्योंकि यह पहला गुणनखंड एल्गोरिथम है, जो व्यवहार में अच्छी तरह से काम करता है। हालाँकि, इसमें जमीनी क्षेत्र के तत्वों पर एक लूप होता है, जिसका तात्पर्य है कि यह केवल छोटे परिमित क्षेत्रों पर ही व्यावहारिक है। एक निश्चित ग्राउंड फील्ड के लिए, इसकी [[समय जटिलता]] बहुपद है, लेकिन, सामान्य ग्राउंड फील्ड के लिए, जटिलता ग्राउंड फील्ड के आकार में घातीय है।
+बेर्लेकैंप का एल्गोरिथम ऐतिहासिक रूप से महत्वपूर्ण है क्योंकि यह पहला गुणनखंड एल्गोरिथम है, जो गणना में अच्छी तरह से कार्य करता है। हालाँकि इसमें जमीनी क्षेत्र के तत्वों पर एक लूप होता है, जिसका तात्पर्य है कि यह केवल छोटे परिमित क्षेत्रों पर ही व्यावहारिक है। एक निश्चित सतह क्षेत्र के लिए इसकी समय समिश्रता बहुपद है, लेकिन सामान्य सतह क्षेत्र के लिए समिश्रता सतह क्षेत्र के आकार में घातीय है।
-=== वर्ग मुक्त गुणनखंड ===
+=== वर्ग-मुक्त गुणनखंड ===
-एल्गोरिथ्म एक वर्ग-मुक्त बहुपद निर्धारित करता है। बहुपदों के लिए वर्ग-मुक्त गुणनखंड जिसके गुणांक परिमित क्षेत्र F से आते हैं<sub>''q''</sub> आदेश की {{nowrap|1=''q'' = ''p''<sup>''m''</sup>}} पी प्राइम के साथ। यह एल्गोरिदम पहले व्युत्पन्न को निर्धारित करता है और फिर बहुपद और उसके व्युत्पन्न के जीसीडी की गणना करता है। यदि यह एक नहीं है तो gcd को फिर से मूल बहुपद में विभाजित किया जाता है, बशर्ते कि व्युत्पन्न शून्य न हो (ऐसा मामला जो परिमित क्षेत्रों पर परिभाषित गैर-निरंतर बहुपदों के लिए मौजूद है)।
+एल्गोरिद्म उन बहुपदों के लिए एक वर्ग-मुक्त गुणनखंडन निर्धारित करता है जिनके गुणांक p, a अभाज्य के साथ क्रम {{nowrap|1=''q'' = ''p''<sup>''m''</sup>}} के परिमित क्षेत्र F<sub>q</sub> से आते हैं। यह एल्गोरिदम पहले व्युत्पन्न को निर्धारित करता है और फिर बहुपद और उसके व्युत्पन्न के gcd की गणना करता है। यदि यह एक नहीं है तो gcd को फिर से मूल बहुपद में विभाजित किया जाता है, परंतु व्युत्पन्न शून्य न हो ऐसी स्थिति मे जो परिमित क्षेत्रों पर परिभाषित गैर-निरंतर बहुपदों के लिए सम्मिलित है।
-यह एल्गोरिदम इस तथ्य का उपयोग करता है कि, यदि बहुपद का व्युत्पन्न शून्य है, तो यह x में बहुपद है<sup>p</sup>, जो कि, यदि गुणांक 'F' से संबंधित है<sub>''p''</sub>, x को x से प्रतिस्थापित करने पर प्राप्त बहुपद की pth शक्ति<sup>1/पैसा</sup>. यदि गुणांक 'एफ' से संबंधित नहीं हैं<sub>''p''</sub>, शून्य अवकलज वाले बहुपद का pवाँ मूल x पर उसी प्रतिस्थापन द्वारा प्राप्त किया जाता है, जिसे गुणांकों में [[फ्रोबेनियस एंडोमोर्फिज्म]] के व्युत्क्रम को लागू करके पूरा किया जाता है। {{Citation needed|date=December 2020}}
+यह एल्गोरिथ्म इस तथ्य का उपयोग करता है कि यदि बहुपद का व्युत्पन्न शून्य है तो यह x<sup>p</sup> में एक बहुपद है, जो कि यदि गुणांक F<sub>p</sub> से संबंधित है, तो x द्वारा x<sup>1/p</sup> को प्रतिस्थापित करके प्राप्त बहुपद की p<sup>th</sup> घात गुणांक F<sub>p</sub> से संबंधित नहीं हैं, तो शून्य अवकलज वाले बहुपद का p<sup>th</sup> मूल x पर उसी प्रतिस्थापन द्वारा प्राप्त किया जाता है, जिसे गुणांकों के लिए [[फ्रोबेनियस एंडोमोर्फिज्म|फ्रोबेनियस स्वसमाकृतिकता]] के व्युत्क्रम को प्रयुक्त करके पूरा किया जाता है।{{Citation needed|date=December 2020}}
-यह एल्गोरिथ्म [[विशेषता (बीजगणित)]] शून्य के एक क्षेत्र पर भी काम करता है, केवल अंतर के साथ कि यह कभी भी निर्देशों के ब्लॉक में प्रवेश नहीं करता है जहां पीटीएच जड़ों की गणना की जाती है। हालांकि, इस मामले में, वर्ग-मुक्त बहुपद#यून का एल्गोरिदम|यून का एल्गोरिदम अधिक कुशल है क्योंकि यह कम डिग्री के बहुपदों के सबसे बड़े सामान्य भाजक की गणना करता है। एक परिणाम यह है कि, पूर्णांकों पर एक बहुपद का गुणनखंड करते समय, निम्न एल्गोरिथम का उपयोग नहीं किया जाता है: पहले पूर्णांकों पर वर्ग-मुक्त गुणनखंडन की गणना करता है, और परिणामी बहुपदों का गुणनखंड करने के लिए, एक पी चुनता है जैसे कि वे वर्ग-मुक्त रहते हैं मोडुलो पी।
+यह एल्गोरिदम विशेष शून्य के क्षेत्र में भी कार्य करता है, केवल अंतर के साथ यह कभी भी निर्देशों के ब्लॉक में प्रवेश नहीं करता है जहां p<sup>th</sup> घातों की गणना की जाती है। हालांकि, इस स्थिति में u का एल्गोरिदम अधिक कुशल है क्योंकि यह कम घात के बहुपदों के सबसे बड़े सामान्य विभाजक की गणना करता है। एक परिणाम यह है कि जब पूर्णांकों पर एक बहुपद का गुणनखंड किया जाता है तो निम्न एल्गोरिथम का उपयोग नहीं किया जाता है जो पहले पूर्णांकों पर वर्ग-मुक्त गुणनखंडन की गणना करता है और परिणामी बहुपदों का गुणनखंड करने के लिए p को चुनता है जैसे कि वे वर्ग-मुक्त मॉड्यूलो p उपस्थित रहते हैं।
-  'एल्गोरिदम': 'एसएफएफ' (स्क्वायर-फ्री फैक्टराइजेशन)
+  '''Algorithm''': '''SFF''' (Square-Free Factorization)
-      'इनपुट': 'एफ' में एक मोनिक बहुपद एफ<sub>''q''</sub>[एक्स] जहां क्यू = पी<sup>मी</sup>
+      '''Input''': A monic polynomial ''f'' in '''F'''<sub>''q''</sub>[''x''] where ''q'' = ''p<sup>m</sup>''
-      'आउटपुट': f का वर्ग-मुक्त गुणनखंडन
+      '''Output''': Square-free factorization of ''f''
-      आर ← 1
+      ''R'' ← 1
-      # डब्ल्यू को एफ के सभी कारकों का उत्पाद (बहुलता के बिना) बनाएं
+      # Make ''w'' be the product (without multiplicity) of all factors of ''f'' that have
-      # बहुलता p से विभाज्य नहीं है
+      # multiplicity not divisible by ''p''
-      सी ← 'जीसीडी' (एफ, एफ')
+      ''c'' ← gcd(''f'', ''f''′)
-      डब्ल्यू ← एफ/सी
+      ''w'' ← ''f''/''c''
-      # चरण 1: डब्ल्यू में सभी कारकों की पहचान करें
+      # Step 1: Identify all factors in ''w''
-      मैं ← 1
+      ''i'' ← 1
-      'जबकि' डब्ल्यू ≠ 1 'करो'
+      '''while''' ''w'' ≠ 1 '''do'''
-          वाई ← 'जीसीडी' (डब्ल्यू, सी)
+          ''y'' ← gcd(''w'', ''c'')
-          एफएसी ← डब्ल्यू / वाई
+          ''fac'' ← ''w'' / ''y''
-          आर ← आर · तथ्य<sup>मैं
+          ''R'' ← ''R'' · ''fac<sup>i</sup>''
-          डब्ल्यू ← वाई; सी ← सी / वाई; मैं ← मैं + 1
+          ''w'' ← ''y''; ''c'' ← ''c'' / ''y''; ''i'' ← ''i'' + 1
-      'अंत जबकि'
+      '''end while'''
-      # c अब f के शेष कारकों का गुणनफल (बहुलता के साथ) है
+      # ''c'' is now the product (with multiplicity) of the remaining factors of ''f''
-      # चरण 2: पुनरावर्तन का उपयोग करके शेष सभी कारकों की पहचान करें
+      # Step 2: Identify all remaining factors using recursion
-      # ध्यान दें कि ये f के कारक हैं जिनकी बहुलता p से विभाज्य है
+      # Note that these are the factors of ''f'' that have multiplicity divisible by ''p''
-      'अगर' सी ≠ 1 'तो'
+      '''if''' ''c'' ≠ 1 '''then'''
-          सी ← सी<sup>1/पैसा</sup>
+          ''c'' ← ''c''<sup>1/''p''</sup>
-          आर ← आर·'एसएफएफ'(सी)<sup>पी</सुप>
+          ''R'' ← ''R''·'''SFF'''(''c'')<sup>''p''</sup>
-      'अगर अंत'
+      '''end if'''
-      'आउटपुट' (आर)
+      '''Output'''(''R'')
+विचार यह है कि समान बहुलता वाले f के सभी अलघुकरणीय कारकों के गुणनफल की पहचान की जाए। यह दो चरणों में किया जाता है। पहला चरण f के औपचारिक व्युत्पन्न का उपयोग करता है ताकि बहुलता वाले सभी कारकों को p से विभाजित न किया जा सके। दूसरा चरण शेष कारकों की पहचान करता है। जैसा कि शेष सभी कारकों में p से विभाज्य बहुलता है जिसका अर्थ है कि वे p की घात हैं कोई भी केवल p<sup>th</sup> वर्गमूल ले सकता है और पुनरावर्तन प्रयुक्त कर सकता है।
-विचार यह है कि समान बहुलता वाले f के सभी अलघुकरणीय कारकों के गुणनफल की पहचान की जाए। यह दो चरणों में किया जाता है। पहला कदम एफ के औपचारिक व्युत्पन्न का उपयोग करता है ताकि बहुलता वाले सभी कारकों को पी से विभाजित न किया जा सके। दूसरा चरण शेष कारकों की पहचान करता है। जैसा कि शेष सभी कारकों में p से विभाज्य बहुलता है, जिसका अर्थ है कि वे p की शक्तियाँ हैं, कोई भी केवल pth वर्गमूल ले सकता है और पुनरावर्तन लागू कर सकता है।
 ==== वर्ग मुक्त गुणनखंड का उदाहरण ====
-होने देना
+माना कि
 : <math> f = x^{11} + 2 x^9 + 2x^8 + x^6 + x^5 + 2x^3 + 2x^2 +1 \in \mathbf{F}_3[x],</math>
-तीन तत्वों के साथ क्षेत्र में फ़ैक्टर होना।
+तीन तत्वों के साथ क्षेत्र में गुणनखंड एल्गोरिदम पहले गणना करता है:
-एल्गोरिदम पहले गणना करता है
 : <math> c = \gcd(f, f') = x^9 + 2x^6 + x^3 + 2.</math>
-चूंकि व्युत्पन्न गैर शून्य है हमारे पास है {{math|1=''w'' = ''f''/''c'' = ''x''<sup>2</sup> + 2}} और हम while पाश में प्रवेश करते हैं। एक लूप के बाद हमारे पास है {{math|1=''y'' = ''x'' + 2}}, {{math|1=''z'' = ''x'' + 1}} और {{math|1=''R'' = ''x'' + 1}} अपडेट के साथ {{math|1=''i'' = 2}}, {{math|1=''w'' = ''x'' + 2}} और {{math|1=''c'' = ''x''<sup>8</sup> + ''x''<sup>7</sup> + ''x''<sup>6</sup> + ''x''<sup>2</sup>+''x''+1}}. दूसरी बार पाश के माध्यम से देता है {{math|1=''y'' = ''x'' + 2}}, {{math|1=''z'' = 1}}, {{math|1=''R'' = ''x'' + 1}}, अपडेट के साथ {{math|1=''i'' = 3}}, {{math|1=''w'' = ''x'' + 2}} और {{math|1=''c'' = ''x''<sup>7</sup> + 2''x''<sup>6</sup> + ''x'' + 2}}. लूप के माध्यम से तीसरी बार भी नहीं बदलता है {{math|1=''R''}}. चौथी बार हमें लूप के माध्यम से मिलता है {{math|1= ''y'' = 1}}, {{math|1=''z'' = ''x'' + 2}}, {{math|1=''R'' = (''x'' + 1)(''x'' + 2)<sup>4</sup>}}, अपडेट के साथ {{math|1=''i'' = 5}}, {{math|1=''w'' = 1}} और {{math|1=''c'' = ''x''<sup>6</sup> + 1}}. चूँकि w = 1, हम while लूप से बाहर निकल जाते हैं। तब से {{math|''c'' ≠ 1}}, यह एक पूर्ण घन होना चाहिए। का घनमूल {{math|''c''}}, प्रतिस्थापित करके प्राप्त किया गया {{math|''x''<sup>3</sup>}} द्वारा {{math|''x''}} है {{math|''x''<sup>2</sup> + 1}}, और वर्ग-मुक्त प्रक्रिया को पुनरावर्ती रूप से कॉल करना यह निर्धारित करता है कि यह वर्ग-मुक्त है। इसलिए, इसे घन करना और इसे के मूल्य के साथ जोड़ना {{math|''R''}} उस बिंदु पर वर्ग-मुक्त अपघटन देता है
+चूंकि व्युत्पन्न गैर-शून्य है, हमारे पास {{math|1=''w'' = ''f''/''c'' = ''x''<sup>2</sup> + 2}} है और हम व्हील लूप में प्रवेश करते हैं। व्हील लूप के बाद हमारे पास {{math|1=''y'' = ''x'' + 2}}, {{math|1=''z'' = ''x'' + 1}} और {{math|1=''R'' = ''x'' + 1}} के साथ {{math|1=''i'' = 2}}, {{math|1=''w'' = ''x'' + 2}} और {{math|1=''c'' = ''x''<sup>8</sup> + ''x''<sup>7</sup> + ''x''<sup>6</sup> + ''x''<sup>2</sup>+''x''+1}} है। व्हील लूप के माध्यम से दूसरी बार {{math|1=''y'' = ''x'' + 2}}, {{math|1=''z'' = 1}}, {{math|1=''R'' = ''x'' + 1}} के साथ {{math|1=''i'' = 3}}, {{math|1=''w'' = ''x'' + 2}} और {{math|1=''c'' = ''x''<sup>7</sup> + 2''x''<sup>6</sup> + ''x'' + 2}} के माध्यम से देता है। तीसरी बार के माध्यम से व्हील लूप भी R नहीं परिवर्तित होता है। चौथी बार व्हील लूप के माध्यम से हमें {{math|1= ''y'' = 1}}, {{math|1=''z'' = ''x'' + 2}}, {{math|1=''R'' = (''x'' + 1)(''x'' + 2)<sup>4</sup>}} के साथ {{math|1=''i'' = 5}}, {{math|1=''w'' = 1}} और {{math|1=''c'' = ''x''<sup>6</sup> + 1}} प्राप्त होता है चूंकि w = 1, हम व्हील लूप से बाहर निकलते हैं। चूँकि {{math|''c'' ≠ 1}}, यह एक पूर्ण घन होना चाहिए और {{math|''x''<sup>3</sup>}} को {{math|''x''}} से प्रतिस्थापित करके प्राप्त {{math|''c''}} का घनमूल {{math|''x''<sup>2</sup> + 1}} है और वर्ग-मुक्त प्रक्रिया को पुनरावर्ती रूप से कॉल करके यह निर्धारित करता है कि यह वर्ग-मुक्त है। इसलिए इसे {{math|''R''}} के मान के साथ उस बिंदु पर संयोजित करना वर्ग-मुक्त अपघटन देता है:
 : <math> f= (x+1)(x^2+1)^3(x+2)^4.</math>
+=== विशिष्ट घात गुणनखंडन ===
+यह एल्गोरिथम एक वर्ग-मुक्त बहुपद को बहुपदों के एक उत्पाद में विभाजित करता है जिनके अलघुकरणीय कारकों में समान घात होती है। मान लीजिए {{math|''f'' ∈ '''F'''<sub>''q''</sub>[''x'']}} घात {{math|''n''}} का गुणनखंड किया जाने वाला बहुपद है।
-=== अलग डिग्री गुणनखंड ===
+  '''Algorithm''' Distinct-degree factorization(DDF)
-यह एल्गोरिथम एक वर्ग-मुक्त बहुपद को बहुपदों के एक उत्पाद में विभाजित करता है, जिनके अलघुकरणीय कारकों में समान डिग्री होती है। होने देना {{math|''f'' ∈ '''F'''<sub>''q''</sub>[''x'']}} डिग्री {{math|''n''}} गुणनखंड किया जाने वाला बहुपद हो।
+      '''Input''': A monic square-free polynomial ''f'' ∈ '''F'''<sub>''q''</sub>[''x'']
+      '''Output''': The set of all pairs (''g'', ''d''), such that
-  एल्गोरिथम डिस्टिक्ट-डिग्री फ़ैक्टराइज़ेशन (DDF)
+              ''f'' has an irreducible factor of degree ''d'' and
-      इनपुट: एक मोनिक वर्ग-मुक्त बहुपद  {{math|''f'' ∈ '''F'''<sub>''q''</sub>[''x'']}}
+              ''g'' is the product of all monic irreducible factors of ''f'' of degree ''d''.
-      आउटपुट: सभी जोड़ियों का सेट {{math|(''g'', ''d'')}}, ऐसा है कि
+      '''Begin'''
- {{math|''f''}} डिग्री का एक अप्रासंगिक कारक है {{math|''d''}} और
-{{math|''g''}} के सभी मोनिक इरेड्यूसिबल कारकों का उत्पाद है {{math|''f''}} डिग्री {{math|''d''}}.
+         '''while'''  '''do'''
-      शुरू
-<math>i:=1;\qquad S:=\emptyset,\qquad f^*:=f;</math>
+             '''if''' ''g'' ≠ 1, '''then'''
-जबकि <math>\deg f^*\ge 2i</math> करना
+                 ;
- <math>g=\gcd(f^*, x^{q^i}-x)</math>
-अगर {{math|''g'' ≠ 1}}, तब
+             '''end if'''
- <math>S:=S\cup\{(g,i)\}</math>;
+             ''i'' := ''i'' + 1;
-<math>f^*:=f^*/g</math>
+          '''end while''';
-अगर अंत
+          '''if''' , '''then''';
-{{math|1=''i'' := ''i'' + 1;}}
+          '''if''' , '''then return''' {(''f'', 1)},
-          समाप्त जबकि;
+              '''else return''' ''S''
-          अगर <math>f^*\ne 1</math>, तब <math>S:= S\cup\{(f^*,\deg f^*)\}</math>;
+      '''End'''
-          अगर <math>S=\emptyset</math>, फिर लौटें {{math|{{mset|(''f'', 1)}}}},
-              वरना लौट जाओ {{math|''S''}}
-      अंत
 एल्गोरिथ्म की शुद्धता निम्नलिखित पर आधारित है:
-<ब्लॉककोट>लेम्मा. ''i'' के लिए ≥ 1 बहुपद
+लेम्मा i ≥ 1 के लिए बहुपद है:
 : <math>x^{q^i}-x \in \mathbf{F}_q[x]</math>
-एफ में सभी मोनिक इरेड्यूसबल बहुपदों का उत्पाद है<sub>''q''</sub>[x] जिसकी डिग्री i को विभाजित करती है।</blockquote>
+F<sub>q</sub> [x] में सभी मोनिक अलघुकरणीय बहुपदों का गुणनफल है जो घात i को विभाजित करते है।
-पहली नज़र में, यह कुशल नहीं है क्योंकि इसमें उस डिग्री के बहुपदों के जीसीडी की गणना करना शामिल है जो इनपुट बहुपद की डिग्री में घातीय है। हालाँकि,
+पहले चरण में यह कुशल नहीं है क्योंकि इसमें उस घात के बहुपदों के gcd की गणना करना सम्मिलित है जो इनपुट बहुपद की घात में घातीय है।
+हालाँकि,
 : <math>g=\gcd \left (f^*, x^{q^i}-x \right )</math>
-द्वारा प्रतिस्थापित किया जा सकता है
+द्वारा प्रतिस्थापित किया जा सकता है:
 : <math>g=\gcd \left (f^*, \left (x^{q^i}-x \mod f^* \right ) \right ).</math>
 इसलिए, हमें गणना करनी होगी:
 : <math>x^{q^i}-x \mod f^*,</math>
-दो तरीके हैं:
+जिसके दो तरीके हैं:
-<blockquote>विधि I. के मान से प्रारंभ करें
+'''विधि 1.''' के मान से प्रारंभ करें।
 : <math>x^{q^{i-1}}\mod f^* </math>
-वर्ग विधि द्वारा घातांक का उपयोग करते हुए, पिछले चरण में गणना की गई और इसकी qth शक्ति मॉड्यूलो नई f * की गणना करने के लिए। इसकी जरूरत है
+वर्ग विधि द्वारा घातांक का उपयोग करते हुए, पिछले चरण में गणना की गई है और इसकी qth घात मॉड्यूलो मे f * की गणना करने के लिए इसकी आवश्यकता है:
 :<math>O \left (\log(q) \deg(f)^2 \right )</math>
-एफ में अंकगणितीय संचालन<sub>''q''</sub> प्रत्येक चरण पर, और इस प्रकार
+प्रत्येक चरण में F<sub>q</sub> में अंकगणितीय संचालन इस प्रकार है:
 :<math>O \left (\log(q) \deg(f)^3 \right )</math>
-संपूर्ण एल्गोरिथम के लिए अंकगणितीय संक्रियाएं।</blockquote>
+संपूर्ण एल्गोरिथम के लिए अंकगणितीय संक्रियाएं है।
-<ब्लॉककोट>विधि II. इस तथ्य का उपयोग करते हुए कि ''q''वीं शक्ति F पर एक रेखीय मानचित्र है<sub>''q''</sub> हम इसके मैट्रिक्स की गणना कर सकते हैं
+'''विधि 2.''' इस तथ्य का उपयोग करते हुए कि qth घात F<sub>q</sub> पर एक रैखिक मानचित्र है हम इसके आव्यूह की गणना कर सकते हैं:
 : <math>O \left (\deg(f)^2(\log(q)+\deg(f)) \right )</math>
-संचालन। फिर लूप के प्रत्येक पुनरावृत्ति पर, वेक्टर द्वारा मैट्रिक्स के उत्पाद की गणना करें (O(deg(f) के साथ)<sup>2</sup>) संचालन)। यह F में कुल संक्रियाओं को प्रेरित करता है<sub>''q''</sub> जो है
+लूप के प्रत्येक पुनरावृत्ति पर एक सदिश द्वारा आव्यूह (O(deg(f)<sup>2</sup>) संचालन के साथ) के उत्पाद की गणना करें। यह F<sub>q</sub> में कुल संचालन को प्रेरित करता है:
 : <math>O \left (\deg(f)^2 (\log(q)+\deg(f)) \right ).</math>
-इस प्रकार यह दूसरी विधि अधिक कुशल है और आमतौर पर पसंद की जाती है। इसके अलावा, इस पद्धति में जिस मैट्रिक्स की गणना की जाती है, उसका उपयोग अधिकांश एल्गोरिदम द्वारा समान-डिग्री गुणनखंड के लिए किया जाता है (नीचे देखें); इस प्रकार इसे विशिष्ट-डिग्री गुणनखंडन के लिए उपयोग करने से आगे कंप्यूटिंग समय की बचत होती है।</blockquote>
+इस प्रकार यह दूसरी विधि अधिक कुशल है और सामान्यतः पसंद की जाती है। इसके अतिरिक्त इस पद्धति में जिस आव्यूह की गणना की जाती है उसका उपयोग अधिकांश एल्गोरिदम द्वारा समान-घात गुणनखंड के लिए किया जाता है। इस प्रकार इसे विशिष्ट-घात गुणनखंडन के लिए उपयोग करने से आगे कंप्यूटिंग समय की बचत होती है।
-=== समान-डिग्री गुणनखंड ===
+=== समान-घात गुणनखंड ===
 ==== कैंटर-ज़सेनहॉस एल्गोरिथम ====
-{{main article|Cantor–Zassenhaus algorithm}}
+{{main article|कैंटर-ज़सेनहॉस एल्गोरिथम
-इस खंड में, हम एक परिमित क्षेत्र 'F' पर डिग्री n वाले एक मोनिक स्क्वायरफ्री यूनिवेरिएट बहुपद f के गुणनखंडन पर विचार करते हैं।<sub>''q''</sub>, जो है {{math|''r'' ≥ 2}} जोड़ीदार अलग-अलग अलघुकरणीय कारक <math> f_1,\ldots,f_r</math> प्रत्येक डिग्री डी।
+}}
-हम पहले कैंटर और ज़ैसेनहॉस (1981) द्वारा एक एल्गोरिथ्म का वर्णन करते हैं और फिर एक वेरिएंट जिसमें थोड़ी बेहतर जटिलता है। दोनों संभाव्य एल्गोरिदम हैं जिनके चलने का समय यादृच्छिक विकल्पों ([[लास वेगास एल्गोरिथम]]) पर निर्भर करता है, और एक अच्छा औसत चलने का समय है। अगले भाग में हम शौप (1990) द्वारा एक एल्गोरिथम का वर्णन करते हैं, जो एक समान-डिग्री गुणनखंड एल्गोरिथम भी है, लेकिन नियतात्मक है। इन सभी एल्गोरिदम को गुणांक के क्षेत्र के लिए विषम क्रम q की आवश्यकता होती है। अधिक गुणनखंडन एल्गोरिदम के लिए उदाहरण देखें नुथ की पुस्तक [[कंप्यूटर प्रोग्रामिंग की कला]] वॉल्यूम 2।
+इस गुणनखंड में हम एक परिमित क्षेत्र F<sub>q</sub> पर घात n के एक मोनिक वर्ग मुक्त चर बहुपद f के गुणन पर विचार करते हैं, जिसमें {{math|''r'' ≥ 2}} जोड़ीदार अलग-अलग अलघुकरणीय कारक <math> f_1,\ldots,f_r</math> की प्रत्येक घात d हैं।
-  'एल्गोरिदम' कैंटर-ज़सेनहॉस एल्गोरिथम।
+हम पहले कैंटर और ज़ैसेनहॉस (1981) द्वारा एक एल्गोरिथ्म का वर्णन करते हैं और फिर एक बहुपद जिसमें अपेक्षाकृत समिश्रता है। दोनों संभाव्य एल्गोरिदम हैं जिनके चलने का समय यादृच्छिक विकल्पों (लास वेगास एल्गोरिदम) पर निर्भर करता है, और एक अच्छा औसत चलने का समय है। अगले भाग में हम शौप (1990) द्वारा एक एल्गोरिथम का वर्णन करते हैं, जो एक समान-घात गुणनखंड एल्गोरिथम भी है, लेकिन नियतात्मक है। इन सभी एल्गोरिदम को गुणांक के क्षेत्र के लिए विषम क्रम q की आवश्यकता होती है। अधिक गुणनखंडन एल्गोरिदम के लिए नुथ की पुस्तक "कंप्यूटर प्रोग्रामिंग की कला" को देखें।
-      'इनपुट:' एक परिमित क्षेत्र 'एफ'<sub>''q''</sub> विषम क्रम का क्यू।
+  '''Algorithm''' Cantor–Zassenhaus algorithm.
-             'एफ' में एक मोनिक वर्ग मुक्त बहुपद एफ<sub>''q''</sub>[x] डिग्री n = rd,
+      '''Input:''' A finite field '''F'''<sub>''q''</sub> of odd order ''q''.
-                  जिसमें डिग्री डी के प्रत्येक आर ≥ 2 अपरिवर्तनीय कारक हैं
+             A monic square free polynomial ''f'' in '''F'''<sub>''q''</sub>[''x''] of degree ''n'' = ''rd'',
-      'आउटपुट:' f के मोनिक इरेड्यूसिबल कारकों का सेट।
+                  which has ''r'' ≥ 2 irreducible factors each of degree ''d''
+      '''Output:''' The set of monic irreducible factors of ''f''.
-      गुणनखंड := {f};
+      Factors := {''f''};
-      'जबकि' आकार (कारक) <आर 'करो',
+      '''while''' Size(Factors) < ''r'' '''do''',
-          'एफ' में एच चुनें<sub>''q''</sub>[x] डिग्री के साथ (ज) < n यादृच्छिक पर;
+          Choose ''h'' in '''F'''<sub>''q''</sub>[''x''] with deg(''h'') < ''n'' at random;
-<math>g:=h^{\frac{q^d-1}{2}}- 1 \pmod f</math>
-प्रत्येक ''u'' के लिए deg(''u'') > ''d'' वाले गुणकों में करें
+         '''for each''' ''u'' '''in''' Factors with deg(''u'') > ''d'' '''do'''
-              अगर gcd(''g'', ''u'') ≠ 1 और gcd(''g'', ''u'') ≠ ''u'', तो
+              '''if''' gcd(''g'', ''u'') ≠ 1 and gcd(''g'', ''u'') ≠ ''u'', '''then'''
-                  कारक:= कारक<math>\,\setminus\, \{u\}\cup\{(\gcd(g,u),u/\gcd(g,u))\}</math>;
+                  Factors:= Factors;
-              अगर अंत
+              '''endif'''
-      हमेशा के लिए
+      '''endwhile'''
-      वापसी कारक
+      '''return''' Factors
+इस एल्गोरिथम की शुद्धता इस तथ्य पर निर्भर करती है कि वलय '''F'''<sub>''q''</sub>[''x'']/''f'' क्षेत्र '''F'''<sub>''q''</sub>[''x'']/''f'' का एक प्रत्यक्ष उत्पाद है जहां f अलघुकरणीय कारक है। चूँकि इन सभी क्षेत्रों में q<sup>d</sup> तत्व हैं इनमें से किसी भी क्षेत्र में g घटक प्रायिकता के साथ शून्य है:
+: <math>\frac{q^d-1}{2q^d} \sim \tfrac{1}{2}.</math>
+इसका तात्पर्य है कि बहुपद gcd (g, u) G के कारकों का उत्पाद है जिसके लिए g का घटक शून्य है।
-इस एल्गोरिथ्म की शुद्धता इस तथ्य पर निर्भर करती है कि रिंग F<sub>''q''</sub>[x]/f फ़ील्ड 'F' का प्रत्यक्ष उत्पाद है<sub>''q''</sub>[एक्स] / च<sub>i</sub>जहां च<sub>i</sub>f के अलघुकरणीय कारकों पर चलता है। चूंकि इन सभी क्षेत्रों में क्यू है<sup>d</sup> तत्व, इनमें से किसी भी क्षेत्र में g का घटक प्रायिकता के साथ शून्य है
+यह दिखाया गया है कि एल्गोरिदम व्हील लूप के पुनरावृत्तियों की औसत संख्या <math>2.5 \log_2 r</math> से कम है, जो F<sub>q</sub> में अंकगणितीय संक्रिया की औसत संख्या देता है जो <math>O(dn^2\log(r)\log(q))</math> है।<ref>{{citation|first1=Philippe|last1=Flajolet|first2=Jean-Marc | last2=Steayaert |title = Automata, languages and programming |location=Aarhus| series = Lecture Notes in Comput. Sci.|volume = 140|pages = 239–251|publisher = Springer|year=1982|doi=10.1007/BFb0012773|isbn=978-3-540-11576-2}}</ref>
-: <math>\frac{q^d-1}{2q^d} \sim \tfrac{1}{2}.</math>
-इसका तात्पर्य है कि बहुपद जीसीडी (जी, यू) जी के कारकों का उत्पाद है जिसके लिए जी का घटक शून्य है।
-यह दिखाया गया है कि एल्गोरिथम के जबकि लूप के पुनरावृत्तियों की औसत संख्या से कम है <math>2.5 \log_2 r</math>, F में अंकगणितीय संक्रियाओं की औसत संख्या दे रहा है<sub>''q''</sub> जो है <math>O(dn^2\log(r)\log(q))</math>.<ref>{{citation|first1=Philippe|last1=Flajolet|first2=Jean-Marc | last2=Steayaert |title = Automata, languages and programming |location=Aarhus| series = Lecture Notes in Comput. Sci.|volume = 140|pages = 239–251|publisher = Springer|year=1982|doi=10.1007/BFb0012773|isbn=978-3-540-11576-2}}</ref>
+विशिष्ट स्थिति में जहां ''d''log(''q'') > ''n'' द्वारा इस समिश्रता को कम किया जा सकता है:
-विशिष्ट मामले में जहां dlog(q) > n, इस जटिलता को कम किया जा सकता है
 : <math>O(n^2(\log(r)\log(q)+n))</math>
 रेखीय मानचित्र के कर्नेल में h चुनकर
 : <math> v \to v^q-v \pmod f</math>
-और निर्देश की जगह
+और निर्देश के स्थान पर
 : <math>g:=h^{\frac{q^d-1}{2}}- 1 \pmod f</math>
 द्वारा
 : <math>g:=h^{\frac{q-1}{2}}- 1 \pmod f.</math>
-वैधता का प्रमाण उपरोक्त जैसा ही है, फ़ील्ड एफ के प्रत्यक्ष उत्पाद को प्रतिस्थापित करना<sub>''q''</sub>[एक्स] / च<sub>i</sub>क्यू तत्वों के साथ उनके उपक्षेत्रों के प्रत्यक्ष उत्पाद द्वारा। जटिलता में विघटित है <math>O(n^2\log(r)\log(q))</math> एल्गोरिदम के लिए ही, <math>O(n^2(\log(q)+n))</math> रेखीय मानचित्र के मैट्रिक्स की गणना के लिए (जो पहले से ही वर्ग-मुक्त गुणनखंड में गणना की जा सकती है) और O(n<sup>3</sup>) इसके कर्नेल की गणना के लिए। यह ध्यान दिया जा सकता है कि यह एल्गोरिथम तब भी काम करता है जब कारकों में समान डिग्री नहीं होती है (इस मामले में कारकों की संख्या आर, जबकि लूप को रोकने के लिए आवश्यक है, कर्नेल के आयाम के रूप में पाया जाता है)। फिर भी, यदि इस एल्गोरिथम का उपयोग करने से पहले वर्ग-मुक्त गुणनखंडन किया जाता है, तो जटिलता थोड़ी बेहतर होती है (चूंकि n वर्ग-मुक्त गुणनखंडन के साथ घट सकता है, इससे महत्वपूर्ण चरणों की जटिलता कम हो जाती है)।
+वैधता का प्रमाण उपरोक्त के समान है।
+क्षेत्र F<sub>q</sub>[x]/fi के प्रत्यक्ष उत्पाद को q तत्वों के साथ उनके उपक्षेत्रों के प्रत्यक्ष उत्पाद द्वारा प्रतिस्थापित किया जाता है। एल्गोरिथ्म के लिए <math>O(n^2\log(r)\log(q))</math> में समिश्रता विघटित होती है, रैखिक के आव्यूह की गणना के लिए <math>O(n^2(\log(q)+n))</math> की पहले से ही वर्ग-मुक्त गुणनखंड में गणना की जा सकती है। और इसके कर्नेल की गणना के लिए O(n<sup>3</sup>) यह ध्यान दिया जा सकता है कि यह एल्गोरिथम तब भी कार्य करता है जब कारकों में समान घात नहीं होती है। इस स्थिति में कारकों की संख्या R लूप को रोकने के लिए आवश्यक है जिसे कर्नेल के आयाम के रूप में प्राप्त जाता है। फिर भी यदि इस एल्गोरिथम का उपयोग करने से पहले वर्ग-मुक्त गुणनखंडन किया जाता है तो समिश्रता अपेक्षाकृत अच्छी होती है चूंकि n वर्ग-मुक्त गुणनखंडन के साथ घट सकता है। इससे महत्वपूर्ण चरणों की समिश्रता अपेक्षाकृत कम हो जाती है।
 ==== [[विक्टर शौप]] का एल्गोरिथम ====
-पिछले खंड के एल्गोरिदम की तरह, विक्टर शौप का एल्गोरिदम एक समान-डिग्री फ़ैक्टराइज़ेशन एल्गोरिदम है।<ref>Victor Shoup, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.9136&rep=rep1&type=pdf On the deterministic complexity of factoring polynomials over finite fields], Information Processing Letters 33:261-267, 1990</ref> उनके विपरीत, यह एक नियतात्मक एल्गोरिथम है। हालांकि, व्यवहार में, पिछले अनुभाग के एल्गोरिदम की तुलना में यह कम कुशल है। शौप के एल्गोरिदम के लिए, इनपुट प्रमुख क्षेत्रों एफ पर बहुपदों तक ही सीमित है<sub>''p''</sub>.
+पूर्ववर्ती गुणनखंड के एल्गोरिदम की तरह विक्टर शौप का एल्गोरिदम एक समान-घात गुणनखंडन एल्गोरिदम है।<ref>Victor Shoup, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.9136&rep=rep1&type=pdf On the deterministic complexity of factoring polynomials over finite fields], Information Processing Letters 33:261-267, 1990</ref> उनके विपरीत यह एक नियतात्मक एल्गोरिथम है। हालांकि गणना में पिछले अनुभाग के एल्गोरिदम की तुलना में यह कम कुशल है। शौप के एल्गोरिद्म के लिए इनपुट अभाज्य क्षेत्रों F<sub>p</sub> पर बहुपदों तक सीमित है।
-शौप के एल्गोरिदम की सबसे खराब स्थिति समय जटिलता का एक कारक है <math>\sqrt{p}.</math> हालांकि चरघातांकी, यह जटिलता पिछले नियतात्मक एल्गोरिथम (बेर्लेकैंप एल्गोरिथम) से काफी बेहतर है, जिसमें {{math|''p''}} कारक के रूप में। हालाँकि, बहुत कम बहुपद हैं जिनके लिए कंप्यूटिंग समय घातीय है, और एल्गोरिथम की औसत समय जटिलता बहुपद है <math>d\log(p),</math> कहाँ {{mvar|''d''}} बहुपद की डिग्री है, और {{math|''p''}} जमीनी क्षेत्र के तत्वों की संख्या है।
+शौप के एल्गोरिथ्म की सबसे वर्स्टेड पद्धति समय समिश्रता में एक कारक <math>\sqrt{p}</math> है हालांकि घातीय यह समिश्रता पिछले नियतात्मक एल्गोरिदम (बेर्लेकैंप के एल्गोरिथ्म) से बहुत अच्छी है, जिसमें एक कारक के रूप में {{math|''p''}} है। हालाँकि अपेक्षाकृत कम बहुपद हैं जिनके लिए कंप्यूटिंग समय घातीय है और एल्गोरिथम की औसत समय समिश्रता <math>d\log(p),</math> में बहुपद है जहाँ {{mvar|''d''}} बहुपद की घात है और {{math|''p''}} तत्वों की सतह क्षेत्र संख्या है।
-चलो जी = जी<sub>1</sub> ... जी<sub>k</sub>वांछित गुणनखंड हो, जहाँ g<sub>i</sub>डिग्री डी के विशिष्ट मोनिक इरेड्यूसबल बहुपद हैं। चलो एन = डिग्री (जी) = केडी। हम वलय (गणित) पर विचार करते हैं R = 'F'<sub>''q''</sub>[x]/g और x द्वारा R में x की छवि को भी निरूपित करें। रिंग R फ़ील्ड R का प्रत्यक्ष उत्पाद है<sub>i</sub>= 'एफ'<sub>''q''</sub>[एक्स] / जी<sub>i</sub>, और हम पी द्वारा निरूपित करते हैं<sub>i</sub>R से R पर प्राकृतिक [[समरूपता]]<sub>i</sub>. द [[गाल्वा समूह]] ऑफ़ आर<sub>i</sub>'एफ' से अधिक<sub>''q''</sub> क्रम d का चक्रीय है, जो [[फील्ड ऑटोमोर्फिज्म]] u → u द्वारा उत्पन्न होता है<sup>पी</सुप>. यह इस प्रकार है कि जी की जड़ें<sub>i</sub>आर में<sub>i</sub>हैं
+मान लीजिए कि g = g1 ... gk वांछित गुणनखंड है, जहां g<sup>i</sup> घात d के विशिष्ट मोनिक अलघुकरणीय बहुपद हैं। माना कि ''n'' = deg(''g'') = ''kd'' वलय R = '''F'''<sub>''q''</sub>[''x'']/''g'' पर विचार करते हैं और R में x की छवि को x द्वारा भी निरूपित करते हैं। वलय R क्षेत्र ''R<sub>i</sub>'' = '''F'''<sub>''q''</sub>[''x'']/''g<sub>i</sub>'', का प्रत्यक्ष उत्पाद है और हम प्राकृतिक ''p<sub>i</sub>'' द्वारा निरूपित करते हैं R से R<sub>i</sub> पर समाकारिता F<sub>q</sub> पर R<sub>i</sub> का गाल्वा क्षेत्र समूह क्रम d का चक्रीय है जो क्षेत्र स्वसमाकृतिकता ''u'' → ''u<sup>p</sup>'' द्वारा उत्पन्न होता है। इससे पता चलता है कि R<sub>i</sub> में g<sub>i</sub> के मूल हैं:
 : <math> p_i(x), p_i(x^q), p_i \left (x^{q^2} \right ), \ldots,  p_i \left (x^{q^{d-1}} \right ).</math>
-पिछले एल्गोरिथम की तरह, यह एल्गोरिथम R के समान [[subalgebra]] B का उपयोग बर्लेकैंप के एल्गोरिथम के रूप में करता है, जिसे कभी-कभी बर्लेकैंप सबएजब्रा कहा जाता है और इसे परिभाषित किया जाता है
+पिछले एल्गोरिथम की तरह, यह एल्गोरिथम R के समान सबलजेब्रा B का उपयोग बर्लेकैंप के एल्गोरिथम के रूप में करता है, जिसे कभी-कभी "बेर्लेकैंप सबएजब्रा" कहा जाता है और इसे परिभाषित किया जाता है:
 : <math>\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{align}</math>
-B का एक उपसमुच्चय S को पृथक्कारी समुच्चय कहा जाता है, यदि प्रत्येक 1 ≤ i < j ≤ k के लिए s ∈ S ऐसा मौजूद हो कि <math>p_i(s) \ne p_j(s)</math>. पूर्ववर्ती एल्गोरिथम में, S के तत्वों को यादृच्छिक रूप से चुनकर एक अलग सेट का निर्माण किया जाता है। शौप के एल्गोरिथ्म में, अलग करने वाले सेट का निर्माण निम्नलिखित तरीके से किया जाता है। मान लीजिए R[Y] में s ऐसा है कि
+B के एक उपसमुच्चय S को पृथक्कारी समुच्चय कहा जाता है, यदि प्रत्येक 1 ≤ i < j ≤ k के लिए s ∈ S ऐसा सम्मिलित हो कि <math>p_i(s) \ne p_j(s)</math> पूर्ववर्ती एल्गोरिथम में S के तत्वों को यादृच्छिक रूप से चुनकर एक अलग समुच्चय का निर्माण किया जाता है। शौप के एल्गोरिथ्म में, अलग करने वाले समुच्चय का निर्माण निम्नलिखित प्रकार से किया जाता है। मान लीजिए R[Y] में s ऐसा है कि
 :<math>\begin{align}
@@ Line 211: / Line 207: @@
 &=s_0+\cdots+s_{d-1}Y^{d-1}+Y^d
 \end{align}</math>
-तब <math>\{s_0,\dots ,s_{d-1}\}</math> एक अलग सेट है क्योंकि <math>p_i(s)=g_i</math> i =1, ..., k के लिए (दो एकात्मक बहुपदों के मूल समान हैं)। जी के रूप में<sub>i</sub>अलग-अलग इंडेक्स (i, j) की प्रत्येक जोड़ी के लिए जोड़ीदार अलग-अलग हैं, कम से कम गुणांक एस में से एक<sub>h</sub>संतुष्ट करेगा <math>p_i(s_h)\ne p_j(s_h).</math>
+फिर <math>\{s_0,\dots ,s_{d-1}\}</math> एक विशिष्ट समुच्चय है क्योंकि <math>p_i(s)=g_i</math> i =1, ..., k के लिए दो मोनिक बहुपदों की घातें समान हैं जैसा कि g<sub>i</sub> अलग-अलग सारणी (i, j) की प्रत्येक जोड़ी के लिए अलग-अलग हैं जो कम से कम एक गुणांक <math>p_i(s_h)\ne p_j(s_h)</math> को संतुष्ट करता है।
-एक अलग सेट होने के बाद, शौप का एल्गोरिथ्म पूर्ववर्ती खंड के अंतिम एल्गोरिथ्म के रूप में आगे बढ़ता है, बस निर्देश को बदलकर रैखिक मानचित्र के कर्नेल में यादृच्छिक एच पर चुनें <math> v \to v^q-v \pmod f</math>h + i चुनें जिसमें h in S और i in {1, ..., k−1} हो।
-== समय जटिलता ==
+एक विशिष्ट समुच्चय होने के बाद शौप का एल्गोरिथ्म पूर्ववर्ती गुणनखंड के अंतिम एल्गोरिथ्म के रूप में आगे बढ़ता है जो निर्देश को परिवर्तित करके रैखिक मानचित्र के कर्नेल में यादृच्छिक h पर<math> v \to v^q-v \pmod f</math>h + i चयनित करता है जिसमें h मे S और i मे {1, ..., k−1} होते है।
-जैसा कि पिछले अनुभागों में वर्णित है, परिमित क्षेत्रों पर गुणनखंडन के लिए, बहुपद समय जटिलता के [[यादृच्छिक एल्गोरिदम]] हैं (उदाहरण के लिए कैंटर-ज़ासेनहॉस एल्गोरिथम)। बहुपद औसत जटिलता के साथ नियतात्मक एल्गोरिदम भी हैं (उदाहरण के लिए शौप का एल्गोरिथ्म)।
-एक बहुपद सबसे खराब स्थिति वाली जटिलता के साथ एक नियतात्मक एल्गोरिथ्म का अस्तित्व अभी भी एक खुली समस्या है।
+== समय सम्मिश्रता ==
+जैसा कि पिछले अनुभागों में वर्णित है कि परिमित क्षेत्रों पर गुणनखंडन के लिए बहुपद समय सम्मिश्रता के यादृच्छिक एल्गोरिदम हैं उदाहरण के लिए कैंटर-ज़ासेनहॉस एल्गोरिथम बहुपद औसत समिश्रता के साथ नियतात्मक एल्गोरिदम अर्थात शौप का एल्गोरिथ्म भी हैं।
-== राबिन की इरेड्यूसिबिलिटी का परीक्षण ==
+एक बहुपद सबसे जटिल स्थिति वाली सम्मिश्रता के साथ नियतात्मक एल्गोरिथ्म का अस्तित्व अभी भी एक विवृत समस्या है।
-विशिष्ट-डिग्री गुणनखंड एल्गोरिथम की तरह, राबिन का एल्गोरिथम<ref>{{cite journal |last1=Rabin |first1=Michael |year=1980 |title=परिमित क्षेत्रों में संभाव्य एल्गोरिदम|journal=SIAM Journal on Computing |volume=9 |issue=2 |pages=273–280 |doi=10.1137/0209024 |citeseerx=10.1.1.17.5653 }}</ref> ऊपर वर्णित लेम्मा पर आधारित है। डिस्टिक्ट-डिग्री फ़ैक्टराइज़ेशन एल्गोरिथम प्रत्येक d का परीक्षण करता है जो इनपुट बहुपद के आधे से अधिक डिग्री नहीं है। राबिन का एल्गोरिदम लाभ उठाता है कि कम डी पर विचार करने के लिए कारकों की आवश्यकता नहीं होती है। अन्यथा, यह विशिष्ट-डिग्री गुणनखंड एल्गोरिथम के समान है। यह निम्नलिखित तथ्य पर आधारित है।
-चलो पी<sub>1</sub>, ..., पी<sub>k</sub>, n के सभी प्रधान विभाजक हों, और निरूपित करें <math>n/p_i=n_i</math>, 'F' में 1 ≤ i ≤ k बहुपद f के लिए<sub>''q''</sub>[x] की डिग्री n 'F' में अलघुकरणीय है<sub>''q''</sub>[एक्स] अगर और केवल अगर <math> \gcd \left (f,x^{q^{n_i}}-x \right )=1</math>, 1 ≤ i ≤ k, और f के लिए विभाजित करता है <math>x^{q^n}-x</math>. वास्तव में, यदि f के पास n को विभाजित न करने वाला अंश है, तो f विभाजित नहीं होता है <math>x^{q^n}-x</math>; यदि f में n को विभाजित करने वाला गुणनखंड है, तो यह गुणक कम से कम एक को विभाजित करता है <math>x^{q^{n_i}}-x.</math>
+== राबिन की अपरिवर्तनीयता का परीक्षण ==
-एल्गोरिथम राबिन इरेड्यूसबिलिटी टेस्ट
+विशिष्ट-घात गुणनखंड एल्गोरिथम की तरह राबिन का एल्गोरिथम ऊपर बताए गए लेम्मा पर आधारित है।<ref>{{cite journal |last1=Rabin |first1=Michael |year=1980 |title=परिमित क्षेत्रों में संभाव्य एल्गोरिदम|journal=SIAM Journal on Computing |volume=9 |issue=2 |pages=273–280 |doi=10.1137/0209024 |citeseerx=10.1.1.17.5653 }}</ref> विशिष्ट-घात गुणनखंडन एल्गोरिथम प्रत्येक d का परीक्षण करता है जो इनपुट बहुपद के आधे से अधिक घात नहीं है। राबिन का एल्गोरिदम लाभ प्राप्त करता है कि अपेक्षाकृत कम d पर विचार करने के लिए कारकों की आवश्यकता नहीं होती है। अन्यथा यह विशिष्ट-घात गुणनखंड एल्गोरिथम के समान होता है। यह निम्नलिखित तथ्य पर आधारित है।
-      इनपुट: एफ में एक मोनिक बहुपद ''एफ''<sub>''q''</sub>[एक्स] डिग्री एन,
-          पी<sub>1</sub>, ..., पी<sub>k</sub>n के सभी विशिष्ट प्रधान भाजक।
+मान लीजिए ''p''<sub>1</sub>, ..., ''p<sub>k</sub>'', n के सभी अभाज्य भाजक हैं और <math>n/p_i=n_i</math>को निरूपित करते हैं, 1 ≤ i ≤ k बहुपद f के लिए घात n के F<sub>q</sub>[x] में F<sub>q</sub>[x] में अप्रासंगिक है यदि और केवल यदि <math> \gcd \left (f,x^{q^{n_i}}-x \right )=1</math>, 1 ≤ i ≤ k के लिए और f <math>x^{q^n}-x</math> को विभाजित करता है। यदि f में n को विभाजित करने वाला गुणक है तो यह गुणक <math>x^{q^{n_i}}-x.</math> में से कम से कम एक को विभाजित करता है।
-      'आउटपुट': या तो f इर्रिड्यूसिबल है या f रिड्यूसिबल है।
+ '''Algorithm''' Rabin Irreducibility Test
+      '''Input''': A monic polynomial ''f'' in '''F'''<sub>''q''</sub>[''x''] of degree ''n'',
+          ''p''<sub>1</sub>, ..., ''p<sub>k</sub>'' all distinct prime divisors of ''n''.
+      '''Output''': Either "''f'' is irreducible" or "''f'' is reducible".
-      'for' j = 1 to k 'do'
+      '''for''' ''j'' = 1 to ''k'' '''do'''
- <math>n_j=n/p_j</math>;
+         ;
-      for ''i'' = 1 to ''k'' करना
+      '''for''' ''i'' = 1 to ''k'' '''do'''
- <math>h:=x^{q^{n_i}}-x \bmod f</math>;
+         ;
-          जी: = जीसीडी (एफ, एच);
+          ''g'' := gcd(''f'', ''h'');
-          'अगर' जी ≠ 1, 'फिर वापसी' च कम हो जाती है 'और बंद करो';
+          '''if''' ''g'' ≠ 1, '''then return''' "''f'' is reducible" '''and STOP''';
-      'के लिए अंत';
+      '''end for''';
-<math>g:= x^{q^{n}}-x \bmod f</math>;
+     ;
-      अगर ''g'' = 0, तो रिटर्न ''f'' इर्रिड्यूसिबल है,
+      '''if''' ''g'' = 0, '''then return''' "''f'' is irreducible",
-          अन्यथा वापसी ''एफ'' कम करने योग्य है
+          '''else return''' "''f'' is reducible"
+इस एल्गोरिथ्म का मूल विचार <math> x^{q^{n_i}} \bmod f</math> की गणना करना है सबसे छोटे <math> n_1,\ldots,n_k</math> से प्रारम्भ करके, बार-बार वर्ग करके या परिमित क्षेत्र फ्रोबेनियस स्वसमाकृतिकता का उपयोग करके पुनः संवाददाता gcd प्राप्त करने के लिए प्रारंभिक बहुपद अंकगणित का उपयोग करते हुए, फ्रोबेनियस स्वसमाकृतिकता के आव्यूह की गणना के लिए Fq में फलन <math>O(n^2 (n+\log q))</math> की आवश्यकता होती है।
-इस एल्गोरिथ्म का मूल विचार गणना करना है <math> x^{q^{n_i}} \bmod f</math> सबसे छोटे से शुरू <math> n_1,\ldots,n_k</math> बार-बार वर्ग करके या परिमित क्षेत्र #Frobenius automorphisms का उपयोग करके, और फिर संवाददाता gcd लेने के लिए। प्रारंभिक बहुपद अंकगणित का उपयोग करते हुए, फ्रोबेनियस ऑटोमोर्फिज्म के मैट्रिक्स की गणना की आवश्यकता है <math>O(n^2 (n+\log q))</math> एफ में संचालन<sub>''q''</sub>, की गणना
 : <math>x^{q^{n_i}}-x \pmod f</math>
-ओ की जरूरत है (एन<sup>3</sup>) आगे के संचालन, और एल्गोरिथम को स्वयं O(kn<sup>2</sup>) संचालन, कुल दे रहा है <math>O(n^2 (n+\log q))</math> एफ में संचालन<sub>''q''</sub>. तेजी से अंकगणित का उपयोग करना (जटिलता <math>O(n\log n)</math> गुणा और भाग के लिए, और <math>O(n(\log n)^2)</math> जीसीडी संगणना के लिए), की गणना <math>x^{q^{n_i}}-x \bmod f</math> बार-बार चुकता करके है <math>O(n^2\log n\log q)</math>, और एल्गोरिथ्म ही है <math>O(kn(\log n)^2)</math>, कुल दे रहा है <math>O(n^2\log n\log q)</math> एफ में संचालन<sub>''q''</sub>.
+इसमे प्रायः ''O''(''n''<sup>3</sup>) संक्रियक की आवश्यकता होती है और एल्गोरिथ्म को स्वयं O(kn<sup>2</sup>) संक्रियक की आवश्यकता होती है क्योकि F<sub>q</sub> में कुल <math>O(n^2 (n+\log q))</math> संक्रियक होते है। गुणन और विभाजन के लिए अंकगणित सम्मिश्रता <math>O(n\log n)</math> और GCD गणना के लिए <math>O(n(\log n)^2)</math> का उपयोग करके <math>x^{q^{n_i}}-x \bmod f</math> की गणना करते है जहाँ वर्ग <math>O(n^2\log n\log q)</math> और एल्गोरिथ्म स्वयं <math>O(kn(\log n)^2)</math> संक्रियक है क्योकि F<sub>q</sub> में कुल <math>O(n^2 (n+\log q))</math> संक्रियक दिए गए है।
 == यह भी देखें ==
-* बेर्लेकैंप का एल्गोरिथम
+* बेर्लेकैंप का एल्गोरिदम
 * कैंटर-ज़सेनहॉस एल्गोरिथम
 * बहुपद गुणनखंडन
@@ Line 268: / Line 264: @@
 * Galois Field:http://designtheory.org/library/encyc/topics/gf.pdf
 * Factoring polynomials over finite fields: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf
-[[Category: बहुपदों]] [[Category: बीजगणित]] [[Category: कंप्यूटर बीजगणित]] [[Category: कोडिंग सिद्धांत]] [[Category: क्रिप्टोग्राफी]] [[Category: कम्प्यूटेशनल संख्या सिद्धांत]] [[Category: बहुपद गुणनखंड एल्गोरिदम]]
-[[Category: Machine Translated Page]]
+[[Category:All articles with unsourced statements]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:Articles with unsourced statements from December 2020]]
+[[Category:Articles with unsourced statements from February 2014]]
 [[Category:Created On 08/06/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:कंप्यूटर बीजगणित]]
+[[Category:कम्प्यूटेशनल संख्या सिद्धांत]]
+[[Category:कोडिंग सिद्धांत]]
+[[Category:क्रिप्टोग्राफी]]
+[[Category:बहुपद गुणनखंड एल्गोरिदम]]
+[[Category:बहुपदों]]
+[[Category:बीजगणित]]

Anonymous

Search

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

Latest revision as of 17:24, 30 June 2023

भूमिका

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

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

उदाहरण

समिश्रता

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

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

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

टिप्पणियाँ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories