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

Revision as of 10:58, 13 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_q से अधिक अपरिवर्तनीय है, डिग्री n के क्षेत्र विस्तार को परिभाषित करता है जो qn तत्वों के साथ क्षेत्र के लिए समरूपता है इस विस्तार के तत्व n से कम डिग्री के बहुपद हैं, घटाव और गुणा F_q के एक तत्व द्वारा बहुपदों में से दो तत्वों का उत्पाद बहुपद के रूप में उनके उत्पाद के f द्वारा विभाजन का शेष है, एक तत्व के व्युत्क्रम की गणना विस्तारित जीसीडी एल्गोरिथ्म द्वारा की जा सकती है (बीजगणितीय एक्सटेंशन का अंकगणित देखें)।

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

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

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

समिश्रता

बहुपद फैक्टरिंग एल्गोरिदम आधारिक बहुपद संचालन जैसे उत्पादों, डिवीजनों, जीसीडी, एक बहुपद मॉडुलो की घातयों का उपयोग करते हैं, आदि। "शास्त्रीय" अंकगणित का उपयोग करके एफq में ओ (n 2) संचालन में अधिकतम n डिग्री के दो बहुपदों का गुणा किया जा सकता है। , या O(nlog(n) log(log(n)) ) "तेज" अंकगणित का उपयोग करके F_q में संचालन। एक यूक्लिडियन विभाजन (शेष के साथ विभाजन) एक ही समय सीमा के भीतर किया जा सकता है। अधिक से अधिक डिग्री के दो बहुपदों के बीच एक बहुपद महानतम आम विभाजक की लागत शास्त्रीय विधियों का उपयोग करके F_q में O(n2) संचालन के रूप में या F_q का उपयोग करके O(nlog2(n) log(log(n)) ) संचालन के रूप में ली जा सकती है। तेज़ तरीके। बहुपद h, g डिग्री के अधिकतम n के लिए, घातांक hq mod g को O(log(q)) बहुपद उत्पादों के साथ किया जा सकता है, वर्ग विधि द्वारा घातांक का उपयोग करके, अर्थात O(n2log(q)) क्लासिकल का उपयोग करके F_q में संचालन विधियों या O(nlog(q)log(n) log(log(n))) तेजी से तरीकों का उपयोग करके F_q में संचालन।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

माना कि

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

दो तरीके हैं:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    return Factors

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

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

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

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

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

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

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

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

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

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

द्वारा

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

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

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

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

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

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

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

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

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

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

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

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

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

समय जटिलता

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

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

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

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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

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

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

बाहरी संबंध

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

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

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

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

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

[1]

[2]

[3]

[4]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 10:58, 13 June 2023

Contents

पृष्ठभूमि

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

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

उदाहरण

समिश्रता

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

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

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

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

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

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

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

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

समय जटिलता

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

यह भी देखें

संदर्भ

टिप्पणियाँ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
 {{Short description|None}}
-गणित और [[कंप्यूटर बीजगणित]] में [[बहुपद]]ों के गुणनखंडन में इसे [[अलघुकरणीय बहुपद]] के [[उत्पाद (गणित)]] में विघटित करना शामिल है। यह अपघटन सैद्धांतिक रूप से संभव है और किसी भी [[क्षेत्र (गणित)]] में गुणांक वाले बहुपदों के लिए अद्वितीय है, लेकिन एक [[ कलन विधि ]] के माध्यम से कारककरण की गणना की अनुमति देने के लिए गुणांक के क्षेत्र पर मजबूत प्रतिबंधों की आवश्यकता होती है। व्यवहार में, एल्गोरिदम को केवल बहुपदों के लिए [[परिमित क्षेत्र]] में गुणांक के साथ, परिमेय के क्षेत्र में या उनमें से किसी एक के परिमित रूप से उत्पन्न क्षेत्र विस्तार के लिए डिज़ाइन किया गया है।
-परिमेय संख्याओं पर [[बहुभिन्नरूपी बहुपद]]ों के मामले सहित सभी गुणनखंडन एल्गोरिदम, इस मामले में समस्या को कम करते हैं; बहुपद गुणनखंड देखें। इसका उपयोग परिमित क्षेत्रों के विभिन्न अनुप्रयोगों के लिए भी किया जाता है, जैसे [[कोडिंग सिद्धांत]] ([[चक्रीय अतिरेक]] कोड और BCH कोड), [[क्रिप्टोग्राफी]] ([[अण्डाकार वक्र क्रिप्टोग्राफी]] के माध्यम से [[सार्वजनिक कुंजी क्रिप्टोग्राफी]]), और [[कम्प्यूटेशनल संख्या सिद्धांत]]।
+गणित और [[कंप्यूटर बीजगणित]] में एक '''[[बहुपद]] के गुणनखंड''' में इसे [[अलघुकरणीय बहुपद|अलघुकरणीय]] कारकों के उत्पाद में विघटित करना सम्मिलित है। यह अपघटन सैद्धांतिक रूप से संभव है और किसी भी [[क्षेत्र (गणित)|क्षेत्र]] में गुणांक वाले बहुपदों के लिए अद्वितीय है, लेकिन एक [[ कलन विधि |एल्गोरिदम]] के माध्यम से कारककरण की गणना की स्वीकृति देने के लिए गुणांक के क्षेत्र पर जटिल प्रतिबंधों की आवश्यकता होती है। व्यवहार में एल्गोरिदम को केवल बहुपदों के लिए परिमित क्षेत्र में गुणांक के साथ परिमेय के क्षेत्र में या उनमें से किसी एक के परिमित रूप से उत्पन्न क्षेत्र विस्तार के लिए निर्मित किया गया है।
+परिमेय संख्याओं पर [[बहुभिन्नरूपी बहुपद|बहुभिन्नरूपी बहुपदों]] के मामले सहित सभी गुणनखंडन एल्गोरिदम, इस मामले में समस्या को कम करते हैं; बहुपद गुणनखंड देखें। इसका उपयोग परिमित क्षेत्रों के विभिन्न अनुप्रयोगों जैसे कि [[कोडिंग सिद्धांत]] ([[चक्रीय अतिरेक]] कोड और बीसीएच कोड), [[क्रिप्टोग्राफी]] ([[अण्डाकार वक्र क्रिप्टोग्राफी|अण्डाकार]] वक्रों के माध्यम से [[सार्वजनिक कुंजी क्रिप्टोग्राफी]]) और [[कम्प्यूटेशनल संख्या सिद्धांत]] के लिए भी किया जाता है।
 एक परिमित क्षेत्र में गुणांक के मामले में बहुभिन्नरूपी बहुपदों के बहुभिन्नरूपी बहुपदों के गुणनखंडन में कोई विशिष्टता नहीं होती है, इस लेख में केवल एक चर वाले बहुपदों पर विचार किया जाता है।
@@ Line 9: / Line 10: @@
 === परिमित क्षेत्र ===
-{{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, को q तत्वों के साथ परिमित क्षेत्र होने दें, जो कि समरूपता तक अद्वितीय है। डिग्री n का एक बहुपद एफ एक से अधिक है, जो F<sub>q</sub> से अधिक अपरिवर्तनीय है, डिग्री n के क्षेत्र विस्तार को परिभाषित करता है जो qn तत्वों के साथ क्षेत्र के लिए समरूपता है इस विस्तार के तत्व n से कम डिग्री के बहुपद हैं, घटाव और गुणा F<sub>q</sub> के एक तत्व द्वारा बहुपदों में से दो तत्वों का उत्पाद बहुपद के रूप में उनके उत्पाद के f द्वारा विभाजन का शेष है, एक तत्व के व्युत्क्रम की गणना विस्तारित जीसीडी एल्गोरिथ्म द्वारा की जा सकती है (बीजगणितीय एक्सटेंशन का अंकगणित देखें)।
-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}}
+परिमित क्षेत्रों पर अलघुकरणीय बहुपद भी फीडबैक शिफ्ट रजिस्टरों और F2n पर असतत लघुगणक का उपयोग करके छद्म यादृच्छिक संख्या निर्माण के लिए उपयोगी होते हैं।
+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 में से कम से कम एक वर्ग है, क्योंकि दो गैर-वर्गों का गुणनफल एक वर्ग है और इसलिए हमारे पास है
-# अगर <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>
+=== समिश्रता ===
+बहुपद फैक्टरिंग एल्गोरिदम आधारिक बहुपद संचालन जैसे उत्पादों, डिवीजनों, जीसीडी, एक बहुपद मॉडुलो की घातयों का उपयोग करते हैं, आदि। "शास्त्रीय" अंकगणित का उपयोग करके एफq में ओ (n 2) संचालन में अधिकतम n डिग्री के दो बहुपदों का गुणा किया जा सकता है। , या O(nlog(n) log(log(n)) ) "तेज" अंकगणित का उपयोग करके F<sub>q</sub> में संचालन। एक यूक्लिडियन विभाजन (शेष के साथ विभाजन) एक ही समय सीमा के भीतर किया जा सकता है। अधिक से अधिक डिग्री के दो बहुपदों के बीच एक बहुपद महानतम आम विभाजक की लागत शास्त्रीय विधियों का उपयोग करके F<sub>q</sub> में O(n2) संचालन के रूप में या F<sub>q</sub> का उपयोग करके O(nlog2(n) log(log(n)) ) संचालन के रूप में ली जा सकती है। तेज़ तरीके। बहुपद h, g डिग्री के अधिकतम n के लिए, घातांक hq mod g को O(log(q)) बहुपद उत्पादों के साथ किया जा सकता है, वर्ग विधि द्वारा घातांक का उपयोग करके, अर्थात O(n2log(q)) क्लासिकल का उपयोग करके F<sub>q</sub> में संचालन विधियों या O(nlog(q)log(n) log(log(n))) तेजी से तरीकों का उपयोग करके 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>, बहुपदों के अंकगणित के लिए शास्त्रीय एल्गोरिदम का उपयोग करना।
+अनुवर्ती एल्गोरिदम में, बहुपदों के अंकगणित के लिए शास्त्रीय एल्गोरिदम का उपयोग करते हुए, F<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> से आते हैं। यह एल्गोरिदम पहले व्युत्पन्न को निर्धारित करता है और फिर बहुपद और उसके व्युत्पन्न के जीसीडी की गणना करता है। यदि यह एक नहीं है तो जीसीडी को फिर से मूल बहुपद में विभाजित किया जाता है, बशर्ते कि व्युत्पन्न शून्य न हो (ऐसा मामला जो परिमित क्षेत्रों पर परिभाषित गैर-निरंतर बहुपदों के लिए सम्मिलित है)।
-यह एल्गोरिदम इस तथ्य का उपयोग करता है कि, यदि बहुपद का व्युत्पन्न शून्य है, तो यह x में बहुपद है<sup>p</sup>, जो कि, यदि गुणांक 'F' से संबंधित है<sub>''p''</sub>, x को x से प्रतिस्थापित करने पर प्राप्त बहुपद की pth शक्ति<sup>1/पैसा</sup>. यदि गुणांक 'एफ' से संबंधित नहीं हैं<sub>''p''</sub>, शून्य अवकलज वाले बहुपद का pवाँ मूल x पर उसी प्रतिस्थापन द्वारा प्राप्त किया जाता है, जिसे गुणांकों में [[फ्रोबेनियस एंडोमोर्फिज्म]] के व्युत्क्रम को लागू करके पूरा किया जाता है। {{Citation needed|date=December 2020}}
+यह एल्गोरिथ्म इस तथ्य का उपयोग करता है कि, यदि बहुपद का व्युत्पन्न शून्य है, तो यह xp में एक बहुपद है, जो कि, यदि गुणांक F<sub>p</sub> से संबंधित है, तो x द्वारा x<sup>1/p</sup> को प्रतिस्थापित करके प्राप्त बहुपद की pth घात। यदि गुणांक F<sub>p</sub> से संबंधित नहीं हैं, तो शून्य अवकलज वाले बहुपद का pth मूल x पर उसी प्रतिस्थापन द्वारा प्राप्त किया जाता है, जिसे गुणांकों के लिए [[फ्रोबेनियस एंडोमोर्फिज्म]] के व्युत्क्रम को लागू करके पूरा किया जाता है।{{Citation needed|date=December 2020}}
-यह एल्गोरिथ्म [[विशेषता (बीजगणित)]] शून्य के एक क्षेत्र पर भी काम करता है, केवल अंतर के साथ कि यह कभी भी निर्देशों के ब्लॉक में प्रवेश नहीं करता है जहां पीटीएच जड़ों की गणना की जाती है। हालांकि, इस मामले में, वर्ग-मुक्त बहुपद#यून का एल्गोरिदम|यून का एल्गोरिदम अधिक कुशल है क्योंकि यह कम डिग्री के बहुपदों के सबसे बड़े सामान्य भाजक की गणना करता है। एक परिणाम यह है कि, पूर्णांकों पर एक बहुपद का गुणनखंड करते समय, निम्न एल्गोरिथम का उपयोग नहीं किया जाता है: पहले पूर्णांकों पर वर्ग-मुक्त गुणनखंडन की गणना करता है, और परिणामी बहुपदों का गुणनखंड करने के लिए, एक पी चुनता है जैसे कि वे वर्ग-मुक्त रहते हैं मोडुलो पी।
+यह एल्गोरिदम विशेषता शून्य के क्षेत्र में भी काम करता है, केवल अंतर के साथ कि यह कभी भी निर्देशों के ब्लॉक में प्रवेश नहीं करता है जहां p<sup>th</sup> जड़ों की गणना की जाती है। हालांकि, इस मामले में, यूं का एल्गोरिदम अधिक कुशल है क्योंकि यह कम डिग्री के बहुपदों के सबसे बड़े सामान्य विभाजक की गणना करता है। एक परिणाम यह है कि जब पूर्णांकों पर एक बहुपद का गुणनखंड किया जाता है तो निम्न एल्गोरिथम का उपयोग नहीं किया जाता है जो पहले पूर्णांकों पर वर्ग-मुक्त गुणनखंडन की गणना करता है, और परिणामी बहुपदों का गुणनखंड करने के लिए, एक पी चुनता है जैसे कि वे वर्ग-मुक्त मॉड्यूलो 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'' ← '''जीसीडी'''(''f'', ''f''′)
-      डब्ल्यू ← एफ/सी
+      ''w'' ← ''f''/''c''
-      # चरण 1: डब्ल्यू में सभी कारकों की पहचान करें
+      # Step 1: Identify all factors in ''w''
-      मैं ← 1
+      ''i'' ← 1
-      'जबकि' डब्ल्यू ≠ 1 'करो'
+      '''while''' ''w'' ≠ 1 '''do'''
-          वाई ← 'जीसीडी' (डब्ल्यू, सी)
+          ''y'' ← '''जीसीडी'''(''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 के सभी अलघुकरणीय कारकों के गुणनफल की पहचान की जाए। यह दो चरणों में किया जाता है। पहला कदम एफ के औपचारिक व्युत्पन्न का उपयोग करता है ताकि बहुलता वाले सभी कारकों को पी से विभाजित न किया जा सके। दूसरा चरण शेष कारकों की पहचान करता है। जैसा कि शेष सभी कारकों में p से विभाज्य बहुलता है, जिसका अर्थ है कि वे p की घातयाँ हैं, कोई भी केवल pth वर्गमूल ले सकता है और पुनरावर्तन लागू कर सकता है।
-विचार यह है कि समान बहुलता वाले 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>
 तीन तत्वों के साथ क्षेत्र में फ़ैक्टर होना।
@@ Line 97: / Line 94: @@
 एल्गोरिदम पहले गणना करता है
 : <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, हम while लूप से बाहर निकलते हैं। चूँकि {{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''}} गुणनखंड किया जाने वाला बहुपद हो।
+यह एल्गोरिथम एक वर्ग-मुक्त बहुपद को बहुपदों के एक उत्पाद में विभाजित करता है, जिनके अलघुकरणीय कारकों में समान डिग्री होती है। मान लीजिए {{math|''f'' ∈ '''F'''<sub>''q''</sub>[''x'']}} डिग्री {{math|''n''}} का गुणनखंड किया जाने वाला बहुपद है।
+  '''Algorithm''' Distinct-degree factorization(DDF)
-  एल्गोरिथम डिस्टिक्ट-डिग्री फ़ैक्टराइज़ेशन (DDF)
+      '''Input''': A monic square-free polynomial  ''f'' ∈ '''F'''<sub>''q''</sub>[''x'']
-      इनपुट: एक मोनिक वर्ग-मुक्त बहुपद  {{math|''f'' ∈ '''F'''<sub>''q''</sub>[''x'']}}
+      '''Output''': The set of all pairs (''g'', ''d''), such that
-      आउटपुट: सभी जोड़ियों का सेट {{math|(''g'', ''d'')}}, ऐसा है कि
+              ''f'' has an irreducible factor of degree ''d'' and
- {{math|''f''}} डिग्री का एक अप्रासंगिक कारक है {{math|''d''}} और
+              ''g'' is the product of all monic irreducible factors of ''f'' of degree ''d''.
-{{math|''g''}} के सभी मोनिक इरेड्यूसिबल कारकों का उत्पाद है {{math|''f''}} डिग्री {{math|''d''}}.
+      '''Begin'''
-      शुरू
-<math>i:=1;\qquad S:=\emptyset,\qquad f^*:=f;</math>
+         '''while'''  '''do'''
-जबकि <math>\deg f^*\ge 2i</math> करना
- <math>g=\gcd(f^*, x^{q^i}-x)</math>
+             '''if''' ''g'' ≠ 1, '''then'''
-अगर {{math|''g'' ≠ 1}}, तब
+                 ;
- <math>S:=S\cup\{(g,i)\}</math>;
-<math>f^*:=f^*/g</math>
+             '''end if'''
-अगर अंत
+             ''i'' := ''i'' + 1;
-{{math|1=''i'' := ''i'' + 1;}}
+          '''end while''';
-          समाप्त जबकि;
+          '''if''' , '''then''' ;
-          अगर <math>f^*\ne 1</math>, तब <math>S:= S\cup\{(f^*,\deg f^*)\}</math>;
+          '''if''' , '''then return''' {(''f'', 1)},
-          अगर <math>S=\emptyset</math>, फिर लौटें {{math|{{mset|(''f'', 1)}}}},
+              '''else return''' ''S''
-              वरना लौट जाओ {{math|''S''}}
+      '''End'''
-      अंत
 एल्गोरिथ्म की शुद्धता निम्नलिखित पर आधारित है:
-<ब्लॉककोट>लेम्मा. ''i'' के लिए ≥ 1 बहुपद
+लेम्मा i ≥ 1 के लिए बहुपद
 : <math>x^{q^i}-x \in \mathbf{F}_q[x]</math>
-एफ में सभी मोनिक इरेड्यूसबल बहुपदों का उत्पाद है<sub>''q''</sub>[x] जिसकी डिग्री i को विभाजित करती है।</blockquote>
+Fq [x] में सभी मोनिक अलघुकरणीय बहुपदों का गुणनफल है, जिसकी डिग्री i को विभाजित करती है।
-पहली नज़र में, यह कुशल नहीं है क्योंकि इसमें उस डिग्री के बहुपदों के जीसीडी की गणना करना शामिल है जो इनपुट बहुपद की डिग्री में घातीय है। हालाँकि,
+पहली नज़र में, यह कुशल नहीं है क्योंकि इसमें उस डिग्री के बहुपदों के जीसीडी की गणना करना सम्मिलित है जो इनपुट बहुपद की डिग्री में घातीय है। हालाँकि,
 : <math>g=\gcd \left (f^*, x^{q^i}-x \right )</math>
 द्वारा प्रतिस्थापित किया जा सकता है
@@ Line 136: / Line 130: @@
 : <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 घात Fq पर एक रैखिक नक्शा है, हम इसके आव्यूह की गणना कर सकते हैं
 : <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)2) संचालन के साथ)। यह 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 की आवश्यकता होती है। अधिक गुणनखंडन एल्गोरिदम के लिए उदाहरण देखें नुथ की पुस्तक द आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग वॉल्यूम 2।
-      'इनपुट:' एक परिमित क्षेत्र 'एफ'<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''' जीसीडी(''g'', ''u'') ≠ 1 and जीसीडी(''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>
+इसका तात्पर्य है कि बहुपद जीसीडी (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 चुनकर
@@ Line 191: / Line 187: @@
 द्वारा
 : <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 वर्ग-मुक्त गुणनखंडन के साथ घट सकता है, इससे महत्वपूर्ण चरणों की जटिलता कम हो जाती है)।
+वैधता का प्रमाण उपरोक्त के समान है, फ़ील्ड Fq[x]/fi के प्रत्यक्ष उत्पाद को q तत्वों के साथ उनके उपक्षेत्रों के प्रत्यक्ष उत्पाद द्वारा प्रतिस्थापित करना। एल्गोरिथ्म के लिए <math>O(n^2\log(r)\log(q))</math> में जटिलता विघटित है, रैखिक के आव्यूह की गणना के लिए <math>O(n^2(\log(q)+n))</math> (जो पहले से ही वर्ग-मुक्त गुणनखंड में गणना की जा सकती है) और इसके कर्नेल की गणना के लिए O(n3)। यह ध्यान दिया जा सकता है कि यह एल्गोरिथम तब भी काम करता है जब कारकों में समान डिग्री नहीं होती है (इस मामले में कारकों की संख्या आर, जबकि लूप को रोकने के लिए आवश्यक है, कर्नेल के आयाम के रूप में पाया जाता है)। फिर भी, यदि इस एल्गोरिथम का उपयोग करने से पहले वर्ग-मुक्त गुणनखंडन किया जाता है, तो जटिलता थोड़ी बेहतर होती है (चूंकि 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 वांछित गुणनखंड है, जहां gi डिग्री d के विशिष्ट मोनिक अलघुकरणीय बहुपद हैं। चलो n = डिग्री (जी) = केडी। हम वलय R = Fq[x]/g पर विचार करते हैं और R में x की छवि को x द्वारा भी निरूपित करते हैं। वलय R फ़ील्ड्स Ri = Fq[x]/gi का प्रत्यक्ष उत्पाद है, और हम प्राकृतिक पाई द्वारा निरूपित करते हैं R से Ri पर समाकारिता Fq पर Ri का Galois समूह आदेश d का चक्रीय है, जो फ़ील्ड ऑटोमोर्फिज़्म u → up द्वारा उत्पन्न होता है। इससे पता चलता है कि Ri में gi के मूल हैं
 : <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 के लिए (दो मोनिक बहुपदों की जड़ें समान हैं)। जैसा कि जीआई अलग-अलग इंडेक्स (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} हो।
+एक अलग समुच्चय होने के बाद, शौप का एल्गोरिथ्म पूर्ववर्ती खंड के अंतिम एल्गोरिथ्म के रूप में आगे बढ़ता है, बस निर्देश को बदलकर रैखिक मानचित्र के कर्नेल में यादृच्छिक एच पर चुनें <math> v \to v^q-v \pmod f</math>h + i चुनें जिसमें h in S और i in {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 का परीक्षण करता है जो इनपुट बहुपद के आधे से अधिक डिग्री नहीं है। राबिन का एल्गोरिदम लाभ उठाता है कि कम डी पर विचार करने के लिए कारकों की आवश्यकता नहीं होती है। अन्यथा, यह विशिष्ट-डिग्री गुणनखंड एल्गोरिथम के समान है। यह निम्नलिखित तथ्य पर आधारित है।
+विशिष्ट-डिग्री गुणनखंड एल्गोरिथम की तरह, राबिन का एल्गोरिथम ऊपर बताए गए लेम्मा पर आधारित है।<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>
+<math>n/p_i=n_i</math>, 1 ≤ i ≤ k बहुपद f के लिए Fq[x] में डिग्री n, Fq[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 को विभाजित न करने वाली डिग्री का कारक है, तो f x^{q^n}-x को विभाजित नहीं करता है; यदि f में n को विभाजित करने वाला गुणक है तो यह गुणक <math>x^{q^{n_i}}-x.</math> में से कम से कम एक को विभाजित करता है।
-एल्गोरिथम राबिन इरेड्यूसबिलिटी टेस्ट
+ '''Algorithm''' Rabin Irreducibility Test
-      इनपुट: एफ में एक मोनिक बहुपद ''एफ''<sub>''q''</sub>[एक्स] डिग्री एन,
+      '''Input''': A monic polynomial ''f'' in '''F'''<sub>''q''</sub>[''x''] of degree ''n'',
-          पी<sub>1</sub>, ..., पी<sub>k</sub>n के सभी विशिष्ट प्रधान भाजक।
+          ''p''<sub>1</sub>, ..., ''p<sub>k</sub>'' all distinct prime divisors of ''n''.
-      'आउटपुट': या तो f इर्रिड्यूसिबल है या f रिड्यूसिबल है।
+      '''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'' := जीसीडी(''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> बार-बार वर्ग करके या परिमित क्षेत्र #Frobenius automorphisms का उपयोग करके, और फिर संवाददाता जीसीडी लेने के लिए। प्रारंभिक बहुपद अंकगणित का उपयोग करते हुए, फ्रोबेनियस ऑटोमोर्फिज्म के आव्यूह की गणना की आवश्यकता है <math>O(n^2 (n+\log q))</math> एफ में संचालन<sub>''q''</sub>, की गणना
-इस एल्गोरिथ्म का मूल विचार गणना करना है <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(kn<sup>2</sup>) आगे के संचालन की आवश्यकता है और एल्गोरिथ्म को स्वयं O(kn<sup>2</sup>) संचालन की आवश्यकता है, Fq में कुल <math>O(n^2 (n+\log q))</math> संचालन देता है। तेजी से अंकगणित का उपयोग करना (जटिलता <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> देता है ) F<sub>q</sub> में संचालन।
 == यह भी देखें ==
-* बेर्लेकैंप का एल्गोरिथम
+* बेर्लेकैंप का एल्गोरिदम
 * कैंटर-ज़सेनहॉस एल्गोरिथम
 * बहुपद गुणनखंडन

Anonymous

Search

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

Revision as of 10:58, 13 June 2023

पृष्ठभूमि

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

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

उदाहरण

समिश्रता

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

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

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

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

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

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

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

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

समय जटिलता

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

यह भी देखें

संदर्भ

टिप्पणियाँ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories