मॉड्यूलो $n$ के नियमित पूर्णांकों की संख्या पर और क्रिप्टोग्राफी के लिए इसका महत्व

मूल जानकारी

• पेपर ID: 2304.02471
• शीर्षक: On the Number of Regular Integers Modulo $n$ and Its Significance to Cryptography
• लेखक: Klaus Dohmen, Mandy Lange-Geisler (Hochschule Mittweida, जर्मनी)
• वर्गीकरण: math.CO (संयोजन गणित), math.GR (समूह सिद्धांत), math.NT (संख्या सिद्धांत)
• प्रकाशन समय: 25 अक्टूबर 2023 (arXiv संस्करण)
• पेपर लिंक: https://arxiv.org/abs/2304.02471v6

सारांश

यह पेपर द्विभाजन सिद्धांत और समावेशन-बहिष्करण सिद्धांत के आधार पर, मॉड्यूलो $n$ नियमित पूर्णांकों की संख्या पर Morgado के सूत्र के लिए चार संयोजनात्मक प्रमाण प्रदान करता है। यह सूत्र OEIS में अनुक्रम A055653 के अनुरूप है, जहां पूर्णांक $m$ को मॉड्यूलो $n$ नियमित कहा जाता है, यदि और केवल यदि सर्वांगसमता समीकरण $m^2x \equiv m \pmod{n}$ पूर्णांक वलय $\mathbb{Z}$ में समाधान रखता है। इस अनुसंधान के महत्व को रेखांकित करने के लिए, लेखकों ने इस अनुक्रम और Morgado सूत्र को RSA क्रिप्टोसिस्टम के हाल ही में प्रस्तावित बहु-अभाज्य बहु-शक्ति सामान्यीकरण से जोड़ा है।

अनुसंधान पृष्ठभूमि और प्रेरणा

मूल समस्या

इस अनुसंधान द्वारा समाधान की जाने वाली मूल समस्या मॉड्यूलो $n$ नियमित पूर्णांकों की संख्या की गणना करना और क्रिप्टोग्राफी में इसके अनुप्रयोग महत्व की खोज करना है।

समस्या का महत्व

1. सैद्धांतिक महत्व: नियमित पूर्णांकों की अवधारणा को Morgado द्वारा 1972 में पहली बार प्रस्तावित किया गया था, यह संख्या सिद्धांत में एक महत्वपूर्ण संयोजनात्मक वस्तु है, जिसका गणना सूत्र इकाई कारकों और यूलर फ़ंक्शन जैसी मूल संख्या-सैद्धांतिक अवधारणाओं को शामिल करता है।
2. व्यावहारिक अनुप्रयोग: लेखकों द्वारा प्रस्तावित RSA क्रिप्टोसिस्टम के सामान्यीकरण में, नियमित पूर्णांक सही ढंग से डिक्रिप्ट किए जा सकने वाले संदेश स्थान का गठन करते हैं, इसलिए उनकी संख्या क्रिप्टोसिस्टम की सही डिक्रिप्शन की संभावना से सीधे संबंधित है।

मौजूदा विधियों की सीमाएं

Morgado सूत्र के पूर्ववर्ती प्रमाण मुख्य रूप से $\varrho(n)$ फ़ंक्शन के गुणक गुणों पर निर्भर करते हैं, जिनमें सहज संयोजनात्मक व्याख्या की कमी है। यह पेपर शुद्ध संयोजनात्मक विधियों के माध्यम से गहन समझ प्रदान करता है।

अनुसंधान प्रेरणा

लेखकों की अनुसंधान प्रेरणा बहु-अभाज्य बहु-शक्ति RSA सामान्यीकरण में उनके द्वारा सामना की गई व्यावहारिक आवश्यकता से उत्पन्न होती है, जिसमें किसी भी संदेश की सही डिक्रिप्शन संभावना का अनुमान लगाने की आवश्यकता होती है।

मूल योगदान

1. चार संयोजनात्मक प्रमाण प्रदान करना: द्विभाजन सिद्धांत और समावेशन-बहिष्करण सिद्धांत के आधार पर, Morgado सूत्र के लिए चार विभिन्न कोणों से संयोजनात्मक प्रमाण दिए गए हैं।
2. एन्कोडिंग योजना स्थापित करना: चौथा प्रमाण नियमित पूर्णांकों की स्पष्ट एन्कोडिंग देता है, जो अनुक्रम A055653 के आगे के अनुसंधान के लिए मूल्यवान हो सकता है।
3. क्रिप्टोग्राफिक अनुप्रयोग: नियमित पूर्णांक सिद्धांत को RSA क्रिप्टोसिस्टम के सामान्यीकरण से जोड़ना, इस संख्या-सैद्धांतिक अवधारणा के व्यावहारिक महत्व को प्रकट करता है।
4. सैद्धांतिक अंतर्दृष्टि: संयोजनात्मक विधि के माध्यम से स्वाभाविक रूप से $\varrho(n)$ फ़ंक्शन के गुणक गुणों को प्राप्त करना।

विधि विवरण

कार्य परिभाषा

इनपुट: सकारात्मक पूर्णांक $n$आउटपुट: मॉड्यूलो $n$ नियमित पूर्णांकों की संख्या $\varrho(n)$बाधा: पूर्णांक $m$ मॉड्यूलो $n$ नियमित है यदि और केवल यदि $x \in \mathbb{Z}$ मौजूद है जैसे कि $m^2x \equiv m \pmod{n}$

मूल सैद्धांतिक आधार

परिभाषा: पूर्णांक $m$ को मॉड्यूलो $n$ नियमित कहा जाता है, यदि सर्वांगसमता समीकरण $m^2x \equiv m \pmod{n}$ का पूर्णांक समाधान है।

Morgado सूत्र (प्रमेय 1): $\varrho(n) = \sum_{d \parallel n} \varphi(d)$ जहां $d \parallel n$ का अर्थ है कि $d$ $n$ का एक इकाई कारक है (अर्थात् $d|n$ और $\gcd(d, n/d) = 1$)।

मुख्य गुण (प्रस्ताव 2): किसी भी $n \in \mathbb{N}$ और $m \in \mathbb{Z}$ के लिए, निम्नलिखित शर्तें समतुल्य हैं:

• (a) $m$ मॉड्यूलो $n$ नियमित है
• (b) $\gcd(m^2, n) = \gcd(m, n)$
• (c) $\gcd(m, n) \parallel n$

चार प्रमाण विधियां

विधि 1: समतुल्यता संबंध प्रमाण

$\mathbb{Z}^{\text{reg}}_n$ पर समतुल्यता संबंध $m_1 \sim m_2 \Leftrightarrow \gcd(m_1, n) = \gcd(m_2, n)$ को परिभाषित करके, समतुल्य वर्गों और $\mathbb{Z}^*_{n/d}$ के बीच द्विभाजन स्थापित करना।

विधि 2: शुद्ध द्विभाजन प्रमाण

मानचित्र $f_n: \mathbb{Z}^{\text{reg}}_n \to \{(d, d') | d \parallel n, d' \in \mathbb{Z}^*_d\}$ का निर्माण: $f_n(m) := \left(\frac{n}{\gcd(m,n)}, m \bmod \frac{n}{\gcd(m,n)}\right)$

इस मानचित्र का व्युत्क्रम मानचित्र है: $f_n^{-1}(d, d') = \frac{n}{d}\left(((n/d \bmod d)^{-1}d') \bmod d\right)$

विधि 3: इरेड्यूसिबल भिन्न प्रमाण

प्रत्येक $m \in \mathbb{Z}^{\text{reg}}_n$ को इरेड्यूसिबल भिन्न $m/n$ के अनुरूप करना, यह सिद्ध करना कि इन इरेड्यूसिबल भिन्नों के हर बिल्कुल $n$ के सभी इकाई कारक हैं।

विधि 4: समावेशन-बहिष्करण सिद्धांत प्रमाण

$P(n)$ को $n$ के अभाज्य कारकों का समुच्चय मानते हुए, प्रत्येक अभाज्य $p \in P(n)$ के लिए परिभाषित करना: $A_p = \{m \in \mathbb{Z}_n | 0 < m_p < n_p\}$ जहां $m_p$ $m$ के अभाज्य गुणनखंड में $p$ की बहुलता को दर्शाता है, फिर समावेशन-बहिष्करण सिद्धांत को लागू करना।

तकनीकी नवाचार बिंदु

1. संयोजनात्मक दृष्टिकोण: पूर्ववर्ती गुणक-आधारित प्रमाणों के विपरीत, यह पेपर सहज संयोजनात्मक व्याख्या प्रदान करता है।
2. द्विभाजन निर्माण: दूसरा प्रमाण नियमित पूर्णांकों की स्पष्ट एन्कोडिंग और डिकोडिंग एल्गोरिथ्म देता है।
3. बहु-कोण विश्लेषण: चार प्रमाण विभिन्न कोणों से नियमित पूर्णांकों के सार को प्रकट करते हैं।
4. क्रिप्टोग्राफिक संबंध: पहली बार नियमित पूर्णांक सिद्धांत को आधुनिक क्रिप्टोग्राफिक अनुप्रयोगों से जोड़ना।

प्रायोगिक सेटअप

संख्यात्मक सत्यापन

पेपर ठोस उदाहरणों के माध्यम से सैद्धांतिक परिणामों को सत्यापित करता है:

उदाहरण: $n = 20$ की स्थिति

• इकाई कारक: $1, 4, 5, 20$
• $\varphi(1) = 1, \varphi(4) = 2, \varphi(5) = 4, \varphi(20) = 8$
• पूर्वानुमानित मान: $\varrho(20) = 1 + 2 + 4 + 8 = 15$
• वास्तविक नियमित पूर्णांक: $\{0, 1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19\}$
• सत्यापन: $|\mathbb{Z}^{\text{reg}}_{20}| = 15$ ✓

मानचित्र उदाहरण

पेपर $f_{20}$ मानचित्र के सभी संगत संबंधों को विस्तार से प्रदर्शित करता है, द्विभाजन की सही्ता को सत्यापित करता है।

प्रायोगिक परिणाम

सैद्धांतिक सत्यापन

सभी चार प्रमाण Morgado सूत्र की सही्ता को सफलतापूर्वक स्थापित करते हैं, प्रत्येक विधि अद्वितीय संयोजनात्मक अंतर्दृष्टि प्रदान करती है।

क्रिप्टोग्राफिक अनुप्रयोग परिणाम

बहु-अभाज्य बहु-शक्ति RSA सामान्यीकरण में:

• सही डिक्रिप्शन संभावना: $\frac{\varrho(n)}{n} = \frac{1}{n}\sum_{d \parallel n} \varphi(d)$
• निम्न सीमा अनुमान: $n = p_1^{e_1} \cdots p_r^{e_r}$ के लिए (जहां $p_i$ $k$-बिट अभाज्य हैं), $\frac{\varrho(n)}{n} \geq 1 - \frac{r}{2^{k-1}}$
• व्यावहारिक महत्व: जब $k = 1024$ हो, तो लगभग सभी संदेश सही ढंग से डिक्रिप्ट हो सकते हैं।

संबंधित कार्य

ऐतिहासिक विकास

1. Morgado (1972): पहली बार नियमित पूर्णांक अवधारणा को परिभाषित किया और गणना सूत्र दिया।
2. Alkam & Osba (2008): नियमित पूर्णांकों के गुणों का आगे अनुसंधान।
3. Apostol & Petrescu (2013): संबंधित फ़ंक्शन के चरम गुणों का अनुसंधान।
4. Tóth (2008): स्पर्शोन्मुख परिणाम और संबंधित फ़ंक्शन विश्लेषण।

इस पेपर का योगदान

मौजूदा कार्य की तुलना में, यह पेपर पहली बार शुद्ध संयोजनात्मक प्रमाण विधियां प्रदान करता है और क्रिप्टोग्राफी के साथ महत्वपूर्ण संबंध स्थापित करता है।

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

1. Morgado सूत्र में समृद्ध संयोजनात्मक व्याख्याएं हैं, प्रत्येक प्रमाण संरचना के विभिन्न स्तरों को प्रकट करता है।
2. नियमित पूर्णांक RSA क्रिप्टोसिस्टम के सामान्यीकरण में महत्वपूर्ण भूमिका निभाते हैं।
3. व्यावहारिक पैरामीटर चयन के लिए, सही डिक्रिप्शन संभावना 1 के करीब है।

सीमाएं

1. क्रिप्टोग्राफिक अनुप्रयोग विशिष्ट RSA सामान्यीकरण तक सीमित हैं।
2. स्पर्शोन्मुख विश्लेषण को आगे के अनुसंधान की आवश्यकता है।
3. कम्प्यूटेशनल जटिलता विश्लेषण पर्याप्त गहन नहीं है।

भविष्य की दिशाएं

1. अधिक सटीक संभाव्यता सीमाएं विकसित करना।
2. अनुक्रम A055653 के स्पर्शोन्मुख गुणों का अनुसंधान।
3. अन्य क्रिप्टोग्राफिक अनुप्रयोगों की खोज।

गहन मूल्यांकन

लाभ

1. सैद्धांतिक नवाचार: चार संयोजनात्मक प्रमाण प्रत्येक अद्वितीय हैं, नियमित पूर्णांकों की समझ को समृद्ध करते हैं।
2. विधि कठोरता: प्रमाण प्रक्रिया सख्त है, तर्क स्पष्ट है।
3. अनुप्रयोग मूल्य: क्रिप्टोग्राफी के साथ संबंध सैद्धांतिक अनुसंधान के व्यावहारिक महत्व को बढ़ाता है।
4. स्पष्ट अभिव्यक्ति: पेपर संरचना तर्कसंगत है, उदाहरण समृद्ध हैं।

कमियां

1. अनुप्रयोग सीमाएं: क्रिप्टोग्राफिक अनुप्रयोग लेखकों द्वारा स्वयं प्रस्तावित RSA सामान्यीकरण तक सीमित हैं।
2. कम्प्यूटेशनल विश्लेषण: एल्गोरिथ्म जटिलता का गहन विश्लेषण अनुपस्थित है।
3. प्रायोगिक सत्यापन: केवल छोटे पैमाने पर संख्यात्मक सत्यापन है, बड़े पैमाने पर कम्प्यूटेशनल प्रयोग अनुपस्थित हैं।

प्रभाव

1. शैक्षणिक मूल्य: संख्या सिद्धांत संयोजन गणित के लिए नई अनुसंधान दिशाएं प्रदान करता है।
2. व्यावहारिक संभावना: क्रिप्टोग्राफी में संभावित अनुप्रयोग मूल्य है।
3. पुनरुत्पादनीयता: सैद्धांतिक प्रमाण पूर्ण हैं, परिणाम सत्यापन में आसान हैं।

लागू परिदृश्य

1. संख्या सिद्धांत और संयोजन गणित का सैद्धांतिक अनुसंधान।
2. क्रिप्टोग्राफी में मॉड्यूलर संचालन से संबंधित परिदृश्य।
3. विशेष पूर्णांक समुच्चय के आकार की गणना की आवश्यकता वाले अनुप्रयोग।

संदर्भ

पेपर 8 संबंधित संदर्भों का हवाला देता है, जो नियमित पूर्णांक सिद्धांत के मुख्य विकास और संबंधित गणितीय आधार को शामिल करते हैं, पाठकों को पूर्ण पृष्ठभूमि ज्ञान प्रदान करते हैं।

समग्र मूल्यांकन: यह एक उच्च-गुणवत्ता वाला गणितीय पेपर है, जो बहु-संयोजनात्मक विधियों के माध्यम से एक शास्त्रीय संख्या-सैद्धांतिक समस्या की समझ को गहरा करता है, और आधुनिक क्रिप्टोग्राफी के साथ सफलतापूर्वक संबंध स्थापित करता है। पेपर का सैद्धांतिक योगदान ठोस है, अनुप्रयोग संभावनाएं विस्तृत हैं, यह संख्या सिद्धांत संयोजन गणित क्षेत्र में मूल्यवान कार्य है।