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

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

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

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

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

विस्तारित यूक्लिडियन एल्गोरिथ्म विशेष रूप से तब उपयोगी होता है जब 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, वह सबसे बड़ा पूर्णांक है जो इससे बड़ा नहीं है 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}|,$ का क्रम $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: Polynomial greatest common divisor § Bézout's identity and extended GCD algorithm

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

स्यूडोकोड

In this section and the following ones, div is an auxiliary function that computes the quotient of the Euclidean division of its left argument by its right argument.

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

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

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

के बराबर है

साबित: = आर;
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}$ अनुक्रम (जो बेज़ाउट गुणांक उत्पन्न करता है $x$), और फिर गणना करें $y$ अंत में:

फ़ंक्शन विस्तारित_जीसीडी (ए, बी)
    एस: = 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 का गुणन bezout_t की गणना में अतिप्रवाह हो सकता है, इस अनुकूलन को इनपुट तक सीमित कर सकता है जिसे आधे से कम अधिकतम आकार में प्रदर्शित किया जा सकता है। असीमित आकार के पूर्णांकों का उपयोग करते समय, गुणन और विभाजन के लिए आवश्यक समय पूर्णांकों के आकार के साथ द्विघात रूप से बढ़ता है। इसका तात्पर्य यह है कि अनुकूलन एक गुणन/विभाजन द्वारा छोटे पूर्णांकों के गुणन/विभाजनों के अनुक्रम को प्रतिस्थापित करता है, जिसके लिए एक साथ लिए गए संचालन की तुलना में अधिक कंप्यूटिंग समय की आवश्यकता होती है।

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

एक अंश 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 विभाजित a समान रूप से, एल्गोरिदम केवल एक पुनरावृत्ति निष्पादित करता है, और हमारे पास है s = 1 एल्गोरिथ्म के अंत में। यह एकमात्र मामला है जहां आउटपुट पूर्णांक है।

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

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

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

Main article: Modular arithmetic

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

बेज़ाउट की पहचान इस बात का दावा करती है a और n कोप्राइम हैं अगर और केवल अगर पूर्णांक मौजूद हैं s और t ऐसा है कि

$ns+at=1$

इस पहचान मॉड्यूल को कम करना n देता है

$at\equiv 1\mod n.$

इस प्रकार t, या, अधिक सटीक रूप से, के विभाजन का शेष भाग t द्वारा n, का गुणक प्रतिलोम है a मापांक 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)