बहुपद का गुणनखंडन

This article is about factorization algorithms. For paper-and-pencil methods, see Factorization § Polynomials.

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

पहला बहुपद कारक एल्गोरिथ्म थियोडोर वॉन शुबर्ट द्वारा 1793 में प्रकाशित किया गया था। लियोपोल्ड क्रोनकर ने 1882 में शूबर्ट के एल्गोरिथ्म को फिर से खोजा और इसे एक बीजगणितीय विस्तार में बहुभिन्नरूपी बहुपद और गुणांक तक बढ़ाया।लेकिन इस विषय पर अधिकांश ज्ञान 1965 और पहले कंप्यूटर बीजगणित प्रणालियों से अधिक पुराना नहीं है:

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

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

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

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

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

बहुपद कारक का प्रश्न केवल एक कम्प्यूटेबल फ़ील्ड में गुणांक के लिए समझ में आता है, जिसका प्रत्येक तत्व कंप्यूटर में दर्शाया जा सकता है और जिसके लिए अंकगणित संचालन के लिए एल्गोरिदम हैं। हालांकि, यह एक पर्याप्त स्थिति नहीं है: फ्रॉहलिच और शेफर्डसन ऐसे क्षेत्रों का उदाहरण देते हैं जिनके लिए कोई कारक एल्गोरिथ्म मौजूद नहीं हो सकता है। गुणांक के क्षेत्र जिनके लिए कारक एल्गोरिदम के लिए जाना जाता है, उनमें प्राइम फ़ील्ड (यानी, तर्कसंगत और प्राइम मॉड्यूलर अंकगणित का क्षेत्र) और उनके बारीक रूप से उत्पन्न क्षेत्र एक्सटेंशन शामिल हैं। पूर्णांक गुणांक भी ट्रैक्टेबल हैं। क्रोनकर की शास्त्रीय विधि केवल एक ऐतिहासिक दृष्टिकोण से दिलचस्प है; आधुनिक एल्गोरिदम एक उत्तराधिकार द्वारा आगे बढ़ते हैं:

• वर्ग मुक्त कारक
• परिमित क्षेत्रों पर कारक

और कटौती:

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

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

See also: Content (algebra) and Gauss's lemma (polynomial)

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

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

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

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

सामग्री और आदिम भाग में एक कारक है।

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

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

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

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

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

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

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

सामग्री और आदिम भाग में एक कारक है।

गॉस ने साबित किया कि दो आदिम बहुपदों का उत्पाद भी आदिम है (गॉस का लेम्मा (बहुपद) | गॉस लेम्मा)। इसका तात्पर्य यह है कि एक आदिम बहुपद तर्कसंगत लोगों पर अतार्क्य है यदि और केवल अगर यह पूर्णांक पर अतार्क्य है। इसका तात्पर्य यह भी है कि तर्कसंगत गुणांक के साथ एक बहुपद के तर्कसंगतताओं पर कारक अपने आदिम भाग के पूर्णांक पर कारक के समान है। इसी तरह, पूर्णांक गुणांक के साथ एक बहुपद के पूर्णांक पर कारक इसकी सामग्री के कारक द्वारा इसके आदिम भाग के कारक का उत्पाद है।

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

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

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

Main article: Square-free polynomial

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

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

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

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

शास्त्रीय तरीके

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

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

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

तर्कसंगत गुणांक के साथ सभी रैखिक कारकों को तर्कसंगत रूट परीक्षण का उपयोग करके पाया जा सकता है।यदि बहुपद को फैक्टर किया जाता है $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}$।पूर्णांक कारकों के सभी संभावित संयोजनों को वैधता के लिए परीक्षण किया जा सकता है, और प्रत्येक वैध को बहुपद लंबे विभाजन का उपयोग करके बाहर किया जा सकता है।यदि मूल बहुपद कारकों का उत्पाद है, जिनमें से कम से कम दो डिग्री 2 या उच्चतर हैं, तो यह तकनीक केवल एक आंशिक कारक प्रदान करती है;अन्यथा कारक पूरा हो गया है।विशेष रूप से, यदि वास्तव में एक गैर-रैखिक कारक है, तो यह सभी रैखिक कारकों के बाद छोड़ दिया गया बहुपद होगा।एक क्यूबिक बहुपद के मामले में, यदि क्यूबिक बिल्कुल भी कारक है, तो तर्कसंगत रूट परीक्षण एक पूर्ण कारक देता है, या तो एक रैखिक कारक और एक ireducible द्विघात कारक में, या तीन रैखिक कारकों में।

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

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

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

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

$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 केवल कारक के रूप में हो सकता है

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

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

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

और इसी तरह पी (1) के लिए।6 के आठ कारक हैं (1 × 6 और 2 × 3 के लिए चार प्रत्येक), कुल 4 × 4 × 8 = 128 संभावित ट्रिपल्स (पी (0), पी (1), पी () 1)),जिनमें से आधे को दूसरे आधे की नकारात्मक के रूप में छोड़ दिया जा सकता है।इस प्रकार, हमें 64 स्पष्ट पूर्णांक बहुपद की जांच करनी चाहिए $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)$। अब कोई पी (एक्स) और क्यू (एक्स) के कारकों को खोजने के लिए पुनरावर्ती परीक्षण कर सकता है, इस मामले में तर्कसंगत रूट परीक्षण का उपयोग करके।यह पता चला है कि वे दोनों अतार्किक हैं, इसलिए f (x) का अतार्किक कारक है:

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

आधुनिक तरीके

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

Main articles: Factorization of polynomials over finite fields, Berlekamp's algorithm, and Cantor–Zassenhaus algorithm

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

1. primitive part-content फैक्टराइजेशन होने के लिए | सामग्री-मुक्त

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

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

1. वर्ग-मुक्त कारक रहता है | वर्ग-मुक्त, और उसी डिग्री के रूप में $f(x)$।

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

तर्कसंगत बहुपदों को फैक्टरिंग के लिए पहला बहुपद समय एल्गोरिथ्म लेंस्ट्रा, लेंस्ट्रा और लवसेज़ द्वारा खोजा गया था और यह लेंस्ट्रा -लेंस्ट्रा -लोवाज़ जाली लेटिस बेसिस रिडक्शन एल्गोरिथ्म का एक अनुप्रयोग है। (Lenstra, Lenstra & Lovász 1982)। एलएलएल फैक्टरकरण एल्गोरिथ्म का एक सरलीकृत संस्करण इस प्रकार है: बहुपद के एक जटिल (या पी-एडिक) रूट α की गणना करें $f(x)$ उच्च परिशुद्धता के लिए, फिर 1, α, α के बीच एक अनुमानित रैखिक संबंध खोजने के लिए Lenstra -Lenstra -Lovász Lattice आधार कटौती एल्गोरिथ्म का उपयोग करें² , ए³ ,।।।पूर्णांक गुणांक के साथ, जो एक सटीक रैखिक संबंध और एक बहुपद कारक हो सकता है $f(x)$।कोई सटीकता के लिए एक बाध्य हो सकता है जो गारंटी देता है कि यह विधि या तो एक कारक, या एक ireducibility प्रमाण का उत्पादन करती है।यद्यपि यह विधि बहुपद समय में समाप्त होती है, लेकिन इसका उपयोग व्यवहार में नहीं किया जाता है क्योंकि जाली में उच्च आयाम और विशाल प्रविष्टियाँ होती हैं, जो गणना को धीमा कर देती है।

Zassenhaus एल्गोरिथ्म में घातीय जटिलता एक कॉम्बिनेटरियल समस्या से आती है: कैसे सही सबसेट का चयन करें $f_{1}(x),...,f_{r}(x)$।अत्याधुनिक फैक्टरिंग कार्यान्वयन Zassenhaus के समान तरीके से काम करते हैं, सिवाय इसके कि कॉम्बिनेटरियल समस्या को एक जाली समस्या के लिए अनुवादित किया जाता है जो तब LLL द्वारा हल किया जाता है। इस दृष्टिकोण में, LLL का उपयोग कारकों के गुणांक की गणना करने के लिए नहीं किया जाता है, बल्कि वैक्टर की गणना करने के लिए किया जाता है $r$ {0,1} में प्रविष्टियाँ जो सबसेट को एनकोड करती हैं $f_{1}(x),...,f_{r}(x)$ Irreducible सच्चे कारकों के अनुरूप।

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

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

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

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

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

हम कारक को जाने बिना इस अपघटन को पाएंगे।सबसे पहले, हम स्पष्ट रूप से एक बीजगणित के रूप में एल लिखते हैं $\mathbb {Q}$: हम एक यादृच्छिक तत्व चुनते हैं $\alpha \in L$, जो उत्पन्न करता है $L$ ऊपर $\mathbb {Q}$ आदिम तत्व प्रमेय द्वारा उच्च संभावना के साथ।यदि यह मामला है, तो हम न्यूनतम बहुपद की गणना कर सकते हैं $q(y)\in \mathbb {Q} [y]$ का $\alpha$ ऊपर $\mathbb {Q}$, एक खोजकर $\mathbb {Q}$1, ए, के बीच -लाइन संबंध।।।, एकⁿ ।तर्कसंगत पॉलीमियल के लिए एक फैक्टरिंग एल्गोरिथ्म का उपयोग करते हुए, हम irreducibles में कारक हैं $\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),$

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

एल के जनरेटर के जनरेटर के साथ x हैं $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.$

यह भी देखें

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

ग्रन्थसूची

• 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

]]