बहुपद का गुणनखंडन: Difference between revisions

Latest revision as of 17:29, 24 August 2023

बहुपद या बहुपद का गुणनखंडन किसी दिए गए क्षेत्र में या पूर्णांकों में गुणांक के साथ बहुपद को उसी डोमेन में गुणांक वाले अखण्डनीय कारकों के उत्पाद के रूप में व्यक्त करता हैI पहला बहुपद कारक एल्गोरिथ्म थियोडोर वॉन शुबर्ट द्वारा 1793 में प्रकाशित किया गया था।^[1] लियोपोल्ड क्रोनकर ने 1882 में शूबर्ट के एल्गोरिथ्म को फिर से खोजा और बीजगणित में बहुभिन्नरूपी बहुपद और गुणांक तक इसका विस्तार किया गया । बहुपद गुणनखंड कंप्यूटर की बीजगणित प्रणाली के मूलभूत घटकों में से एक है। इस विषय में ज्यादा विस्तार 1965 में किया गया थाI

लंबे समय से ज्ञात परिमित एल्गोरिदम को पहली बार कंप्यूटर पर रखा गया थाI वह इसे खोजने में अधिक अक्षम हो गए थेI थ्योरी के तथ्य के अनुरूप देखा जाए तो ज्ञात होता है कि बहुभिन्नरूपी बहुपद की डिग्री 100 तक और एक मध्यम आकार (100 बिट्स तक) के गुणांक के साथ कंप्यूटर के कुछ मिनटों में आधुनिक एल्गोरिदम द्वारा किया जा सकता है।पहला कंप्यूटर बीजगणितीय सिस्टम 1965 में लॉन्च हुआ थाI

आधुनिक एल्गोरिदम और कंप्यूटर से हजारों अंकों के गुणांक वाले 1000 से अधिक डिग्री के बहुपद को प्रमाणित कर सकते हैंI ^[2] परिमित क्षेत्र पर बहुपद का गुडनखंड एक मौलिक निर्णय था I

प्रश्न का निर्माण

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

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

बहुपद गुणनखंडन का प्रश्न केवल संगणनीय क्षेत्र में गुणांकों के लिए प्रस्तावित है I बहुपद के प्रत्येक पद के तत्व को कंप्यूटर में दर्शाया जा सकता हैI जिसके लिए अंकगणित संचालन के लिए एल्गोरिदम हैं। हालांकि यह एक पर्याप्त स्थिति नहीं हैI फ्रॉहलिच और शेफर्डसन ऐसे क्षेत्रों का उदाहरण देते हैं जिनके लिए कोई कारक एल्गोरिथ्म मौजूद नहीं हो सकता है।^[3]

गुणांक के कारक एल्गोरिदम के लिए जाने जाते हैं I एल्गोरिदम में तर्कसंगत और प्राइम मॉड्यूलर अंकगणित का क्षेत्र शामिल हैं। पूर्णांक गुणांक भी सरल हैं। क्रोनकर की वर्गीकृत विधि केवल ऐतिहासिक दृष्टिकोण से आकर्षक हैI आधुनिक एल्गोरिदम अनुक्रम द्वारा आगे बढ़ते हैंI

वर्ग मुक्त कारक

परिमित क्षेत्रों पर कारक

और कटौती

बहुभिन्नरूपी मामले से अविभाज्य मामले तक
ग्राउंड फील्ड में एक बीजीय विस्तार में गुणांक से गुणांक तक
तर्कसंगत गुणांक से पूर्णांक गुणांक तक
नीचे दिए गए उदाहरण में अच्छी तरह से चुने गए P के लिए P तत्वों के साथ प्रमुख क्षेत्र में पूर्णांक गुणांक से गुणांक तक संचारित होते हैं ।

आदिम भाग -कंटेंट फैक्टरकरण

इस खंड में दिखाया गया है कि Q (तर्कसंगत संख्या) और Z (पूर्णांक) पर फैक्टरिंग अनिवार्य रूप से एक ही समस्या है।

एक बहुपद p 'Z [' X ] की सामग्री निरूपित प्रतियोगिता ( p )के साइन तक और इसके गुणांक का सबसे बड़ा सामान्य विभाजक है। P का साधारण भाग प्राइमपार्ट ( p ) = p /cont. ( p ) है जो कि पूर्णांक गुणांक के साथ साधारण बहुपद है। यह पूर्णांक और साधारण बहुपद के उत्पाद में Pके कारक को परिभाषित करता है।यह कारक सामग्री के संकेत के लिए अद्वितीय है।यह सामग्री के संकेत को चुनने के लिए सामान्य चलन है जैसे कि साधारण भाग का प्रमुख गुणांक सकारात्मक है।

उदाहरण के लिए

-10x^{2}+5x+5=(-5)(2x^{2}-x-1)\,

सामग्री और साधारण भाग में एक कारक है।

तर्कसंगत गुणांक के साथ प्रत्येक बहुपद q लिखा जा सकता है

q={\frac {p}{c}},

जहां p and 'z' [x] और c, 'z': यह q के गुणांक के सभी भाजक (उदाहरण के लिए उनके उत्पाद) और p = cq के सभी भाजक के लिए C पर्याप्त वैल्यू है।Q की सामग्री को इस प्रकार परिभाषित किया गया हैI

{\text{cont}}(q)={\frac {{\text{cont}}(p)}{c}},

पूर्णांक गुणांक के साथ बहुपद के लिए Q,P का हिस्सा है। यह तर्कसंगत संख्या में कारक को परिभाषित करता है और पूर्णांक गुणांक के साथ साधारण बहुपद को प्रमाणित करता है। यह कारक संकेत की प्राथमिकता के लिए अद्वितीय है।

उदाहरण के लिए,

{\frac {x^{5}}{3}}+{\frac {7x^{2}}{2}}+2x+1={\frac {2x^{5}+21x^{2}+12x+6}{6}}

सामग्री और प्राचीन भाग में एक ही कारक है।

गॉस ने साबित किया कि दो साधारण बहुपदों का उत्पाद भी साधारण हैI इसका तात्पर्य यह है कि साधारण बहुपद तर्कसंगत लोगों पर अखंडनीय हैI इसका तात्पर्य यह है कि तर्कसंगत गुणांक के साथ बहुपद के तर्कसंगतताओं पर कारक अपने साधारण भाग के पूर्णांक पर कारक के समान है। इसी तरह पूर्णांक गुणांक के साथ बहुपद के पूर्णांक का कारक इसकी सामग्री के प्राचीन भाग के कारक का उत्पाद है।

दूसरे शब्दों में पूर्णांक GCD की गणना पूर्णांक गुणांक के साथ बहुपद के कारक के लिए तर्कसंगत बहुपद कारक को कम करती हैI

यदि Z को एक फ़ील्ड F पर बहुपद रिंग द्वारा प्रतिस्थापित किया जाता है तो सब कुछ सही तौर पर निर्धारित होता है I Q को एक ही चर में F पर तर्कसंगत कार्यों द्वारा प्रतिस्थापित किया जाता हैI एक अंतर के साथ साइन को F में एक उल्टे स्थिरांक द्वारा गुणन तक प्रतिस्थापित किया जाना चाहिए। यह f पर बहुभिन्नरूपी बहुपद के कारक के लिए f के विशुद्ध रूप से पारलौकिक क्षेत्र विस्तार पर कारक को कम करता है।

वर्ग-मुक्त कारक

यदि एक बहुपद के दो या दो से अधिक कारक समान हैं तो बहुपद कारक वर्ग का एक बहुपद है। कई कारक भी बहुपद के व्युत्पन्न का एक कारक है .

न्यूनतम बहुपद के लिए एक कारक कई जड़ों के बराबर हैं। वर्ग-मुक्त कारक इसलिए अधिकांश बहुपद कारक एल्गोरिदम में पहला कदम है। तर्कसंगतताओं पर एक तरफा बहुपद के लिए वर्ग-मुक्त बहुपद के एल्गोरिथ्म अधिक महत्वपूर्ण होते हैं। ऐसे कारक जो एक वर्ग के गुणक नहीं हैं जीसीडी (f(x), f '(x)) से शुरू होने वाले GCD संगणनाओं के अनुक्रम को प्रारंभिक बहुपद का गुणनखंड करने के लिए निष्पादित करते हैं। एक वर्ग का GCD (f (x), f '(x)) के साथ शुरू होने वाले GCD संगणनाओं का अनुक्रम प्रदर्शन करता है। प्रारंभिक बहुपद को फैक्टर करने के लिए प्रत्येक वर्ग-मुक्त कारक को कारक बनाने के लिए पर्याप्त है।

एल्गोरिथ्म बहुपद रिंग पर अविभाजित बहुपद के रूप में बहुभिन्नरूपी बहुपद पर विचार करके बहुभिन्नरूपी मामले में इसका विस्तार करता है।

एक परिमित क्षेत्र पर एक बहुपद के मामले का एल्गोरिथ्म केवल तभी लागू होता है जब डिग्री विशेषता से छोटी होती हैI गैर-शून्य बहुपद का व्युत्पन्न शून्य हो सकता है (पी तत्वों के साथ क्षेत्र में, व्युत्पन्न, व्युत्पन्न, व्युत्पन्न, व्युत्पन्न का व्युत्पन्न हो सकता है एक्स में एक बहुपद^Pहमेशा शून्य होता है) फिर भी जीसीडी संगणना का उत्तराधिकार बहुपद और उसके व्युत्पन्न से शुरू होता हैI वर्ग-मुक्त अपघटन की गणना करने की अनुमति देता हैI

वर्गीकृत तरीके

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

दो विधियाँ जो एक यूनीवेट बहुपद से शुरू होती हैं उन कारकों को खोजने के लिए पूर्णांक गुणांक के साथ शुरू होती हैं जो पूर्णांक गुणांक के साथ बहुपद भी हैं।

रैखिक कारक प्राप्त करना

यदि बहुपद को फैक्टर किया जाता हैI तर्कसंगत गुणांक के साथ सभी रैखिक कारकों को तर्कसंगत रूट परीक्षण का उपयोग करके पाया जा सकता है। $a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}$ तो सभी संभव रैखिक कारक फॉर्म के हैं $b_{1}x-b_{0}$ , कहाँ पे $b_{1}$ का एक पूर्णांक कारक है $a_{n}$ तथा $b_{0}$ का एक पूर्णांक कारक है $a_{0}$ है ।पूर्णांक कारकों के सभी संभावित संयोजनों को वैधता के लिए परीक्षण किया जा सकता हैI प्रत्येक वैध को बहुपद लंबे विभाजन का उपयोग करके बाहर किया जा सकता है। यदि मूल बहुपद कारकों का उत्पाद है जिनमें से कम से कम दो डिग्री या उच्चतर हैं तो यह तकनीक केवल आंशिक कारक प्रदान करती है I विशेष रूप से यदि वास्तव में एक गैर-रैखिक कारक है तो सभी रैखिक कारकों को पीछे कर दिया जाता है I एक क्यूबिक बहुपद के मामले में यदि क्यूबिक कारक है तो तर्कसंगत रूट परीक्षण एक पूर्ण कारक देता हैI

क्रोनकर की विधि

क्रोनकर की विधि का उद्देश्य पूर्णांक गुणांक के साथ पूर्णांक गुणांक के साथ न्यूनतम बहुपद कारक करना है।

विधि इस तथ्य का उपयोग करती है कि पूर्णांक मूल्यों पर पूर्णांक बहुपद का मूल्यांकन करना पूर्णांक का उत्पादन करना चाहिए। अगर $f(x)$ पूर्णांक गुणांक के साथ बहुपद है फिर $f(a)$ जैसे ही पूर्णांक है $a$ एक पूर्णांक है। केवल संभावित पूर्णांक मानों की एक सीमित संख्या हैI $a$ अगर $g(x)$ का एक कारक है $f(x),$ का मान है $g(a)$ के कारकों में एक होना चाहिए I $f(a).$ यदि कोई किसी दिए गए डिग्री के कारकों को खोजता है I $d$ विचार कर सकते हैं $d+1$ मान, $a_{0},\ldots ,a_{d}$ के लिये $a$ , जो टपल के लिए संभावनाओं की सीमित संख्या देते हैंI $(f(a_{0}),\ldots ,f(a_{d}).$ इस तरह के प्रत्येक ट्यूपल में सबसे अधिक डिग्री के एक अद्वितीय बहुपद को परिभाषित करता हैI $d$ जिसकी गणना बहुपद प्रक्षेप द्वारा की जा सकती हैI बहुपद विभाजन द्वारा कारक होने के लिए परीक्षण किया जा सकता है। एक संपूर्ण खोज सबसे अधिक डिग्री के सभी कारकों को खोजने की अनुमति देती है।

उदाहरण के लिए विचार करें

f(x)=x^{5}+x^{4}+x^{2}+x+2

।

यदि यह बहुपद z पर कारक है तो इसके कम से कम एक कारक $p(x)$ दो या उससे कम डिग्री का होना चाहिए इसलिए $p(x)$ विशिष्ट रूप से तीन मूल्यों द्वारा निर्धारित किया जाता है।इस प्रकार हम तीन मूल्यों की गणना करते हैं $f(0)=2$ , $f(1)=6$ तथा $f(-1)=2$ ।

यदि इन मानों में से एक 0 है, तो हमारे पास एक रैखिक कारक है।यदि मान नॉनज़ेरो हैं तो हम प्रत्येक के लिए संभावित कारकों को सूचीबद्ध कर सकते हैं।अब 2 केवल कारक के रूप में हो सकता हैI

1 × 2, 2 × 1, () 1) × (−2), या (−2) × () 1)।

यदि एक दूसरी डिग्री पूर्णांक बहुपद कारक है तो इनमें से एक मान को लेना होगा I

P (0) = 1, 2, −1, या −2

और इसी तरह पी (1) के लिए।6 के आठ कारक हैं (1 × 6 और 2 × 3 के लिए चार प्रत्येक) कुल 4 × 4 × 8 = 128 संभावित ट्रिपल्स (पी (0), पी (1), पी () 1)जिनमें से आधे को दूसरे आधे की नकारात्मक के रूप में छोड़ दिया जा सकता है। इस प्रकार हमें 64 स्पष्ट पूर्णांक बहुपद की जांच करनी चाहिएI $p(x)=ax^{2}+bx+c$ के रूप में संभव कारकों $f(x)$ से परीक्षण करने से पता चलता है कि $p(x)=x^{2}+x+1$

(G (0), G (1), G () 1)) = (1,3,1) कारक से निर्मित है $f(x)$

P (x) द्वारा f (x) को विभाजित करना अन्य कारक देता है $q(x)=x^{3}-x+2$ , ताकि $f(x)=p(x)q(x)$ पी (एक्स) और क्यू (एक्स) कारकों को खोजने के लिए पुनरावर्ती का परीक्षण कर सकता हैI इस मामले में तर्कसंगत रूट परीक्षण का उपयोग करके वे दोनों इसलिए f (x) का अतार्किक कारक हैI^[4]

f(x)=p(x)q(x)=(x^{2}+x+1)(x^{3}-x+2).

आधुनिक तरीके

परिमित क्षेत्रों पर फैक्टरिंग

पूर्णांकों पर अविभाज्य बहुपदों का गुणनखंड करना

यदि $f(x)$ पूर्णांक पर एक अविभाज्य बहुपद है, माना जाता है

प्रिमिटिव पार्ट कंटेंट फैक्टराइजेशन के लिए सामग्री-मुक्त और #वर्ग-मुक्त कारक की गणना करके शुरू होता हैI $B$ $g(x)$ के गुणांक का कारक है हैI निरपेक्ष मूल्य $B$ अगर $m$ हैI पूर्णांक से बड़ा $2B$ और $g(x)$ मोडुलो के नाम से जाना जाता हैI $m$ , $g(x)$ की मॉड से पुनर्निर्माण किया जा सकता है $m$ ।

एल्गोरिथ्म इस प्रकार आगे बढ़ता है। सबसे पहले, एक प्राइम संख्या $p$ चुनेंI ऐसी छवि $f(x)$ वर्ग-मुक्त कारक रहता है | वर्ग-मुक्त और उसी डिग्री के रूप में $f(x)$

तत्कालीन कारक $f(x)$ आधुनिक $p$ का कारक है I यह पूर्णांक बहुपद का उत्पादन करता है $f_{1}(x),...,f_{r}(x)$ जिसका उत्पाद मेल खाता है $f(x)$ आधुनिक $p$ अगला, हेन्सेल के लेम्मा को लागू करें | हेन्सल $f_{i}(x)$ इस तरह से अपडेट करता है कि उनका उत्पाद $f(x)$ आधुनिक $p^{a}$ से मेल खाता हैI $2B$ : इस प्रकार प्रत्येक $f_{i}(x)$ एक अच्छी तरह से परिभाषित पूर्णांक बहुपद के अनुरूप है। सापेक्ष $p^{a}$ , बहुपद $f(x)$ हैI $2^{r}$ कारक सभी इकाइयों तक सबसेट के उत्पाद ${f_{1}(x),...,f_{r}(x)}$ आधुनिक $p^{a}$ कारक मोडुलो $p^{a}$ के सही कारकों के अनुरूप नहीं होना चाहिएI $f(x)$ में $\mathbb {Z} [x]$ आसानी से $\mathbb {Z} [x]$ विभाजन में परीक्षण कर सकते हैंI इस तरह सभी न्यूनतम कारकों को सबसे अधिक जाँच करके पाया जा सकता हैI तर्कसंगत बहुपदों को फैक्टरिंग के लिए पहला बहुपद समय एल्गोरिथ्म लेंस्ट्रा, लेंस्ट्रा और लवसेज़ द्वारा खोजा गया था Iयह लेंस्ट्रा -लेंस्ट्रा -लोवाज़ जाली लेटिस बेसिस रिडक्शन एल्गोरिथ्म का एक अनुप्रयोग है।

एलएलएल फैक्टरकरण एल्गोरिथ्म का एक सरलीकृत संस्करण हैI बहुपद के एक जटिल (या पी-एडिक) रूट α की गणना $f(x)$ उच्च परिशुद्धता के लिए 1, α, α के बीच एक अनुमानित रैखिक संबंध खोजने के लिए एल्गोरिथम का उपयोग किया जाता हैI ए³पूर्णांक और गुणांक के बीच निकट संबंध हो सकता है I किसी सटीक कारक के लिए अपरिवर्तनीयता प्रमाण का उत्पादन करती है। यद्यपि यह विधि बहुपद समय में समाप्त होती है लेकिन इसका उपयोग व्यवहार में नहीं किया जाता है क्योंकि जाली में उच्च आयाम और विशाल प्रविष्टियाँ होती हैं जो गणना को धीमा कर देती है।

एल्गोरिथ्म में घातीय जटिलता कॉम्बिनेटरियल समस्या आती हैI अत्याधुनिक फैक्टरिंग कार्यान्वयन के समान तरीके से काम करते हैंI इस दृष्टिकोण में कारकों का उपयोग गुणांक की गणना करने के लिए नहीं किया जाता है बल्कि वैक्टर की गणना करने के लिए किया जाता हैi $r$ {0,1} में प्रविष्टियाँ जो सबसेट को एनकोड करती हैंi

बीजगणितीय एक्सटेंशन (ट्रेजर की विधि) पर फैक्टरिंग

बहुपद कारक $p(x)\in K[x]$ का कार्य कर सकते हैं जहां क्षेत्र $K$ का एक परिमित विस्तार हैI सबसे पहले #वर्ग-मुक्त कारक का उपयोग करके वर्ग-मुक्त कर सकते हैंI हम मान सकते हैं कि बहुपद वर्ग-मुक्त हैI भागफल की अंगूठी को परिभाषित करते हैं $L=K[x]/p(x)$ डिग्री का $n=[L:\mathbb {Q} ]=\deg p(x)\,[K:\mathbb {Q} ]$ यह एक क्षेत्र नहीं है जब तक $p(x)$ अपरिवर्तनीय हैI

$p(x)=\prod _{i=1}^{m}p_{i}(x)$

p (x) का वांछित कारक है रिंग विशिष्ट रूप से क्षेत्रों में विशिष्ट रूप से विघटित हो जाती हैI

L=K[x]/p(x)\cong \prod _{i=1}^{m}K[x]/p_{i}(x).

हम कारक को जाने बिना इस अपघटन को पाएंगे।सबसे पहले स्पष्ट रूप से एक बीजगणित के रूप में एल लिखते हैं I $\mathbb {Q}$ एक यादृच्छिक तत्व चुनते हैं $\alpha \in L$ जो $L$ ऊपर $\mathbb {Q}$ आदिम तत्व प्रमेय द्वारा उच्च संभावना के साथ उत्पन्न करता है। न्यूनतम बहुपद $q(y)\in \mathbb {Q} [y]$ की गणना कर सकते हैं ।

q(y)=\prod _{i=1}^{n}q_{i}(y).

इस प्रकार हमारे पास है

L\cong \mathbb {Q} [y]/q(y)\cong \prod _{i=1}^{n}\mathbb {Q} [y]/q_{i}(y),

$y\leftrightarrow (y,y,\ldots ,y)$ पिछले अपघटन के लिए $L$ । आइसोमोर्फिक होना चाहिएI

एल के जनरेटर के साथ x हैंI $K$ ऊपर $\mathbb {Q}$ इन्हें एक बहुपद के रूप में लिखना $\alpha$ , एम्बेडिंग का निर्धारण कर सकते हैं $x$ तथा $K$ प्रत्येक घटक में $\mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)$ की न्यूनतम बहुपद का पता लगाकर $x$ में $\mathbb {Q} [y]/q_{i}(y)$ , $p_{i}(x)$ और इस प्रकार कारक $p(x)$ ऊपर $K.$ की गणना करते हैं I

यह भी देखें

Factorization § Polynomials, प्राथमिक हेयुरिस्टिक तरीकों और स्पष्ट सूत्रों के लिए

ग्रन्थसूची

↑ FT Schubert: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, p. 172-182(1793)
↑ An example of degree 2401, taking 7.35 seconds, is found in Section 4 in: Hart, van Hoeij, Novocin: Practical Polynomial Factoring in Polynomial Time ISSAC'2011 Proceedings, p. 163-170 (2011).
↑ Fröhlich, A.; Shepherdson, J. C. (1955). "On the factorisation of polynomials in a finite number of steps". Mathematische Zeitschrift. 62 (1): 331–334. doi:10.1007/bf01180640. ISSN 0025-5874.
↑ Van der Waerden, Sections 5.4 and 5.6

Fröhlich, A.; Shepherson, J. C. (1955), "On the factorisation of polynomials in a finite number of steps", Mathematische Zeitschrift, 62 (1): 331–334, doi:10.1007/BF01180640, ISSN 0025-5874
Trager, B.M. (1976), "Algebraic Factoring and Rational Function Integration", Proc. SYMSAC 76, Symsac '76: 219–226, doi:10.1145/800205.806338
Bernard Beauzamy, Per Enflo, Paul Wang (October 1994). "Quantitative Estimates for Polynomials in One or Several Variables: From Analysis and Number Theory to Symbolic and Massively Parallel Computation". Mathematics Magazine. 67 (4): 243–257. doi:10.2307/2690843. JSTOR 2690843.{{cite journal}}: CS1 maint: multiple names: authors list (link) (accessible to readers with undergraduate mathematics)
Cohen, Henri (1993). A course in computational algebraic number theory. Graduate Texts in Mathematics. Vol. 138. Berlin, New York: Springer-Verlag. ISBN 978-3-540-55640-4. MR 1228206.
Kaltofen, Erich (1982), "Factorization of polynomials", in B. Buchberger; R. Loos; G. Collins (eds.), Computer Algebra, Springer Verlag, pp. 95–113, CiteSeerX 10.1.1.39.7916
Knuth, Donald E (1997). "4.6.2 Factorization of Polynomials". Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (Third ed.). Reading, Massachusetts: Addison-Wesley. pp. 439–461, 678–691. ISBN 978-0-201-89684-8.
Lenstra, A. K.; Lenstra, H. W.; Lovász, László (1982). "Factoring polynomials with rational coefficients". Mathematische Annalen. 261 (4): 515–534. CiteSeerX 10.1.1.310.318. doi:10.1007/BF01457454. ISSN 0025-5831. MR 0682664.
Van der Waerden, Algebra (1970), trans. Blum and Schulenberger, Frederick Ungar.

अग्रिम पठन

Kaltofen, Erich (1990), "Polynomial Factorization 1982-1986", in D. V. Chudnovsky; R. D. Jenks (eds.), Computers in Mathematics, Lecture Notes in Pure and Applied Mathematics, vol. 125, Marcel Dekker, Inc., CiteSeerX 10.1.1.68.7461
Kaltofen, Erich (1992), "Polynomial Factorization 1987–1991" (PDF), Proceedings of Latin '92, Springer Lect. Notes Comput. Sci., vol. 583, Springer, retrieved October 14, 2012
Ivanyos, Gabor; Marek, Karpinski; Saxena, Nitin (2009), "Schemes for Deterministic Polynomial Factoring", Proc. ISSAC 2009: 191–198, arXiv:0804.1974, doi:10.1145/1576702.1576730, ISBN 9781605586090

] ]

[1] FT Schubert: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, p. 172-182(1793)

[2] An example of degree 2401, taking 7.35 seconds, is found in Section 4 in: Hart, van Hoeij, Novocin: Practical Polynomial Factoring in Polynomial Time ISSAC'2011 Proceedings, p. 163-170 (2011).

[3] Fröhlich, A.; Shepherdson, J. C. (1955). "On the factorisation of polynomials in a finite number of steps". Mathematische Zeitschrift. 62 (1): 331–334. doi:10.1007/bf01180640. ISSN 0025-5874.

[4] Van der Waerden, Sections 5.4 and 5.6

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
 {{Short description|Computational method}}
 {{About|factorization algorithms|paper-and-pencil methods|Factorization#Polynomials}}
-बहुपद या बहुपद का गुणनखंडन किसी दिए गए क्षेत्र में या पूर्णांकों में गुणांक के साथ एक बहुपद को उसी डोमेन में गुणांक वाले अखण्डनीय कारकों के उत्पाद के रूप में व्यक्त करता हैI पहला बहुपद कारक एल्गोरिथ्म थियोडोर वॉन शुबर्ट द्वारा 1793 में प्रकाशित किया गया था।<ref>FT Schubert: ''De Inventione Divisorum'' Nova Acta Academiae Scientiarum Petropolitanae v.11, p. 172-182(1793)</ref> लियोपोल्ड क्रोनकर ने 1882 में शूबर्ट के एल्गोरिथ्म को फिर से खोजा और बीजगणित में बहुभिन्नरूपी बहुपद और गुणांक तक इसका विस्तार किया गया । बहुपद गुणनखंड कंप्यूटर की बीजगणित प्रणाली के मूलभूत घटकों में से एक है। इस विषय में ज्यादा विस्तार 1965 में किया गया थाI
+बहुपद या बहुपद का गुणनखंडन किसी दिए गए क्षेत्र में या पूर्णांकों में गुणांक के साथ बहुपद को उसी डोमेन में गुणांक वाले अखण्डनीय कारकों के उत्पाद के रूप में व्यक्त करता हैI पहला बहुपद कारक एल्गोरिथ्म थियोडोर वॉन शुबर्ट द्वारा 1793 में प्रकाशित किया गया था।<ref>FT Schubert: ''De Inventione Divisorum'' Nova Acta Academiae Scientiarum Petropolitanae v.11, p. 172-182(1793)</ref> लियोपोल्ड क्रोनकर ने 1882 में शूबर्ट के एल्गोरिथ्म को फिर से खोजा और बीजगणित में बहुभिन्नरूपी बहुपद और गुणांक तक इसका विस्तार किया गया । बहुपद गुणनखंड कंप्यूटर की बीजगणित प्रणाली के मूलभूत घटकों में से एक है। इस विषय में ज्यादा विस्तार 1965 में किया गया थाI
 <blockquote>
@@ Line 32: / Line 32: @@
 इस खंड में दिखाया गया है कि Q (तर्कसंगत संख्या) और Z (पूर्णांक) पर फैक्टरिंग अनिवार्य रूप से एक ही समस्या है।
-एक बहुपद '' p '' 'Z [' X ''] की '' सामग्री ''निरूपित प्रतियोगिता ('' p '')के साइन तक और इसके गुणांक का सबसे बड़ा सामान्य विभाजक है।'' P ''का साधारण ''भाग ''प्राइमपार्ट ('' p '') = '' p ''/cont ('' p '') है जो कि पूर्णांक गुणांक के साथ साधारण बहुपद है। यह पूर्णांक और साधारण बहुपद के उत्पाद में '' P''के कारक को परिभाषित करता है।यह कारक सामग्री के संकेत के लिए अद्वितीय है।यह सामग्री के संकेत को चुनने के लिए सामान्य चलन है जैसे कि साधारण भाग का प्रमुख गुणांक सकारात्मक है।''
+एक बहुपद '' p '' 'Z [' X ''] की '' सामग्री ''निरूपित प्रतियोगिता ('' p '')के साइन तक और इसके गुणांक का सबसे बड़ा सामान्य विभाजक है।'' P ''का साधारण ''भाग ''प्राइमपार्ट ('' p '') = '' p ''/cont. ('' p '') है जो कि पूर्णांक गुणांक के साथ साधारण बहुपद है। यह पूर्णांक और साधारण बहुपद के उत्पाद में '' P''के कारक को परिभाषित करता है।यह कारक सामग्री के संकेत के लिए अद्वितीय है।यह सामग्री के संकेत को चुनने के लिए सामान्य चलन है जैसे कि साधारण भाग का प्रमुख गुणांक सकारात्मक है।''
 उदाहरण के लिए
@@ Line 45: / Line 45: @@
 जहां p and 'z' [x] और c, 'z': यह q के गुणांक के सभी भाजक (उदाहरण के लिए उनके उत्पाद) और p = cq के सभी भाजक के लिए C पर्याप्त वैल्यू है।Q की सामग्री को इस प्रकार परिभाषित किया गया हैI
 :<math>\text{cont} (q) =\frac{\text{cont} (p)}{c},</math>
-पूर्णांक गुणांक के साथ बहुपद के लिए Q,P का हिस्सा है।  यह तर्कसंगत संख्या में कारक को परिभाषित करता है और पूर्णांक गुणांक के साथ साधारण बहुपद को प्रमाणित करता है। यह कारक संकेत की पसंद के लिए भी अद्वितीय है।
+पूर्णांक गुणांक के साथ बहुपद के लिए Q,P का हिस्सा है।  यह तर्कसंगत संख्या में कारक को परिभाषित करता है और पूर्णांक गुणांक के साथ साधारण बहुपद को प्रमाणित करता है। यह कारक संकेत की प्राथमिकता के लिए अद्वितीय है।
 उदाहरण के लिए,
 :<math>
 \frac{x^5}{3} + \frac{7x^2}{2} + 2x + 1 = \frac{2x^5 + 21x^2 + 12x + 6}{6}</math>
-सामग्री और ''प्राचीन  ''भाग में एक कारक है।
+सामग्री और ''प्राचीन  ''भाग में एक ही कारक है।
-गॉस ने साबित किया कि दो साधारण बहुपदों का उत्पाद भी साधारण हैI इसका तात्पर्य यह है कि साधारण बहुपद तर्कसंगत लोगों पर अखंडनीय हैI  इसका तात्पर्य यह है कि तर्कसंगत गुणांक के साथ एक बहुपद के तर्कसंगतताओं पर कारक अपने साधारण भाग के पूर्णांक पर कारक के समान है। इसी तरह पूर्णांक गुणांक के साथ बहुपद के पूर्णांक का कारक इसकी सामग्री के प्राचीन भाग के कारक का उत्पाद है।
+गॉस ने साबित किया कि दो साधारण बहुपदों का उत्पाद भी साधारण हैI इसका तात्पर्य यह है कि साधारण बहुपद तर्कसंगत लोगों पर अखंडनीय हैI  इसका तात्पर्य यह है कि तर्कसंगत गुणांक के साथ बहुपद के तर्कसंगतताओं पर कारक अपने साधारण भाग के पूर्णांक पर कारक के समान है। इसी तरह पूर्णांक गुणांक के साथ बहुपद के पूर्णांक का कारक इसकी सामग्री के प्राचीन भाग के कारक का उत्पाद है।
 दूसरे शब्दों में पूर्णांक GCD की गणना पूर्णांक गुणांक के साथ बहुपद के कारक के लिए तर्कसंगत बहुपद कारक को कम करती हैI
-यदि Z को एक फ़ील्ड '' F '' पर बहुपद रिंग द्वारा प्रतिस्थापित किया जाता है तो सब कुछ सही तौर पर निर्धारित होता है I Q को एक ही चर में '' F '' पर तर्कसंगत कार्यों द्वारा प्रतिस्थापित किया जाता हैI एक अंतर के साथ साइन को ''F'' में एक उल्टे स्थिरांक द्वारा गुणन तक प्रतिस्थापित किया जाना चाहिए। यह '' f '' पर बहुभिन्नरूपी बहुपद के कारक के लिए '' f '' के विशुद्ध रूप से पारलौकिक क्षेत्र विस्तार पर कारक को कम करता है।
+यदि Z को एक फ़ील्ड'' F '' पर बहुपद रिंग द्वारा प्रतिस्थापित किया जाता है तो सब कुछ सही तौर पर निर्धारित होता है I Q को एक ही चर में '' F '' पर तर्कसंगत कार्यों द्वारा प्रतिस्थापित किया जाता हैI एक अंतर के साथ साइन को ''F'' में एक उल्टे स्थिरांक द्वारा गुणन तक प्रतिस्थापित किया जाना चाहिए। यह '' f '' पर बहुभिन्नरूपी बहुपद के कारक के लिए '' f '' के विशुद्ध रूप से पारलौकिक क्षेत्र विस्तार पर कारक को कम करता है।
 == वर्ग-मुक्त कारक ==
 {{Main|Square-free polynomial}}
-यदि एक बहुपद के दो या अधिक कारक समान हैं, तो बहुपद इस कारक के वर्ग का एक बहु है। कई कारक भी बहुपद के व्युत्पन्न का एक कारक है (किसी भी चर के संबंध में, यदि कई)।
+यदि एक बहुपद के दो या दो से अधिक कारक समान हैं तो बहुपद कारक वर्ग का एक बहुपद है। कई कारक भी बहुपद के व्युत्पन्न का एक कारक है .
-Univariate बहुपद के लिए, कई कारक कई जड़ों (एक उपयुक्त एक्सटेंशन फ़ील्ड पर) के बराबर हैं। तर्कसंगतताओं पर एकतरफा बहुपद के लिए (या अधिक आम तौर पर विशेषता शून्य के एक क्षेत्र पर), वर्ग-मुक्त बहुपद#यूं के एल्गोरिथ्म। यूं के एल्गोरिथ्म ने कुशलता से बहुपद को वर्ग-मुक्त कारकों में कारक करने के लिए इसका शोषण किया, जो कि कई नहीं हैं। एक वर्ग का, GCD (f (x), f '(x)) के साथ शुरू होने वाले GCD संगणनाओं का एक अनुक्रम प्रदर्शन करता है। प्रारंभिक बहुपद को फैक्टर करने के लिए, यह प्रत्येक वर्ग-मुक्त कारक को कारक बनाने के लिए पर्याप्त है। वर्ग-मुक्त कारक इसलिए अधिकांश बहुपद कारक एल्गोरिदम में पहला कदम है।
+न्यूनतम बहुपद के लिए एक कारक कई जड़ों के बराबर हैं। वर्ग-मुक्त कारक इसलिए अधिकांश बहुपद कारक एल्गोरिदम में पहला कदम है। तर्कसंगतताओं पर एक तरफा बहुपद के लिए वर्ग-मुक्त बहुपद के एल्गोरिथ्म अधिक महत्वपूर्ण होते हैं। ऐसे कारक जो एक वर्ग के गुणक नहीं हैं जीसीडी (f(x), f '(x)) से शुरू होने वाले GCD संगणनाओं के अनुक्रम को प्रारंभिक बहुपद का गुणनखंड करने के लिए निष्पादित करते हैं। एक वर्ग का GCD (f (x), f '(x)) के साथ शुरू होने वाले GCD संगणनाओं का अनुक्रम प्रदर्शन करता है। प्रारंभिक बहुपद को फैक्टर करने के लिए प्रत्येक वर्ग-मुक्त कारक को कारक बनाने के लिए पर्याप्त है।
-यूं का एल्गोरिथ्म एक बहुपद रिंग पर एक अविभाजित बहुपद के रूप में एक बहुभिन्नरूपी बहुपद पर विचार करके बहुभिन्नरूपी मामले में इसका विस्तार करता है।
+एल्गोरिथ्म बहुपद रिंग पर अविभाजित बहुपद के रूप में बहुभिन्नरूपी बहुपद पर विचार करके बहुभिन्नरूपी मामले में इसका विस्तार करता है।
-एक परिमित क्षेत्र पर एक बहुपद के मामले में, यूं का एल्गोरिथ्म केवल तभी लागू होता है जब डिग्री विशेषता से छोटी होती है, क्योंकि, अन्यथा, एक गैर-शून्य बहुपद का व्युत्पन्न शून्य हो सकता है (पी तत्वों के साथ क्षेत्र में, व्युत्पन्न, व्युत्पन्न, व्युत्पन्न, व्युत्पन्न का व्युत्पन्न हो सकता है एक्स में एक बहुपद<sup>P </sup> हमेशा शून्य होता है)।फिर भी, जीसीडी संगणना का एक उत्तराधिकार, बहुपद और उसके व्युत्पन्न से शुरू होता है, एक को वर्ग-मुक्त अपघटन की गणना करने की अनुमति देता है;परिमित क्षेत्रों#वर्ग-मुक्त कारक पर बहुपद कारक देखें।
+एक परिमित क्षेत्र पर एक बहुपद के मामले का एल्गोरिथ्म केवल तभी लागू होता है जब डिग्री विशेषता से छोटी होती हैI  गैर-शून्य बहुपद का व्युत्पन्न शून्य हो सकता है (पी तत्वों के साथ क्षेत्र में, व्युत्पन्न, व्युत्पन्न, व्युत्पन्न, व्युत्पन्न का व्युत्पन्न हो सकता है एक्स में एक बहुपद<sup>P </sup>हमेशा शून्य होता है) फिर भी जीसीडी संगणना का उत्तराधिकार बहुपद और उसके व्युत्पन्न से शुरू होता हैI वर्ग-मुक्त अपघटन की गणना करने की अनुमति देता हैI
-== शास्त्रीय तरीके ==
+== वर्गीकृत तरीके ==
-यह खंड पाठ्यपुस्तक के तरीकों का वर्णन करता है जो हाथ से कंप्यूटिंग करते समय सुविधाजनक हो सकता है।इन विधियों का उपयोग कंप्यूटर कम्प्यूटेशन के लिए नहीं किया जाता है क्योंकि वे पूर्णांक कारक का उपयोग करते हैं, जो वर्तमान में बहुपद कारक की तुलना में धीमा है।
+यह खंड पाठ्यपुस्तक के तरीकों का वर्णन करता है जो हाथ से कंप्यूटिंग करते समय सुविधाजनक हो सकता है।इन विधियों का उपयोग कंप्यूटर कम्प्यूटेशन के लिए नहीं किया जाता है क्योंकि वे पूर्णांक कारक का उपयोग करते हैं जो वर्तमान में बहुपद कारक की तुलना में धीमा है।
-दो विधियाँ जो एक यूनीवेट बहुपद से शुरू होती हैं, उन कारकों को खोजने के लिए पूर्णांक गुणांक के साथ शुरू होती हैं जो पूर्णांक गुणांक के साथ बहुपद भी हैं।
+दो विधियाँ जो एक यूनीवेट बहुपद से शुरू होती हैं उन कारकों को खोजने के लिए पूर्णांक गुणांक के साथ शुरू होती हैं जो पूर्णांक गुणांक के साथ बहुपद भी हैं।
 === रैखिक कारक प्राप्त करना ===
-तर्कसंगत गुणांक के साथ सभी रैखिक कारकों को तर्कसंगत रूट परीक्षण का उपयोग करके पाया जा सकता है।यदि बहुपद को फैक्टर किया जाता है <math>a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0</math>, तो सभी संभव रैखिक कारक फॉर्म के हैं <math>b_1x-b_0</math>, कहाँ पे <math>b_1</math> का एक पूर्णांक कारक है <math>a_n</math> तथा <math>b_0</math> का एक पूर्णांक कारक है <math>a_0</math>।पूर्णांक कारकों के सभी संभावित संयोजनों को वैधता के लिए परीक्षण किया जा सकता है, और प्रत्येक वैध को बहुपद लंबे विभाजन का उपयोग करके बाहर किया जा सकता है।यदि मूल बहुपद कारकों का उत्पाद है, जिनमें से कम से कम दो डिग्री 2 या उच्चतर हैं, तो यह तकनीक केवल एक आंशिक कारक प्रदान करती है;अन्यथा कारक पूरा हो गया है।विशेष रूप से, यदि वास्तव में एक गैर-रैखिक कारक है, तो यह सभी रैखिक कारकों के बाद छोड़ दिया गया बहुपद होगा।एक क्यूबिक बहुपद के मामले में, यदि क्यूबिक बिल्कुल भी कारक है, तो तर्कसंगत रूट परीक्षण एक पूर्ण कारक देता है, या तो एक रैखिक कारक और एक ireducible द्विघात कारक में, या तीन रैखिक कारकों में।
+यदि बहुपद को फैक्टर किया जाता हैI तर्कसंगत गुणांक के साथ सभी रैखिक कारकों को तर्कसंगत रूट परीक्षण का उपयोग करके पाया जा सकता है।<math>a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0</math> तो सभी संभव रैखिक कारक फॉर्म के हैं <math>b_1x-b_0</math>, कहाँ पे <math>b_1</math> का एक पूर्णांक कारक है <math>a_n</math> तथा <math>b_0</math> का एक पूर्णांक कारक है <math>a_0</math>है ।पूर्णांक कारकों के सभी संभावित संयोजनों को वैधता के लिए परीक्षण किया जा सकता हैI प्रत्येक वैध को बहुपद लंबे विभाजन का उपयोग करके बाहर किया जा सकता है। यदि मूल बहुपद कारकों का उत्पाद है जिनमें से कम से कम दो डिग्री या उच्चतर हैं तो यह तकनीक केवल आंशिक कारक प्रदान करती है I विशेष रूप से यदि वास्तव में एक गैर-रैखिक कारक है तो सभी रैखिक कारकों को पीछे कर दिया जाता है I एक क्यूबिक बहुपद के मामले में यदि क्यूबिक कारक है तो तर्कसंगत रूट परीक्षण एक पूर्ण कारक देता हैI
 === क्रोनकर की विधि ===
-क्रोनकर की विधि का उद्देश्य पूर्णांक गुणांक के साथ पूर्णांक गुणांक के साथ univariate बहुपद कारक करना है।
+क्रोनकर की विधि का उद्देश्य पूर्णांक गुणांक के साथ पूर्णांक गुणांक के साथ न्यूनतम बहुपद कारक करना है।
-विधि इस तथ्य का उपयोग करती है कि पूर्णांक मूल्यों पर पूर्णांक बहुपद का मूल्यांकन करना पूर्णांक का उत्पादन करना चाहिए।वह है, अगर <math>f(x)</math> पूर्णांक गुणांक के साथ एक बहुपद है, फिर <math>f(a)</math> जैसे ही एक पूर्णांक है {{mvar|a}} एक पूर्णांक है।के कारक के लिए केवल संभावित पूर्णांक मानों की एक सीमित संख्या है {{mvar|a}}।तो अगर <math>g(x)</math> का एक कारक है <math>f(x),</math> का मान है <math>g(a)</math> के कारकों में से एक होना चाहिए <math>f(a).</math>
+विधि इस तथ्य का उपयोग करती है कि पूर्णांक मूल्यों पर पूर्णांक बहुपद का मूल्यांकन करना पूर्णांक का उत्पादन करना चाहिए। अगर <math>f(x)</math> पूर्णांक गुणांक के साथ बहुपद है फिर <math>f(a)</math> जैसे ही पूर्णांक है {{mvar|a}} एक पूर्णांक है। केवल संभावित पूर्णांक मानों की एक सीमित संख्या हैI {{mvar|a}} अगर <math>g(x)</math> का एक कारक है <math>f(x),</math> का मान है <math>g(a)</math> के कारकों में एक होना चाहिए I <math>f(a).</math>यदि कोई किसी दिए गए डिग्री के कारकों को खोजता है I {{mvar|d}} विचार कर सकते हैं <math>d+1</math> मान, <math>a_0, \ldots, a_d</math> के लिये {{mvar|a}}, जो टपल के लिए संभावनाओं की सीमित संख्या देते हैंI <math>(f(a_0),\ldots, f(a_d).</math> इस तरह के प्रत्येक ट्यूपल में सबसे अधिक डिग्री के एक अद्वितीय बहुपद को परिभाषित करता हैI {{mvar|d}} जिसकी गणना बहुपद प्रक्षेप द्वारा की जा सकती हैI बहुपद विभाजन द्वारा कारक होने के लिए परीक्षण किया जा सकता है। एक संपूर्ण खोज सबसे अधिक डिग्री के सभी कारकों को खोजने की अनुमति देती है।
-यदि कोई किसी दिए गए डिग्री के कारकों को खोजता है {{mvar|d}}, एक विचार कर सकते हैं <math>d+1</math> मान, <math>a_0, \ldots, a_d</math> के लिये {{mvar|a}}, जो टपल के लिए संभावनाओं की एक सीमित संख्या देते हैं <math>(f(a_0),\ldots, f(a_d).</math> इस तरह के प्रत्येक ट्यूपल में सबसे अधिक डिग्री के एक अद्वितीय बहुपद को परिभाषित करता है {{mvar|d}}, जिसे बहुपद प्रक्षेप द्वारा गणना की जा सकती है, और बहुपद विभाजन द्वारा एक कारक होने के लिए परीक्षण किया जा सकता है।तो, एक संपूर्ण खोज सबसे अधिक डिग्री के सभी कारकों को खोजने की अनुमति देती है {{mvar|d}}।
-उदाहरण के लिए, विचार करें
+उदाहरण के लिए विचार करें
 :<math>f(x) = x^5 + x^4 + x^2 + x + 2</math>।
-यदि यह बहुपद z पर कारक है, तो इसके कम से कम एक कारक <math>p(x)</math> दो या उससे कम डिग्री का होना चाहिए, इसलिए <math>p(x)</math> विशिष्ट रूप से तीन मूल्यों द्वारा निर्धारित किया जाता है।इस प्रकार, हम तीन मूल्यों की गणना करते हैं <math>f(0) = 2</math>, <math>f(1) = 6</math> तथा <math>f(-1) = 2</math>।यदि इन मानों में से एक 0 है, तो हमारे पास एक रैखिक कारक है।यदि मान नॉनज़ेरो हैं, तो हम प्रत्येक के लिए संभावित कारकों को सूचीबद्ध कर सकते हैं।अब, 2 केवल कारक के रूप में हो सकता है
+यदि यह बहुपद z पर कारक है तो इसके कम से कम एक कारक <math>p(x)</math> दो या उससे कम डिग्री का होना चाहिए इसलिए <math>p(x)</math> विशिष्ट रूप से तीन मूल्यों द्वारा निर्धारित किया जाता है।इस प्रकार हम तीन मूल्यों की गणना करते हैं <math>f(0) = 2</math>, <math>f(1) = 6</math> तथा <math>f(-1) = 2</math>।
+यदि इन मानों में से एक 0 है, तो हमारे पास एक रैखिक कारक है।यदि मान नॉनज़ेरो हैं तो हम प्रत्येक के लिए संभावित कारकों को सूचीबद्ध कर सकते हैं।अब 2 केवल कारक के रूप में हो सकता हैI
 : 1 × 2, 2 × 1, () 1) × (−2), या (−2) × () 1)।
-इसलिए, यदि एक दूसरी डिग्री पूर्णांक बहुपद कारक मौजूद है, तो इसे मानों में से एक को लेना होगा
+यदि एक दूसरी डिग्री पूर्णांक बहुपद कारक है तो इनमें से एक मान को लेना होगा I
 : P (0) = 1, 2, −1, या −2
-और इसी तरह पी (1) के लिए।6 के आठ कारक हैं (1 × 6 और 2 × 3 के लिए चार प्रत्येक), कुल 4 × 4 × 8 = 128 संभावित ट्रिपल्स (पी (0), पी (1), पी () 1)),जिनमें से आधे को दूसरे आधे की नकारात्मक के रूप में छोड़ दिया जा सकता है।इस प्रकार, हमें 64 स्पष्ट पूर्णांक बहुपद की जांच करनी चाहिए <math>p(x) = ax^2+bx+c</math> के रूप में संभव कारकों <math>f(x)</math>।उन्हें पूरी तरह से परीक्षण करने से पता चलता है कि
+और इसी तरह पी (1) के लिए।6 के आठ कारक हैं (1 × 6 और 2 × 3 के लिए चार प्रत्येक) कुल 4 × 4 × 8 = 128 संभावित ट्रिपल्स (पी (0), पी (1), पी () 1)जिनमें से आधे को दूसरे आधे की नकारात्मक के रूप में छोड़ दिया जा सकता है। इस प्रकार हमें 64 स्पष्ट पूर्णांक बहुपद की जांच करनी चाहिएI <math>p(x) = ax^2+bx+c</math> के रूप में संभव कारकों <math>f(x)</math> से परीक्षण करने से पता चलता है कि <math>p(x) = x^2 + x + 1</math>
-:<math>p(x) = x^2 + x + 1</math>
+(G (0), G (1), G () 1)) = (1,3,1) कारक से निर्मित है <math>f(x)</math>
-(G (0), G (1), G () 1)) = (1,3,1) कारक से निर्मित <math>f(x)</math>।
-P (x) द्वारा f (x) को विभाजित करना अन्य कारक देता है <math>q(x) = x^3 - x + 2</math>, ताकि <math>f(x) = p(x)q(x)</math>।
+P (x) द्वारा f (x) को विभाजित करना अन्य कारक देता है <math>q(x) = x^3 - x + 2</math>, ताकि <math>f(x) = p(x)q(x)</math>पी (एक्स) और क्यू (एक्स) कारकों को खोजने के लिए पुनरावर्ती का परीक्षण कर सकता हैI इस मामले में तर्कसंगत रूट परीक्षण का उपयोग करके वे दोनों इसलिए f (x) का अतार्किक कारक हैI<ref>''Van der Waerden'', Sections 5.4 and 5.6</ref>
-अब कोई पी (एक्स) और क्यू (एक्स) के कारकों को खोजने के लिए पुनरावर्ती परीक्षण कर सकता है, इस मामले में तर्कसंगत रूट परीक्षण का उपयोग करके।यह पता चला है कि वे दोनों अतार्किक हैं, इसलिए f (x) का अतार्किक कारक है:<ref>''Van der Waerden'', Sections 5.4 and 5.6</ref>
 :<math>f(x) = p(x)q(x) = (x^2 + x + 1)(x^3 - x + 2). </math>
+आधुनिक तरीके
-== आधुनिक तरीके ==
 === परिमित क्षेत्रों पर फैक्टरिंग ===
 {{Main|Factorization of polynomials over finite fields|Berlekamp's algorithm|Cantor–Zassenhaus algorithm}}
 === पूर्णांकों पर अविभाज्य बहुपदों का गुणनखंड करना ===
 यदि <math>f(x)</math> पूर्णांक पर एक अविभाज्य बहुपद है, माना जाता है
-#primitive part-content फैक्टराइजेशन होने के लिए | सामग्री-मुक्त
+#प्रिमिटिव पार्ट कंटेंट फैक्टराइजेशन के लिए सामग्री-मुक्त और #वर्ग-मुक्त कारक की गणना करके शुरू होता हैI <math>B</math> <math>g(x)</math> के गुणांक का कारक है हैI निरपेक्ष मूल्य <math>B</math> अगर <math>m</math> हैI  पूर्णांक से बड़ा <math>2B</math> और <math>g(x)</math> मोडुलो के नाम से जाना जाता हैI <math>m</math>, <math>g(x)</math> की मॉड से पुनर्निर्माण किया जा सकता है <math>m</math>।
-और #वर्ग-मुक्त कारक | वर्ग-मुक्त, एक बाउंड की गणना करके शुरू होता है <math>B</math>
+एल्गोरिथ्म इस प्रकार आगे बढ़ता है। सबसे पहले, एक प्राइम संख्या <math>p</math> चुनेंI ऐसी छवि <math>f(x)</math> वर्ग-मुक्त कारक रहता है | वर्ग-मुक्त और उसी डिग्री के रूप में <math>f(x)</math>
-ऐसा कोई कारक है <math>g(x)</math> के गुणांक है
-निरपेक्ष मूल्य <math>B</math>।इस तरह, अगर <math>m</math> है
+तत्कालीन कारक <math>f(x)</math> आधुनिक <math>p</math>का कारक है I यह पूर्णांक बहुपद का उत्पादन करता है <math>f_1(x),...,f_r(x)</math> जिसका उत्पाद मेल खाता है <math>f(x)</math> आधुनिक <math>p</math>अगला, हेन्सेल के लेम्मा को लागू करें | हेन्सल <math>f_i(x)</math> इस तरह से अपडेट करता है कि उनका उत्पाद <math>f(x)</math> आधुनिक <math>p^a</math>से मेल खाता हैI  <math>2B</math>: इस प्रकार प्रत्येक <math>f_i(x)</math> एक अच्छी तरह से परिभाषित पूर्णांक बहुपद के अनुरूप है। सापेक्ष <math>p^a</math>, बहुपद <math>f(x)</math> हैI <math>2^r</math> कारक सभी इकाइयों तक सबसेट के उत्पाद <math>{f_1(x),...,f_r(x)}</math> आधुनिक <math>p^a</math>कारक मोडुलो <math>p^a</math> के सही कारकों के अनुरूप नहीं होना चाहिएI <math>f(x)</math> में <math>\mathbb Z[x]</math> आसानी से  <math>\mathbb Z[x]</math> विभाजन में परीक्षण कर सकते हैंI इस तरह सभी न्यूनतम कारकों को सबसे अधिक जाँच करके पाया जा सकता हैI तर्कसंगत बहुपदों को फैक्टरिंग के लिए पहला बहुपद समय एल्गोरिथ्म लेंस्ट्रा, लेंस्ट्रा और लवसेज़ द्वारा खोजा गया था Iयह लेंस्ट्रा -लेंस्ट्रा -लोवाज़ जाली लेटिस बेसिस रिडक्शन एल्गोरिथ्म का एक अनुप्रयोग है।
-एक पूर्णांक से बड़ा <math>2B</math>, और अगर <math>g(x)</math> मोडुलो जाना जाता है
-<math>m</math>, फिर <math>g(x)</math> इसकी छवि मॉड से पुनर्निर्माण किया जा सकता है <math>m</math>।
+एलएलएल फैक्टरकरण एल्गोरिथ्म का एक सरलीकृत संस्करण हैI बहुपद के एक जटिल (या पी-एडिक) रूट α की गणना <math>f(x)</math> उच्च परिशुद्धता के लिए 1, α, α के बीच एक अनुमानित रैखिक संबंध खोजने के लिए एल्गोरिथम का उपयोग किया जाता हैI  ए<sup>3 </sup>पूर्णांक और गुणांक के बीच निकट संबंध हो सकता है I किसी सटीक कारक के लिए अपरिवर्तनीयता प्रमाण का उत्पादन करती है। यद्यपि यह विधि बहुपद समय में समाप्त होती है लेकिन इसका उपयोग व्यवहार में नहीं किया जाता है क्योंकि जाली में उच्च आयाम और विशाल प्रविष्टियाँ होती हैं जो गणना को धीमा कर देती है।
+एल्गोरिथ्म में घातीय जटिलता कॉम्बिनेटरियल समस्या आती हैI  अत्याधुनिक फैक्टरिंग कार्यान्वयन  के समान तरीके से काम करते हैंI इस दृष्टिकोण में कारकों का उपयोग गुणांक की गणना करने के लिए नहीं किया जाता है बल्कि वैक्टर की गणना करने के लिए किया जाता हैi <math>r</math> {0,1} में प्रविष्टियाँ जो सबसेट को एनकोड करती हैंi
-Zassenhaus एल्गोरिथ्म इस प्रकार आगे बढ़ता है।सबसे पहले, एक प्राइम चुनें
-संख्या <math>p</math> ऐसी छवि <math>f(x)</math> आधुनिक <math>p</math>
-#वर्ग-मुक्त कारक रहता है | वर्ग-मुक्त, और उसी डिग्री के रूप में <math>f(x)</math>।
-तत्कालीन कारक <math>f(x)</math> आधुनिक <math>p</math>।यह पूर्णांक बहुपद का उत्पादन करता है <math>f_1(x),...,f_r(x)</math> जिसका उत्पाद मेल खाता है <math>f(x)</math> आधुनिक <math>p</math>।अगला, हेन्सेल के लेम्मा को लागू करें | हेन्सल उठाना;यह अपडेट करता है <math>f_i(x)</math> इस तरह से कि उनका उत्पाद मेल खाता है <math>f(x)</math> आधुनिक <math>p^a</math>,  कहाँ पे <math>a</math> काफी बड़ा है <math>p^a</math> से अधिक है <math>2B</math>: इस प्रकार प्रत्येक <math>f_i(x)</math> एक अच्छी तरह से परिभाषित पूर्णांक बहुपद के अनुरूप है।सापेक्ष <math>p^a</math>, बहुपद <math>f(x)</math> है <math>2^r</math> कारक (इकाइयों तक): सभी सबसेट के उत्पाद <math>{f_1(x),...,f_r(x)}</math> आधुनिक <math>p^a</math>।ये कारक मोडुलो <math>p^a</math> के सही कारकों के अनुरूप नहीं होना चाहिए <math>f(x)</math> में <math>\mathbb Z[x]</math>, लेकिन हम आसानी से उन्हें विभाजन में परीक्षण कर सकते हैं <math>\mathbb Z[x]</math>।इस तरह, सभी इरेड्यूसिबल सच्चे कारकों को सबसे अधिक जाँच करके पाया जा सकता है <math>2^r</math> मामले, कम हो गए <math>2^{r-1}</math> परिसर को छोड़कर मामले।यदि <math>f(x)</math> reducible है, मामलों की संख्या को हटाकर और कम हो जाता है <math>f_i(x)</math> जो पहले से ही पाया गया सच्चा कारक दिखाई देता है।Zassenhaus एल्गोरिथ्म प्रत्येक मामले (प्रत्येक सबसेट) को जल्दी से संसाधित करता है, हालांकि, सबसे खराब स्थिति में, यह मामलों की एक घातीय संख्या पर विचार करता है।
-तर्कसंगत बहुपदों को फैक्टरिंग के लिए पहला बहुपद समय एल्गोरिथ्म लेंस्ट्रा, लेंस्ट्रा और लवसेज़ द्वारा खोजा गया था और यह लेंस्ट्रा -लेंस्ट्रा -लोवाज़ जाली लेटिस बेसिस रिडक्शन एल्गोरिथ्म का एक अनुप्रयोग है। {{harv|Lenstra|Lenstra|Lovász|1982}}।
-एलएलएल फैक्टरकरण एल्गोरिथ्म का एक सरलीकृत संस्करण इस प्रकार है: बहुपद के एक जटिल (या पी-एडिक) रूट α की गणना करें <math>f(x)</math> उच्च परिशुद्धता के लिए, फिर 1, α, α के बीच एक अनुमानित रैखिक संबंध खोजने के लिए Lenstra -Lenstra -Lovász Lattice आधार कटौती एल्गोरिथ्म का उपयोग करें<sup>2 </sup>, ए<sup>3 </sup>,।।।पूर्णांक गुणांक के साथ, जो एक सटीक रैखिक संबंध और एक बहुपद कारक हो सकता है <math>f(x)</math>।कोई सटीकता के लिए एक बाध्य हो सकता है जो गारंटी देता है कि यह विधि या तो एक कारक, या एक ireducibility प्रमाण का उत्पादन करती है।यद्यपि यह विधि बहुपद समय में समाप्त होती है, लेकिन इसका उपयोग व्यवहार में नहीं किया जाता है क्योंकि जाली में उच्च आयाम और विशाल प्रविष्टियाँ होती हैं, जो गणना को धीमा कर देती है।
-Zassenhaus एल्गोरिथ्म में घातीय जटिलता एक कॉम्बिनेटरियल समस्या से आती है: कैसे सही सबसेट का चयन करें <math>f_1(x),...,f_r(x)</math>।अत्याधुनिक फैक्टरिंग कार्यान्वयन Zassenhaus के समान तरीके से काम करते हैं, सिवाय इसके कि कॉम्बिनेटरियल समस्या को एक जाली समस्या के लिए अनुवादित किया जाता है जो तब LLL द्वारा हल किया जाता है।<ref>M. van Hoeij: [https://www.math.fsu.edu/~hoeij/knapsack/paper/knapsack.pdf ''Factoring polynomials and the knapsack problem.''] Journal of Number Theory, 95, 167-189, (2002).</ref> इस दृष्टिकोण में, LLL का उपयोग कारकों के गुणांक की गणना करने के लिए नहीं किया जाता है, बल्कि वैक्टर की गणना करने के लिए किया जाता है <math>r</math> {0,1} में प्रविष्टियाँ जो सबसेट को एनकोड करती हैं <math>f_1(x),...,f_r(x)</math> Irreducible सच्चे कारकों के अनुरूप।
-[[Category:Articles with hatnote templates targeting a nonexistent page]]
-[[Category:Articles with short description]]
-[[Category:CS1]]
-[[Category:CS1 maint]]
-[[Category:Machine Translated Page]]
-[[Category:Pages with template loops]]
-[[Category:Short description with empty Wikidata description]]
-[[Category:Templates using TemplateData]]
-[[Category:Wikipedia pages with incorrect protection templates|Cite book/TemplateData]]
 === बीजगणितीय एक्सटेंशन (ट्रेजर की विधि) पर फैक्टरिंग ===
-हम एक बहुपद कारक कर सकते हैं <math>p(x) \in K[x] </math>, जहां क्षेत्र <math>K</math> का एक परिमित विस्तार है <math>\mathbb{Q}</math>।सबसे पहले, #वर्ग-मुक्त कारक का उपयोग करके | वर्ग-मुक्त कारक, हम मान सकते हैं कि बहुपद वर्ग-मुक्त है।आगे हम भागफल की अंगूठी को परिभाषित करते हैं <math>L= K[x]/p(x)</math> डिग्री का <math>n=[L:\mathbb{Q}] = \deg p(x)\, [K:\mathbb{Q}]</math>;यह एक क्षेत्र नहीं है जब तक <math>p(x)</math> IRreducible है, लेकिन यह एक कम अंगूठी है <math>p(x)</math> वर्ग-मुक्त है।वास्तव में, अगर <blockquote><math>p(x) = \prod_{i=1}^m p_i(x)</math></blockquote> p (x) का वांछित कारक है, रिंग विशिष्ट रूप से क्षेत्रों में विशिष्ट रूप से विघटित हो जाती है:
+बहुपद कारक  <math>p(x) \in K[x] </math>का कार्य कर सकते हैं जहां क्षेत्र <math>K</math> का एक परिमित विस्तार हैI सबसे पहले #वर्ग-मुक्त कारक का उपयोग करके वर्ग-मुक्त कर सकते हैंI हम मान सकते हैं कि बहुपद वर्ग-मुक्त हैI भागफल की अंगूठी को परिभाषित करते हैं <math>L= K[x]/p(x)</math> डिग्री का<math>n=[L:\mathbb{Q}] = \deg p(x)\, [K:\mathbb{Q}]</math>यह एक क्षेत्र नहीं है जब तक <math>p(x)</math> अपरिवर्तनीय हैI <blockquote><math>p(x) = \prod_{i=1}^m p_i(x)</math></blockquote> p (x) का वांछित कारक है रिंग विशिष्ट रूप से क्षेत्रों में विशिष्ट रूप से विघटित हो जाती हैI
 :<math>L = K[x]/p(x) \cong \prod_{i=1}^m K[x]/p_i(x).</math>
-हम कारक को जाने बिना इस अपघटन को पाएंगे।सबसे पहले, हम स्पष्ट रूप से एक बीजगणित के रूप में एल लिखते हैं <math>\mathbb{Q}</math>: हम एक यादृच्छिक तत्व चुनते हैं <math>\alpha \in L</math>, जो उत्पन्न करता है <math>L</math> ऊपर <math>\mathbb{Q}</math> आदिम तत्व प्रमेय द्वारा उच्च संभावना के साथ।यदि यह मामला है, तो हम न्यूनतम बहुपद की गणना कर सकते हैं <math>q(y)\in \mathbb{Q}[y]</math> का <math>\alpha</math> ऊपर <math>\mathbb{Q}</math>, एक खोजकर <math>\mathbb{Q}</math>1, ए, के बीच -लाइन संबंध।।।, एक<sup>n </sup>।तर्कसंगत पॉलीमियल के लिए एक फैक्टरिंग एल्गोरिथ्म का उपयोग करते हुए, हम irreducibles में कारक हैं <math>\mathbb{Q}[y]</math>:
+हम कारक को जाने बिना इस अपघटन को पाएंगे।सबसे पहले स्पष्ट रूप से एक बीजगणित के रूप में एल लिखते हैं I <math>\mathbb{Q}</math>एक यादृच्छिक तत्व चुनते हैं <math>\alpha \in L</math> जो  <math>L</math> ऊपर <math>\mathbb{Q}</math> आदिम तत्व प्रमेय द्वारा उच्च संभावना के साथ उत्पन्न करता है। न्यूनतम बहुपद <math>q(y)\in \mathbb{Q}[y]</math>  की गणना कर सकते हैं ।
 :<math>q(y) = \prod_{i=1}^{n} q_i(y).</math>
-इस प्रकार हमारे पास है:
+इस प्रकार हमारे पास है
 :<math>L \cong \mathbb{Q}[y]/q(y) \cong \prod_{i=1}^n \mathbb{Q}[y]/q_i(y),</math>
-कहाँ पे <math>\alpha</math> से मेल खाती है <math>y\leftrightarrow (y,y,\ldots,y)</math>।यह पिछले अपघटन के लिए आइसोमोर्फिक होना चाहिए <math>L</math>।
+<math>y\leftrightarrow (y,y,\ldots,y)</math> पिछले अपघटन के लिए <math>L</math>। आइसोमोर्फिक होना चाहिएI
+एल के जनरेटर के साथ x हैंI <math>K</math> ऊपर <math>\mathbb{Q}</math> इन्हें एक बहुपद के रूप में लिखना <math>\alpha</math>, एम्बेडिंग का निर्धारण कर सकते हैं <math>x</math> तथा <math>K</math> प्रत्येक घटक में <math>\mathbb{Q}[y]/q_i(y)=K[x]/p_i(x)</math>की न्यूनतम बहुपद का पता लगाकर <math>x</math> में <math>\mathbb{Q}[y]/q_i(y)</math>, <math>p_i(x)</math> और इस प्रकार कारक <math>p(x)</math> ऊपर <math>K.</math>की गणना करते हैं I
-एल के जनरेटर के जनरेटर के साथ x हैं <math>K</math> ऊपर <math>\mathbb{Q}</math>;इन्हें एक बहुपद के रूप में लिखना <math>\alpha</math>, हम एम्बेडिंग का निर्धारण कर सकते हैं <math>x</math> तथा <math>K</math> प्रत्येक घटक में <math>\mathbb{Q}[y]/q_i(y)=K[x]/p_i(x)</math>।की न्यूनतम बहुपद का पता लगाकर <math>x</math> में <math>\mathbb{Q}[y]/q_i(y)</math>, हम गणना करते हैं <math>p_i(x)</math>, और इस प्रकार कारक <math>p(x)</math> ऊपर <math>K.</math>
-[[Category:Articles with hatnote templates targeting a nonexistent page]]
-[[Category:Articles with short description]]
-[[Category:CS1]]
-[[Category:CS1 maint]]
-[[Category:Machine Translated Page]]
-[[Category:Pages with template loops]]
-[[Category:Short description with empty Wikidata description]]
-[[Category:Templates using TemplateData]]
-[[Category:Wikipedia pages with incorrect protection templates|Cite book/TemplateData]]
-[[Category:कंप्यूटर बीजगणित]]
 == यह भी देखें ==
@@ Line 209: / Line 197: @@
 {{Polynomials}}
-[[Category: बहुपद]]
-[[Category: कंप्यूटर बीजगणित]]
-[[Category: कारक]]]
-[[Category: बहुपद कारक एल्गोरिदम]]]
-[[Category: Machine Translated Page]]
+]
+]
+[[Category:Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:Articles with short description]]
+[[Category:CS1]]
+[[Category:CS1 maint]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with template loops]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia pages with incorrect protection templates|Cite book/TemplateData]]
+[[Category:कंप्यूटर बीजगणित]]
+[[Category:कारक]]
+[[Category:बहुपद]]
+[[Category:बहुपद कारक एल्गोरिदम]]

v t e बहुपद और बहुपद कार्य
डिग्री	शून्य बहुपद (डिग्री अपरिभाषित या −1 या and) निरंतर कार्य (0) रैखिक फ़ंक्शन (1) रेखीय समीकरण द्विघात कार्य (2) द्विघात समीकरण क्यूबिक फंक्शन (3) घन समीकरण चतुर्थक कार्य (4) चतुर्थक समीकरण क्विंटिक फंक्शन (5) सेक्स्टिक समीकरण (6) सेप्टिक समीकरण (7)
गुणों से	Univariate bivariate बहुभिन्नरूपी मोनोमियल बिनोमियल ट्रिनोमियल irreducible वर्ग-मुक्त सजातीय quasi-homogenous
औजार और एल्गोरिदम	कारक सबसे बड़ा आम भाजक डिवीजन हॉर्नर की मूल्यांकन की विधि परिणामी भेदभावपूर्ण Gröbner आधार

Anonymous

Search

बहुपद का गुणनखंडन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 17:29, 24 August 2023

Contents

प्रश्न का निर्माण

आदिम भाग -कंटेंट फैक्टरकरण

वर्ग-मुक्त कारक