तर्कसंगत पुनर्निर्माण (गणित)

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

समस्या कथन

तर्कसंगत पुनर्निर्माण समस्या में, एक को इनपुट के रूप में मान दिया जाता है $n\equiv r/s{\pmod {m}}$. वह है, $n$ संपत्ति के साथ एक पूर्णांक है $ns\equiv r{\pmod {m}}$. तर्कसंगत संख्या $r/s$ अज्ञात है, और समस्या का लक्ष्य इसे दी गई जानकारी से पुनर्प्राप्त करना है।

समस्या को हल करने योग्य होने के लिए, यह मान लेना आवश्यक है कि मापांक $m$ की तुलना में काफी बड़ा है $r$ और $s$. आमतौर पर, यह माना जाता है कि के संभावित मूल्यों के लिए एक सीमा $r$ और $s$ ज्ञात है: $|r|<N$ और $0<s<D$ कुछ दो के लिए संख्यात्मक पैरामीटर $N$ और $D$. जब कभी भी $m>2ND$ और एक समाधान मौजूद है, समाधान अद्वितीय है और कुशलता से पाया जा सकता है।

समाधान

पॉल एस वांग से एक विधि का उपयोग करना, पुनर्प्राप्त करना संभव है $r/s$ से $n$ और $m$ यूक्लिडियन एल्गोरिथ्म का उपयोग इस प्रकार है। एक डालता है $v=(m,0)$ और $w=(n,1)$. एक तब निम्न चरणों को दोहराता है जब तक कि w का पहला घटक नहीं बन जाता $\leq N$. रखना $q=\left\lfloor {\frac {v_{1}}{w_{1}}}\right\rfloor$, z = v − qw रखें। नया v और w तब v = w और w = z लगाकर प्राप्त किया जाता है।

फिर डब्ल्यू के साथ ऐसा है $w_{1}\leq N$, w = −w if लगाकर दूसरा घटक सकारात्मक बनाता है $w_{2}<0$. अगर $w_{2}<D$ और $\gcd(w_{1},w_{2})=1$, फिर अंश ${\frac {r}{s}}$ मौजूद है और $r=w_{1}$ और $s=w_{2}$, अन्यथा ऐसा कोई अंश मौजूद नहीं है।