विस्तारित यूक्लिडियन एल्गोरिथ्म

अंकगणित और कंप्यूटर प्रोग्रामिंग में, विस्तारित यूक्लिडियन एल्गोरिथ्म का एक विस्तार है, और पूर्णांक a और b के सबसे बड़े सामान्य भाजक (gcd) के अतिरिक्त, बेज़ाउट के गुणांकों की भी गणना करता है। सर्वसमिका, जो कि पूर्णांक 'x' और 'y' हैं

$ax+by=\gcd(a,b).$

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

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

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

विवरण

मानक यूक्लिडियन एल्गोरिथ्म यूक्लिडियन विभाजनों के उत्तराधिकार से आगे बढ़ता है जिनके भागफल का उपयोग नहीं किया जाता है। अवशेष ही रखे जाते हैं। विस्तारित एल्गोरिथम के लिए, लगातार भागफल का उपयोग किया जाता है। अधिक सटीक रूप से, इनपुट के रूप में ए और बी के साथ मानक यूक्लिडियन एल्गोरिथ्म में एक अनुक्रम की गणना होती है $q_{1},\ldots ,q_{k}$ भागफल और एक क्रम $r_{0},\ldots ,r_{k+1}$ शेषफल कि तरह हैं.

${\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\quad {\text{and}}\quad 0\leq r_{i+1}<|r_{i}|\quad {\text{(this defines }}q_{i})\\&\,\,\,\vdots \end{aligned}}$

यूक्लिडियन विभाजन की यह मुख्य संपत्ति है कि दाईं ओर की असमानताएँ विशिष्ट रूप से परिभाषित होती हैं $q_{i}$ और $r_{i+1}$ से $r_{i-1}$ और $r_{i}.$ जब कोई शेषफल तक पहुँचता है तो गणना बंद हो जाती है $r_{k+1}$ जो शून्य है; सबसे बड़ा सामान्य विभाजक तब होता है जब अंतिम गैर शून्य शेष हो $r_{k}.$ विस्तारित यूक्लिडियन एल्गोरिथ्म समान रूप से आगे बढ़ता है, परंतु निम्नानुसार दो अन्य अनुक्रम को जोड़ता है.

${\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\text{and }}0&\leq r_{i+1}<|r_{i}|&{\text{(this defines }}q_{i}{\text{)}}\\s_{i+1}&=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\,\vdots \end{aligned}}$

गणना कब समाप्त होती है $r_{k+1}=0$

• $r_{k}$ इनपुट का महत्तम समापवर्तक है $a=r_{0}$ और $b=r_{1}.$
• बेज़ाउट गुणांक हैं $s_{k}$ $t_{k},$ $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$
• a और b के भागफल उनके महत्तम समापवर्तक द्वारा दिए गए हैं $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ और $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$

इसके अतिरिक्त, यदि ए और बी दोनों सकारात्मक हैं $\gcd(a,b)\neq \min(a,b)$,

$|s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}}\right\rfloor \quad {\text{and}}\quad |t_{i}|\leq \left\lfloor {\frac {a}{2\gcd(a,b)}}\right\rfloor$

$0\leq i\leq k,$ $\lfloor x\rfloor$ के अभिन्न अंग को दर्शाता है, जो कि x से अधिक नहीं सबसे बड़ा पूर्णांक है।

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

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

उदाहरण

निम्न तालिका दिखाती है कि विस्तारित यूक्लिडियन एल्गोरिथम इनपुट 240 और 46. के साथ कैसे आगे बढ़ता है। सबसे बड़ा सामान्य विभाजक अंतिम गैर शून्य प्रविष्टि है, 2 कॉलम शेष में। गणना पंक्ति 6 ​​पर रुक जाती है, चूंकि इसमें शेष है 0. बेज़ाउट गुणांक दूसरी-से-अंतिम पंक्ति की अंतिम दो प्रविष्टियों में दिखाई देते हैं। वास्तव में, इसे सत्यापित करना आसान है −9 × 240 + 47 × 46 = 2. अंत में अंतिम दो प्रविष्टियाँ 23 और {{nowrap|−120} चिह्न तक, इनपुट 46 और 240 के भागफल हैं। सबसे बड़ा सामान्य भाजक 2 है।

index i	quotient qi−1	Remainder ri	si	ti
0		240	1	0
1		46	0	1
2	240 ÷ 46 = 5	240 − 5 × 46 = 10	1 − 5 × 0 = 1	0 − 5 × 1 = −5
3	46 ÷ 10 = 4	46 − 4 × 10 = 6	0 − 4 × 1 = −4	1 − 4 × −5 = 21
4	10 ÷ 6 = 1	10 − 1 × 6 = 4	1 − 1 × −4 = 5	−5 − 1 × 21 = −26
5	6 ÷ 4 = 1	6 − 1 × 4 = 2	−4 − 1 × 5 = −9	21 − 1 × −26 = 47
6	4 ÷ 2 = 2	4 − 2 × 2 = 0	5 − 2 × −9 = 23	−26 − 2 × 47 = −120

प्रमाण

जैसे $0\leq r_{i+1}<|r_{i}|,$ गैर-ऋणात्मक पूर्णांकों का घटता क्रम है (i = 2 )। इस प्रकार यह कुछ हद तक सूक्ष्म होना चाहिए $r_{k+1}=0.$ यह साबित करता है कि एल्गोरिदम अंततः सूक्ष्म हो जाता है।

जैसे $r_{i+1}=r_{i-1}-r_{i}q_{i},$ महत्तम समापवर्तक समान है $(r_{i-1},r_{i})$ और $(r_{i},r_{i+1}).$ यह दर्शाता है कि इनपुट का महत्तम समापवर्तक $a=r_{0},b=r_{1}$ के समान है $r_{k},r_{k+1}=0.$ इससे यह सिद्ध होता है $r_{k}$ a और b का महत्तम समापवर्तक है। (इस बिंदु तक, प्रमाण शास्त्रीय यूक्लिडियन एल्गोरिथम के समान है।)

जैसे $a=r_{0}$ और $b=r_{1},$ हमारे पास है $as_{i}+bt_{i}=r_{i}$ i = 0 और 1 के लिए। संबंध सभी के लिए प्रेरण द्वारा अनुसरण करता है $i>1$:

$r_{i+1}=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{i})q_{i}=(as_{i-1}-as_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1}+bt_{i+1}.$

इस प्रकार $s_{k}$ और $t_{k}$ बेज़ाउट गुणांक हैं।

मैट्रिक्स पर विचार करें

$A_{i}={\begin{pmatrix}s_{i-1}&s_{i}\\t_{i-1}&t_{i}\end{pmatrix}}.$

पुनरावृत्ति संबंध को मैट्रिक्स रूप में पुनः लिखा जा सकता है

$A_{i+1}=A_{i}\cdot {\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix}}.$

गणित में मैट्रिक्स का निर्धारक $A_{1}$ है। पूर्ववर्ती सूत्र में सबसे सही मैट्रिक्स का निर्धारक -1 है। यह इस प्रकार है $A_{i}$$(-1)^{i-1}.$, $i=k+1,$ $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ इसे बेजाउट की पहचान के रूप में देखने से यह पता चलता है कि $s_{k+1}$, $t_{k+1}$ यह सह अभाज्य हैं। $as_{k+1}+bt_{k+1}=0$ यह ऊपर सिद्ध हो चुका है और यूक्लिड की प्रमेयिका (लेम्मा) यह दर्शाती है कि वह $s_{k+1}$ b, को विभाजित करता है, $b=ds_{k+1}$ कुछ पूर्णांक के लिए d. द्वारा विभाजित करना $s_{k+1}$ संबंध $as_{k+1}+bt_{k+1}=0$ देता है $a=-dt_{k+1}.$ इसलिए, $s_{k+1}$ और $-t_{k+1}$ कोप्राइम पूर्णांक हैं जो कि के भागफल हैं a और b एक सामान्य कारक द्वारा, जो इस प्रकार उनका सबसे बड़ा सामान्य विभाजक या इसका योगात्मक व्युत्क्रम है।

अंतिम अभिकथन को सिद्ध करने के लिए, a और b दोनों धनात्मक हैं $\gcd(a,b)\neq \min(a,b)$., $a\neq b$, $a<b$, यह देखा जा सकता है कि EEA के तहत (a,b) के लिए s और t क्रम प्रारंभिक 0s और 1s तक, (b,a) के लिए t और s क्रम हैं। परिभाषाएँ तब दिखती हैं जब (ए, बी) स्थिति (बी, ए) स्थिति से कम हो जाती है। तो मान लीजिए $a>b$ सामान्यता क्षति के अतिरिक्त होती है।

यह देखा जा सकता है $s_{2}$ 1 $s_{3}$ (जो इसके द्वारा उपस्थित है $\gcd(a,b)\neq \min(a,b)$) एक ऋणात्मक पूर्णांक है। तत्पश्चात, द साइन इन $s_{i}$ संकेत में वैकल्पिक और सही से परिमाण में वृद्धि, जो परिभाषाओं और तथ्य से आगमनात्मक रूप से अनुसरण करती है $q_{i}\geq 1$ के लिए $1\leq i\leq k$, स्थिति $i=1$ रखता है क्योंकि $a>b$. के लिए भी यही सच है $t_{i}$ पहली कुछ शर्तों के बाद, उसी कारण से। इसके अतिरिक्त, यह देखना आसान है $q_{k}\geq 2$ (जब ए और बी दोनों सकारात्मक हो $\gcd(a,b)\neq \min(a,b)$). इस प्रकार से ,

$|s_{k+1}|=\left|{\frac {b}{\gcd(a,b)}}\right|\geq 2|s_{k}|\qquad {\text{and}}\qquad |t_{k+1}|=\left|{\frac {a}{\gcd(a,b)}}\right|\geq 2|t_{k}|.$

यह इस तथ्य के साथ है कि $s_{k},t_{k}$ किसी भी पिछले की तुलना में निरपेक्ष मान से बड़े या बराबर हैं $s_{i}$ या $t_{i}$ क्रमशः।

बहुपद विस्तारित यूक्लिडियन एल्गोरिथम

See also: बहुपद महानतम सामान्य विभाजक §  बेज़ाउट की पहचान और विस्तारित GCD एल्गोरिथम

एक क्षेत्र (गणित) में गुणांक वाले अविभाजित बहुपदों के लिए, सब कुछ समान रूप से काम करता है, यूक्लिडियन डिवीजन, बेज़ाउट की पहचान और विस्तारित यूक्लिडियन एल्गोरिथ्म। पहला अंतर यह है कि, यूक्लिडियन डिवीजन और एल्गोरिथम में, असमानता $0\leq r_{i+1}<|r_{i}|$ डिग्री पर असमानता द्वारा प्रतिस्थापित किया जाना है $\deg r_{i+1}<\deg r_{i}.$ अन्यथा, इस आलेख में जो कुछ भी पहले आता है वह वही रहता है, केवल बहुपदों द्वारा पूर्णांकों को प्रतिस्थापित करके।

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

यदि a और b दो शून्येतर बहुपद हैं, तो विस्तारित यूक्लिडियन एल्गोरिथम बहुपदों (s, t) का ऐसा अद्वितीय युग्म उत्पन्न करता है

$as+bt=\gcd(a,b)$

और

$\deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).$

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

गणित में, यह आवश्यक है कि सबसे बड़ा सामान्य विभाजक एक मोनिक बहुपद हो। इसे प्राप्त करने के लिए, आउटपुट के प्रत्येक तत्व को प्रमुख गुणांक द्वारा विभाजित करना पर्याप्त है $r_{k}.$ यह अनुमति देता है कि, यदि a और b सहअभाज्य हैं, तो किसी को बेज़ाउट की असमानता के दाहिने हाथ की ओर 1 मिलता है। अन्यथा, कोई भी अशून्य स्थिरांक प्राप्त हो सकता है। कंप्यूटर बीजगणित में, बहुपदों में सामान्यतः पूर्णांक गुणांक होते हैं, और सबसे बड़े सामान्य विभाजक को सामान्य करने का यह नियम सुविधाजनक होने के लिए बहुत अधिक अंशों का परिचय देता है।

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

एक तीसरे दृष्टिकोण में एक तरह से # उपपरिणामी छद्म-शेष अनुक्रमों के एल्गोरिथम का विस्तार करना सम्मलित है। जो यूक्लिडियन एल्गोरिथम विस्तारित के समान है। यह अनुमति देता है कि पूर्णांक गुणांक वाले बहुपदों से प्रारंभ करते समय, गणना किए गए सभी बहुपदों में पूर्णांक गुणांक होते हैं। इसके अतिरिक्त, प्रत्येक गणना शेष $r_{i}$ एक उपपरिणामी बहुपद है। विशेष रूप से, यदि इनपुट बहुपद सह अभाज्य हैं, तो बेज़ाउट की पहचान बन जाती है

$as+bt=\operatorname {Res} (a,b),$

जहाँ $\operatorname {Res} (a,b)$ ए और बी के परिणाम को दर्शाता है। बेज़ाउट की पहचान के इस रूप में सूत्र में कोई भाजक नहीं है। यदि कोई परिणामी द्वारा सब कुछ विभाजित करता है तो उसमें दिखाई देने वाली परिमेय संख्याओं के लिए एक स्पष्ट साधारण भाजक के साथ शास्त्रीय बेज़ाउट की पहचान मिलती है।

स्यूडोकोड

इस खंड और निम्नलिखित में, div एक सहायक कार्य है जो अपने बाएं तर्क के यूक्लिडियन डिवीजन के भागफल की गणना अपने सही तर्क से करता है।

ऊपर वर्णित एल्गोरिथ्म को प्रयुक्त करने के लिए, पहले यह टिप्पणी करनी चाहिए कि प्रत्येक चरण में अनुक्रमित चर के केवल दो अंतिम मान आवश्यक हैं। इस प्रकार, स्मृति को बचाने के लिए, प्रत्येक अनुक्रमित चर को एकमात्र दो चरों द्वारा प्रतिस्थापित किया जाना चाहिए।

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

(पुरानी_आर, आर) := (आर, पुरानी_आर - भागफल * आर)

के बराबर है

साबित: = आर;
r := old_r - भागफल × सिद्ध;
Old_r := सिद्ध;

और इसी तरह अन्य समांतर कार्यों के लिए। यह निम्न कोड की ओर जाता है:

फ़ंक्शन विस्तारित_जीसीडी (ए, बी)
    (ओल्ड_आर, आर) := (ए, बी)
    (पुराना_एस, एस) := (1, 0)
    (पुराना_टी, टी) := (0, 1)
    
    जबकि आर ≠ 0 करते हैं
        भागफल := old_r div r
        (old_r, r) := (r, old_r - भागफल × r)
        (old_s, s) := (s, old_s - भागफल × s)
        (old_t, t) := (t, old_t − भागफल × t)
    
    आउटपुट बेज़ाउट गुणांक: , (old_s, old_t)
    आउटपुट सबसे बड़ा सामान्य विभाजक: , old_r
    जीसीडी द्वारा आउटपुट भागफल: , (टी, एस)

a और b के भागफल उनके सबसे बड़े सामान्य विभाजक, जो आउटपुट है, उन में गलत चिह्न हो सकते है। गणना के अंत में इसे सही करना आसान है परंतु कोड को सरल बनाने के लिए यहां नहीं किया गया है। इसी तरह, यदि a या b शून्य है और दूसरा ऋणात्मक है, तो सबसे बड़ा सामान्य विभाजक जो आउटपुट है, ऋणात्मक है, और आउटपुट के सभी चिह्नों को बदलना होगा।

$ax+by=\gcd(a,b)$ बेज़ाउट को कोई भी हल कर सकता हैं $y$ दिया गया $a,b,x,\gcd(a,b)$. इस प्रकार, उपरोक्त एल्गोरिथम का अनुकूलन केवल गणना करना है $s_{k}$ अनुक्रम (जो बेज़ाउट गुणांक उत्पन्न करता है) :

फ़ंक्शन विस्तारित_जीसीडी (ए, बी)
    एस: = 0; ओल्ड_एस: = 1
    आर := बी; ओल्ड_आर: = ए
         
    जबकि आर ≠ 0 करते हैं
        भागफल := old_r div r
        (old_r, r) := (r, old_r - भागफल × r)
        (old_s, s) := (s, old_s - भागफल × s)
    
    अगर बी ≠ 0 तो
        bezout_t := (old_r − old_s × a) div b
    अन्य
        बेज़ाउट_टी: = 0
    
    आउटपुट बेज़ाउट गुणांक: , (old_s, bezout_t)
    आउटपुट सबसे बड़ा सामान्य विभाजक: , old_r

चूंकि, कई स्थितियों में यह वास्तव में एक अनुकूलन नहीं है: जबकि मशीन पूर्णांकों (अर्थात, अंकों की एक निश्चित ऊपरी सीमा के साथ पूर्णांक) के साथ उपयोग किए जाने पर पूर्व एल्गोरिथ्म अतिप्रवाह के लिए अतिसंवेदनशील नहीं होता है, old_s * a का गुणन अतिप्रवाह कर सकता है, इस अनुकूलन को इनपुट तक सीमित कर सकता है जिसे आधे से कम अधिकतम आकार में प्रदर्शित किया जा सकता है। असीमित आकार के पूर्णांकों का उपयोग करते समय, गुणन और विभाजन के लिए आवश्यक समय पूर्णांकों के आकार के साथ द्विघात रूप से बढ़ता है। इसका तात्पर्य यह है कि अनुकूलन एक गुणन/विभाजन द्वारा छोटे पूर्णांकों के गुणन/विभाजनों के अनुक्रम को प्रतिस्थापित करता है, जिसके लिए एक साथ लिए गए संचालन की तुलना में अधिक कंप्यूटिंग समय की आवश्यकता होती है।

अंशों का सरलीकरण

एक अंश a/b विहित सरलीकृत रूप में है यदि a और b सहअभाज्य हैं और b धनात्मक है। यह प्रामाणिक सरलीकृत रूप पूर्ववर्ती छद्म कोड की तीन आउटपुट लाइनों को बदलकर प्राप्त किया जा सकता है

अगर s = 0 फिर आउटपुट विभाजन शून्य से
अगर s < 0 तब s := −s;  t := −t (नकारात्मक हर से बचने के लिए)
'अगर' s = 1 फिर आउटपुट -t (1 के बराबर हर से बचने के लिए)
'आउटपुट' -t/s

इस एल्गोरिथ्म का प्रमाण इस तथ्य पर निर्भर करता है कि s और t दो सहअभाज्य पूर्णांक हैं जैसे कि as + bt = 0, और इस तरह ${\frac {a}{b}}=-{\frac {t}{s}}$. प्रामाणिक सरलीकृत रूप प्राप्त करने के लिए, यह सकारात्मक भाजक होने के लिए ऋण चिह्न को स्थानांतरित करने के लिए पर्याप्त है।

यदि b विभाजित समान रूप से, एल्गोरिदम केवल एक पुनरावृत्ति निष्पादित करता है, और हमारे पास एल्गोरिथम के अंत में s = 1 है। यह एकमात्र स्थिति है जहां आउटपुट पूर्णांक है।

मॉड्यूलर संरचनाओं में गुणक व्युत्क्रम की गणना

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

मॉड्यूलर पूर्णांक

Main article: मॉड्यूलर अंकगणित

अगर n एक धनात्मक पूर्णांक है, तो वलय Z/nZ सेट से पहचाना जा सकता है {0, 1, ..., n-1} के साथ यूक्लिडियन विभाजन के अवशेष n, द्वारा की जा सकती है, योग और गुणन में शेष को सम्मलित किया जा सकता है योग और पूर्णांकों के गुणन के परिणाम के n द्वारा। Z/nZ के एक अवयव का गुणात्मक व्युत्क्रम होता है (अर्थात, यह एक इकाई (रिंग थ्योरी) है) यदि यह n के लिए सहअभाज्य संख्या है। विशेष रूप से, यदि n अभाज्य है, तो a का गुणक व्युत्क्रम होता है यदि यह शून्य नहीं है (सापेक्ष n). इस प्रकार Z/nZ एक क्षेत्र है यदि और एकमात्र n अभाज्य है।

बेज़ाउट की पहचान इस बात पर महत्व देती है कि a और n सहअभाज्य हैं यदि और एकमात्र पूर्णांक s और t उपस्थित है

$ns+at=1$

n मॉड्यूल को कम कर देता है

$at\equiv 1\mod n.$

इस प्रकार t, या, अधिक सटीक रूप से, t द्वारा n के विभाजन का शेष, एक मॉड्यूलो n का गुणात्मक व्युत्क्रम है।

इस समस्या के लिए विस्तारित यूक्लिडियन एल्गोरिथम को अनुकूलित करने के लिए, किसी को यह टिप्पणी करनी चाहिए कि n के बेज़ाउट गुणांक की आवश्यकता नहीं है, और इस प्रकार गणना करने की आवश्यकता नहीं है। साथ ही, सकारात्मक और n से कम परिणाम प्राप्त करने के लिए, कोई इस तथ्य का उपयोग कर सकता है कि एल्गोरिथम द्वारा प्रदान किया गया पूर्णांक t संतुष्ट करता है |t| < n. अर्थात्, यदि t < 0, है तो अंत में इसमें n जोड़ना चाहिए। इसका परिणाम स्यूडोकोड में होता है, जिसमें इनपुट n 1 से बड़ा पूर्णांक होता है।

'फ़ंक्शन' उलटा (ए, एन)
    टी : = 0; न्यूट: = 1
    आर := एन; नया := अ

    'जबकि' newr ≠ 0 'करो'
        भागफल := r 'div' newr
        (t, newt) := (newt, t − भागफल × newt)
        (आर, नया) := (नया, आर - भागफल × नया)

    'अगर' आर> 1 'फिर'
        'वापसी' उलटा नहीं है
    'अगर' टी <0 'फिर'
        टी := टी + एन

    'वापसी' टी

सरल बीजगणितीय क्षेत्र विस्तार

विस्तारित यूक्लिडियन एल्गोरिथ्म भी सरल विस्तार में गुणात्मक व्युत्क्रमों की गणना के लिए मुख्य उपकरण है। क्रिप्टोग्राफी और कोडिंग सिद्धांत में व्यापक रूप से उपयोग किया जाने वाला एक महत्वपूर्ण मामला गैर-प्रमुख क्रम के परिमित क्षेत्रों का है। वास्तव में, अगर p एक प्रमुख संख्या है, और q = p^d, व्यवस्था का क्षेत्र q के प्रमुख क्षेत्र का एक सरल बीजगणितीय विस्तार है p तत्व, डिग्री के एक अलघुकरणीय बहुपद की जड़ से उत्पन्न d.

एक साधारण बीजगणितीय विस्तार L एक मैदान का K, एक अलघुकरणीय बहुपद की जड़ से उत्पन्न p डिग्री का d भागफल वलय से पहचाना जा सकता है $K[X]/\langle p\rangle ,$, और इसके तत्व बायेजिव में डिग्री से कम के बहुपदों के साथ हैं d. में जोड़ L बहुपदों का योग है। में गुणन L द्वारा बहुपदों के यूक्लिडियन विभाजन का शेषफल है p बहुपदों के उत्पाद का। इस प्रकार, अंकगणित को पूरा करने के लिए L, यह केवल यह परिभाषित करने के लिए रहता है कि गुणात्मक व्युत्क्रमों की गणना कैसे की जाए। यह विस्तारित यूक्लिडियन एल्गोरिथम द्वारा किया जाता है।

मॉड्यूलर गुणात्मक व्युत्क्रम की गणना के लिए ऊपर दिए गए एल्गोरिदम के समान ही है। दो मुख्य अंतर हैं: सबसे पहले अंतिम लेकिन एक पंक्ति की आवश्यकता नहीं है, क्योंकि जो बेज़ाउट गुणांक प्रदान किया जाता है वह हमेशा एक डिग्री से कम होता है d. दूसरे, सबसे बड़ा सामान्य विभाजक जो प्रदान किया जाता है, जब इनपुट बहुपद सहअभाज्य होते हैं, तो कोई गैर शून्य तत्व हो सकता है K; इस बेज़ाउट गुणांक (आम तौर पर सकारात्मक डिग्री का एक बहुपद) को इस तत्व के व्युत्क्रम से गुणा किया जाना है K. निम्नलिखित स्यूडोकोड में, p एक से अधिक डिग्री का बहुपद है, और a एक बहुपद है।

समारोह उलटा (ए, पी)
    टी : = 0; न्यूट: = 1
    आर := पी; नया := अ

    जबकि newr ≠ 0 करते हैं
        भागफल := r div newr
        (आर, नया) := (नया, आर - भागफल × नया)
        (t, newt) := (newt, t − भागफल × newt)

    अगर डिग्री (आर)> 0 तो
        रिटर्न या तो p इर्रिड्यूसिबल नहीं है या a, p का गुणज है

    वापसी (1/आर) × टी

उदाहरण

उदाहरण के लिए, यदि बहुपद परिमित क्षेत्र GF(2⁸) p = x है⁸ + x⁴ + x³ + x + 1, और a = x⁶ + x⁴ + x + 1 वह तत्व है जिसका व्युत्क्रम वांछित है, फिर एल्गोरिथम निष्पादित करने से निम्न तालिका में वर्णित गणना में परिणाम मिलते हैं। आइए याद करें कि क्रम 2 के क्षेत्रों मेंⁿ, फ़ील्ड में प्रत्येक तत्व z के लिए -z = z और z + z = 0 है)। चूँकि 1 GF(2) का एकमात्र अशून्य तत्व है, स्यूडोकोड की अंतिम पंक्ति में समायोजन की आवश्यकता नहीं है।

step	quotient	r, newr	s, news	t, newt
		p = x8 + x4 + x3 + x + 1	1	0
		a = x6 + x4 + x + 1	0	1
1	x2 + 1	x2 = p - a (x2 + 1)	1	x2 + 1 = 0 - 1 × (x2 + 1)
2	x4 + x2	x + 1 = a - x2 (x4 + x2)	x4+x2 = 0 - 1(x4+x2)	x6 + x2 + 1 = 1 - (x4 + x2) (x2 + 1)
3	x + 1	1 = x2 - (x + 1) (x + 1)	x5+x4+x3+x2+1 = 1 - (x +1)(x4 + x2)	x7 + x6 + x3 + x = (x2 + 1) - (x + 1) (x6 + x2 + 1)
4	x + 1	0 = (x + 1) - 1 × (x + 1)	x6 + x4 + x + 1 = (x4+x2) - (x+1)(x5+x4+x3+x2+1)

अत: प्रतिलोम x है⁷ + x⁶ + x³ + x, जैसा कि परिमित क्षेत्र अंकगणित द्वारा पुष्टि की जा सकती है, और शेषफल द्वारा p परिणाम का।

दो से अधिक संख्याओं का मामला

कोई दो से अधिक संख्याओं के मामले को पुनरावृत्त रूप से संभाल सकता है। पहले हम दिखाते हैं $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$. इसे साबित करने के लिए आइए $d=\gcd(a,b,c)$. जीसीडी की परिभाषा के अनुसार $d$ का भाजक है $a$ और $b$. इस प्रकार $\gcd(a,b)=kd$ कुछ के लिए $k$. उसी प्रकार $d$ का भाजक है $c$ इसलिए $c=jd$ कुछ के लिए $j$. होने देना $u=\gcd(k,j)$. हमारे निर्माण से $u$, $ud|a,b,c$ लेकिन फिर $d$ सबसे बड़ा भाजक है $u$ एक इकाई (रिंग थ्योरी) है। और तबसे $ud=\gcd(\gcd(a,b),c)$ परिणाम सिद्ध होता है।

तो यदि $na+mb=\gcd(a,b)$ तो वहाँ हैं $x$ और $y$ ऐसा है कि $x\gcd(a,b)+yc=\gcd(a,b,c)$ तो अंतिम समीकरण होगा

$x(na+mb)+yc=(xn)a+(xm)b+yc=\gcd(a,b,c).\,$

तो फिर एन नंबरों पर लागू करने के लिए हम इंडक्शन का उपयोग करते हैं

$\gcd(a_{1},a_{2},\dots ,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{3},\dots ,\gcd(a_{n-1}\,,a_{n}))),\dots ),$

सीधे निम्नलिखित समीकरणों के साथ।

यह भी देखें

• यूक्लिडियन डोमेन
• रेखीय सर्वांगसमता प्रमेय
• कुट्टक

संदर्भ

• Knuth, Donald. The Art of Computer Programming. Addison-Wesley. Volume 2, Chapter 4.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859–861 of section 31.2: Greatest common divisor.

बाहरी संबंध

• Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)