यूलर का प्रमेय फर्मेट के छोटे प्रमेय का एक सामान्यीकरण है जो धनात्मक पूर्णांकों के मॉड्यूलो पूर्णांकों की शक्तियों को संभालता है। यह RSA क्रिप्टोसिस्टम के लिए सैद्धांतिक सहायक संरचना जैसे प्रारंभिक संख्या सिद्धांत के अनुप्रयोगों में उत्पन्न होता है।
यह प्रमेय बताता है कि प्रत्येक a और n के लिए जो अपेक्षाकृत अभाज्य हैं:
$$\mathrm{a^{\phi (n)}\, \equiv\, 1 (mod\, n) }$$
जहां φ(n) यूलर का टोटिएंट फ़ंक्शन है, जो n से कम उन धनात्मक पूर्णांकों की संख्या गिनता है जो n के अपेक्षाकृत अभाज्य हैं।
ऐसे पूर्णांकों के समुच्चय पर विचार करें:
R = {x₁, x₂, … x_φ(n)}, यानी R का प्रत्येक तत्व xᵢ n से कम एक अद्वितीय धनात्मक पूर्णांक है जहां gcd(xᵢ, n) = 1। फिर प्रत्येक तत्व को a से गुणा करें और मॉड्यूलो n लें:
S = {(ax₁ mod n), (ax₂ mod n), … (ax_φ(n) mod n)}
क्योंकि a, n के अपेक्षाकृत अभाज्य है और xᵢ, n के अपेक्षाकृत अभाज्य है, axᵢ भी n के अपेक्षाकृत अभाज्य होना चाहिए। इसलिए, S के सभी सदस्य ऐसे पूर्णांक हैं जो n से कम हैं और n के अपेक्षाकृत अभाज्य हैं।
S में कोई डुप्लिकेट नहीं हैं।
यदि axᵢ mod n = axⱼ mod n तो xᵢ = xⱼ
$$\mathrm{Therefore,\, \Pi _{i=1}^{\phi (n)}(ax_{i}\, mod\, n)=\Pi _{i=1}^{\phi (n)}\, x_{i}}$$
$$\mathrm{\Pi _{i=1}^{\phi (n)}\, ax_{i}\equiv \Pi _{i=1}^{\phi (n)}\, x_{i} (mod\, n)}$$
$$\mathrm{a^{\phi (n)}\, x\left [ \Pi _{i=1}^{\phi (n)}\, x_{i} \right ]=\Pi _{i=1}^{\phi (n)}\, x_{i} (mod\, n)}$$
$$\mathrm{a^{\phi (n)}\equiv 1 (mod\, n)}$$
यूलर टोटिएंट फ़ंक्शन
यूलर का टोटिएंट फ़ंक्शन गणितीय गुणात्मक फ़ंक्शन हैं जो दिए गए पूर्णांक जिसे आमतौर पर 'n' के रूप में जाना जाता है, तक धनात्मक पूर्णांकों की गिनती करते हैं जो 'n' के लिए अभाज्य संख्या हैं और फ़ंक्शन का उपयोग दिए गए पूर्णांक 'n' तक मौजूद अभाज्य संख्याओं की संख्या समझने के लिए किया जा सकता है।
यूलर का टोटिएंट फ़ंक्शन यूलर के फाई फ़ंक्शन के रूप में भी जाना जाता है। यह क्रिप्टोग्राफी में एक आवश्यक भूमिका निभाता है। यह उन पूर्णांकों की संख्या खोज सकता है जो n से छोटे हैं और n के अपेक्षाकृत अभाज्य हैं। संख्याओं का यह समुच्चय Zₙ* द्वारा परिभाषित है (संख्याएं जो n से छोटी हैं और n के अपेक्षाकृत अभाज्य हैं)।
यूलर का टोटिएंट फ़ंक्शन कई मायनों में फायदेमंद है। इसका उपयोग RSA एन्क्रिप्शन सिस्टम में किया जा सकता है, जिसे सुरक्षा लक्ष्यों के लिए उपयोग किया जा सकता है। फ़ंक्शन अभाज्य संख्या सिद्धांत से संबंधित है, और यह बड़ी गणनाओं की गणना में भी फायदेमंद है। फ़ंक्शन का उपयोग बीजगणितीय गणना और सरल संख्याओं में किया जा सकता है।
फ़ंक्शन को इंगित करने के लिए उपयोग किया जाने वाला प्रतीक φ है, और इसे फाई फ़ंक्शन के रूप में भी जाना जाता है। फ़ंक्शन में व्यावहारिक उपयोग के बजाय अधिक सैद्धांतिक उपयोग शामिल है। फ़ंक्शन की समझदार आवश्यकता सीमित है।
फ़ंक्शन को केवल सैद्धांतिक स्पष्टीकरण के बजाय कई व्यावहारिक उदाहरणों के माध्यम से बेहतर ढंग से समझा जा सकता है। यूलर के टोटिएंट फ़ंक्शन की गणना के लिए कई नियम हैं, और विभिन्न संख्याओं के लिए, विभिन्न नियमों का उपयोग किया जाना है।
यूलर टोटिएंट फ़ंक्शन φ(n) निम्नलिखित नियमों की सहायता से Zₙ* में तत्वों की संख्या की गणना करता है:
φ(1) = 0।
φ(P) = P - 1 यदि P अभाज्य है।
φ(m x n) = φ(m) x φ(n) यदि m और n अपेक्षाकृत अभाज्य हैं।
φ(Pe) = Pe - Pe-1 (यदि P अभाज्य है)।
निम्नलिखित चार नियमों को φ(n) का मान प्राप्त करने के लिए जोड़ा जा सकता है, n को फैक्टराइज़ करें:
$$\mathrm{n=P_{1}^{e1}\, x\,P_{2}^{e2}x\cdot \cdot \cdot P_{k}^{ek}}$$
$$\mathrm{\phi (n)=\left ( P_{1}^{e1}-P_{1}^{e1-1} \right )\left ( P_{2}^{e2}-P_{2}^{e2-1} \right )x\cdot \cdot \cdot x\left (P_{k}^{ek}-P_{k}^{ek-1} \right )}$$
φ(n) खोजने की कठिनाई n के फैक्टराइज़ेशन खोजने की कठिनाई पर निर्भर करती है।
