असतत लघुगणक: Difference between revisions

Latest revision as of 15:10, 26 December 2022

गणित में, दी गई वास्तविक संख्याओं a और b के लिए लघुगणक log_ba एक संख्या x है जैसे कि b^x = a. इसी तरह, किसी भी समूह (गणित) G में, घात b^k को सभी पूर्णांक k केलिये परिभाषित किया जा सकता है, और 'असतत लघुगणक' log_b a एक पूर्णांक k है जैसे कि b^k = a. संख्या सिद्धांत में, अधिक सामान्य रूप से प्रयोग किया जाने वाला शब्द सूचकांक है: हम r^x ≡ a (mod m) के लिये x = ind_r a (mod m) (r के लिए a से आधार r सापेक्ष m का सूचकांक पढ़ें)। यदि r, m और भाजक (a,m) = 1 का एक अभाज्य मूल है।

असतत लघुगणक कुछ विशेष स्थितियों में शीघ्रता से संगणनीय होते हैं। चूँकि, सामान्य रूप से उनकी गणना करने के लिए कोई प्रभावी विधि ज्ञात नहीं है। सार्वजनिक कुंजी क्रिप्टोग्राफी में कई महत्वपूर्ण कलन विधि, जैसे एलगमाल क्रिप्टोसिस्टम उनकी सुरक्षा को इस धारणा पर आधारित करते हैं कि सावधानीपूर्वक चुने गए समूहों पर असतत लघुगणक समस्या का कोई कुशल समाधान नहीं है।^[1]

परिभाषा

माना G कोई समूह है। इसकी समूह संक्रिया को गुणन द्वारा और इसके सर्वसमता अवयव को 1 से निरूपित करें। मान लीजिए कि b, G का कोई अवयव है। किसी धनात्मक पूर्णांक k के लिए व्यंजक b^k , b के गुणनफल को स्वयं k बार दर्शाता है:^[2]

b^{k}=\underbrace {b\cdot b\cdots b} _{k\;{\text{factors}}}.

इसी तरह, b^−k को b⁻¹ के गुणनफल को स्वयं k बार दर्शाने दें। k = 0 के लिए, k वीं घात सर्वसमिका: b⁰ = 1 है.

मान लीजिए a भी G का एक अवयव है। एक पूर्णांक k जो समीकरण b^k = a को हल करता है, a को आधार b के असतत लघुगणक (या इस संदर्भ में केवल लघुगणक) कहा जाता है। एक k = log_b a लिखता है।

उदाहरण

10 की घातें

10 की घातें हैं

\ldots ,0.001,0.01,0.1,1,10,100,1000,\ldots .

इस सूची में किसी भी संख्या के लिए, कोई भी log₁₀ a की गणना कर सकता है। उदाहरण के लिए, log₁₀ 10000 = 4, और log₁₀ 0.001 = −3 । ये असतत लघुगणक समस्या के उदाहरण हैं।

वास्तविक संख्या में अन्य आधार -10 लघुगणक असतत लघुगणक समस्या के उदाहरण नहीं हैं, क्योंकि उनमें गैर-पूर्णांक घातांक सम्मिलित हैं। उदाहरण के लिए, समीकरण log₁₀ 53 = 1.724276… का अर्थ है कि 10^1.724276… = 53। जबकि पूर्णांक घातांक को उत्पादों और व्युत्क्रमों का उपयोग करके किसी भी समूह में परिभाषित किया जा सकता है, स्वेच्छ वास्तविक घातांक, जैसे कि यह 1.724276…, अन्य अवधारणाओं जैसे घातीय फलन की आवश्यकता होती है।

समूह-सैद्धांतिक शर्तों में, 10 की घात के गुणा के तहत चक्रीय समूह G बनाती हैं, और 10 इस समूह के लिए जनक है। असतत लघुगणक लॉग₁₀a को G में किसी भी a के लिए परिभाषित किया गया है।

निश्चित वास्तविक संख्या की घात

इसी तरह का उदाहरण किसी भी गैर-शून्य वास्तविक संख्या b के लिए है। घात गैर-शून्य वास्तविक संख्याओं का गुणक उपसमूह G = {…, b⁻³, b⁻², b⁻¹, 1, b¹, b², b³, …} बनाते हैं। G के किसी भी अवयव के लिए log_b a की गणना की जा सकती है।

सापेक्षर अंकगणित

असतत लघुगणक के लिए सबसे सरल सेटिंग्स में से एक समूह (Z)_p)^× है। यह गुणन सापेक्षर अभाज्य संख्या p का समूह है। इसके तत्व सर्वांगसमता वर्ग सापेक्ष p है, और दो तत्वों के समूह उत्पाद को तत्वों के साधारण पूर्णांक गुणन द्वारा प्राप्त किया जा सकता है, जिसके बाद कमी सापेक्ष p की होता है।

इस समूह में किसी एक संख्या के kवें घातांक की गणना उसकी kth घात को एक पूर्णांक के रूप में ज्ञात करके और फिर p द्वारा विभाजन के बाद शेषफल ज्ञात करके की जा सकती है। जब सम्मिलित संख्याएं बड़ी होती हैं, तो गणना के दौरान सापेक्ष p को कई बार कम करना अधिक कुशल होता है। उपयोग किए गए विशिष्ट कलन विधि के बाद भी, इस ऑपरेशन को सापेक्षर घातांक कहा जाता है। उदाहरण के लिए, ('Z'₁₇)^× पर विचार करें. इस समूह में, 3⁴ की गणना करने के लिये 3⁴ = 81 की गणना करें, और फिर 81 को 17 से भाग देकर शेषफल 13 प्राप्त होता है। इस प्रकार 3⁴ = समूह में 13 (Z₁₇)^×.

असतत लघुगणक केवल व्युत्क्रम संक्रिया है। उदाहरण के लिए, k के लिए समीकरण 3^k ≡ 13 (mod 17) पर विचार करे। उपरोक्त उदाहरण से, एक समाधान k = 4 है, लेकिन यह एकमात्र समाधान नहीं है। चूंकि 3¹⁶ ≡ 1 (मॉड 17)— फ़र्मा के छोटे प्रमेय से अनुसरण करता है—यह भी अनुसरण करता है कि यदि n एक पूर्णांक है तो 3⁴⁺¹⁶ⁿ ≡ 3⁴ × (3¹⁶)ⁿ ≡ 13 × 1ⁿ ≡ 13 (मॉड 17)। अतः समीकरण के 4 + 16n रूप के अपरिमित रूप से अनेक हल हैं। इसके अतिरिक्त, क्योंकि 16 सबसे छोटा धनात्मक पूर्णांक m है जो 3^m ≡ 1 (मॉड 17) को संतुष्ट करता है, यही एकमात्र समाधान हैं। समतुल्य रूप से, सभी संभावित समाधानों का सेट बाधा द्वारा व्यक्त किया जा सकता है कि k ≡ 4 (mod 16)।

पहचान की घातें

विशेष स्थिति में जहां b समूह G का पहचान तत्व 1 है, असतत लघुगणक log_b a 1 के अलावा अन्य के लिए अपरिभाषित है, और प्रत्येक पूर्णांक k = 1 के लिए असतत लघुगणक है।

गुण

घात सामान्य बीजगणितीय पहचान b^k^+ l = b^k b^l का पालन करते हैं। दूसरे शब्दों में, फलन

f\colon \mathbf {Z} \to G

f(k) = b^k द्वारा परिभाषित पूर्णांकों 'Z' से एक समूह समरूपता है, जो b द्वारा उत्पन G के उपसमूह H पर योग के तहत है।। H में सभी a के लिए, log_b a में उपस्थित है। इसके विपरीत a के लिए log_b a का अस्तित्व नहीं है जो H में नहीं है।

यदि H अनंत है, तो log_b a भी अद्वितीय है, और असतत लघुगणक एक समूह समरूपता के बराबर है

\log _{b}\colon H\to \mathbf {Z} .

दूसरी ओर, यदि H क्रम (समूह सिद्धांत) n का परिमित है, तो log_b a केवल सापेक्षर अंकगणित तक अद्वितीय है, और असतत लघुगणक एक समूह समरूपता के बराबर है

\log _{b}\colon H\to \mathbf {Z} _{n},

जहां Z_n पूर्णांक सापेक्षो n के योज्य समूह को दर्शाता है।

साधारण लघुगणकों के लिए परिचित आधार परिवर्तन सूत्र मान्य रहता है: यदि c, H का एक और जनरेटर है, तो

\log _{c}a=\log _{c}b\cdot \log _{b}a.

कलन विधि

असतत लघुगणक समस्या को अभिकलनीयतः रूप से असभ्य माना जाता है। यही है, सामान्य रूप से असतत कलन विधि की गणना के लिए कोई कुशल पारंपरिक कलन विधि ज्ञात नहीं है।

परिमित समूह G में log_b a की गणना करने के लिए एक सामान्य कलन विधि b को बड़ी और बड़ी घातों k तक बढ़ाना है जब तक कि वांछित a नहीं मिल जाता। इस कलन विधि को कभी-कभी परीक्षण गुणा कहा जाता है। इसके लिए समूह G के आकार में रैखिक समय की आवश्यकता होती है और इस प्रकार समूह के आकार में अंकों की संख्या में घातांक होता है। इसलिए, यह एक घातीय-समय कलन विधि है, जो केवल छोटे समूहों G के लिए व्यावहारिक है।

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

छोटा-पद विशाल-पद
फलन क्षेत्र की जाँच
सूचकांक गणना कलन विधि
संख्या क्षेत्र जाँच
पोहलिग-हेलमैन कलन विधि
कलन विधि के लिए पोलार्ड का rho कलन विधि
पोलार्ड का कंगारू कलन विधि (उर्फ पोलार्ड का लैम्ब्डा कलन विधि)

पीटर शोर के कारण एक कुशल शोर का कलन विधि है।^[3]

कुशल पारंपरिक कलन विधि भी कुछ विशेष स्थितियों में उपस्थित हैं। उदाहरण के लिए, पूर्णांक सापेक्ष p के समूह में जोड़ के तहत, घात b^k एक उत्पाद bk बन जाता है, और समानता का मतलब पूर्णांकों में सर्वांगसम सापेक्ष p है। विस्तारित यूक्लिडियन कलन विधि k को जल्दी पाता है।

डिफी-हेलमैन के साथ एक चक्रीय समूह मापांक एक प्रमुख p का उपयोग किया जाता है, जिससे पोहलिग-हेलमैन के साथ असतत लघुगणक की एक कुशल गणना की अनुमति मिलती है यदि समूह का क्रम (p-1 होना) पर्याप्त रूप से सुचारू है, अर्थात इसमें कोई बड़े प्रमुख कारक नहीं हैं।

पूर्णांक गुणनखंड के साथ तुलना

असतत लघुगणक और पूर्णांक गुणनखंड की गणना करते समय अलग-अलग समस्याएं हैं, वे कुछ गुण साझा करते हैं:

दोनों परिमित विनिमेय समूहों के लिए छिपी हुई उपसमूह समस्या के विशेष स्थिति हैं,
दोनों समस्याएं कठिन प्रतीत होती हैं (गैर-एक संगणक जितना के लिए कोई कुशल कलन विधि ज्ञात नहीं हैं),
दोनों समस्याओं के लिए क्वांटम संगणकोण पर कुशल कलन विधि ज्ञात हैं,
एक समस्या के कलन विधि को अधिकांश दूसरी समस्या के लिए अनुकूलित किया जाता है, और
दोनों समस्याओं की कठिनाई का उपयोग विभिन्न क्रिप्टोग्राफी प्रणालियों के निर्माण के लिए किया गया है।

क्रिप्टोग्राफी

ऐसे समूह उपस्थित हैं जिनके लिए असतत लघुगणक की गणना स्पष्ट रूप से कठिन है। कुछ स्थितियों में (उदाहरण के लिए समूहों के बड़े प्रमुख क्रम उपसमूह (Z_p)^×) सबसे खराब स्थिति के लिए न केवल कोई कुशल कलन विधि ज्ञात है, बल्कि औसत-केस की जटिलता को यादृच्छिक स्व-न्यूनीकरण का उपयोग करके सबसे खराब स्थिति के रूप में दिखाया जा सकता है।^[4]

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

असतत लघुगणक क्रिप्टोग्राफी (डीएलसी) में समूह जी के लिए लोकप्रिय विकल्प चक्रीय समूह ('Z'_p)^× हैं, (उदाहरण के लिए एलगमाल एन्क्रिप्शन, डिफी-हेलमैन कुंजी विनिमय, और डिजिटल हस्ताक्षर कलन विधि) और परिमित क्षेत्रों पर दीर्घवृत्तीय वक्रों के चक्रीय उपसमूह अण्डाकार वक्र क्रिप्टोग्राफी देखें)।

जबकि सामान्य रूप से असतत लघुगणक समस्या को हल करने के लिए कोई सार्वजनिक रूप से ज्ञात कलन विधि नहीं है, संख्या क्षेत्र जाँच कलन विधि के पहले तीन चरण केवल समूह G पर निर्भर करते हैं, न कि G के विशिष्ट तत्वों पर जिनका परिमित log वांछित है। किसी विशिष्ट समूह के लिए इन तीन चरणों की पूर्वगणना करके, किसी को केवल अंतिम चरण को पूरा करने की आवश्यकता होती है, जो कि उस समूह में एक विशिष्ट लघुगणक प्राप्त करने के लिए पहले तीन की तुलना में बहुत कम अभिकलनीयतः रूप से महंगा है।^[5]

यह पता चला है कि बहुत अधिक इंटरनेट ट्रैफ़िक उन मुट्ठी भर समूहों में से एक का उपयोग करता है जो 1024 बिट्स या उससे कम क्रम के हैं, उदा। RFC 2409 में निर्दिष्ट ओकली प्राइम्स के क्रम के साथ चक्रीय समूह।^[6] लॉगजैम (कंप्यूटर सुरक्षा) हमले ने इस भेद्यता का उपयोग विभिन्न प्रकार की इंटरनेट सेवाओं से समझौता करने के लिए किया, जो उन समूहों के उपयोग की अनुमति देता है जिनका आदेश 512-बिट प्राइम नंबर था, जिसे क्रिप्टोग्राफी का निर्यात कहा जाता है।^[5]

लोगजाम (कंप्यूटर सुरक्षा) हमले के लेखकों का अनुमान है कि 1024-बिट प्राइम के लिए असतत लॉग समस्या को हल करने के लिए आवश्यक अधिक कठिन पूर्व-गणना एक बड़ी राष्ट्रीय खुफिया एजेंसी जैसे यू.एस. राष्ट्रीय सुरक्षा एजेंसी (एनएसए) के बजट के अन्दर होगी। ). लोगजाम लेखक अनुमान लगाते हैं कि व्यापक रूप से पुन: उपयोग किए गए 1024 डीएच प्राइम्स के खिलाफ पूर्व-गणना वैश्विक निगरानी प्रकटीकरण (2013-वर्तमान) में दावों के पीछे है कि एनएसए वर्तमान क्रिप्टोग्राफी को तोड़ने में सक्षम है।^[5]

संदर्भ

↑ A. J. Menezes; P. C. van Oorschot; S. A. Vanstone. "Chapter 8.4 ElGamal public-key encryption" (PDF). एप्लाइड क्रिप्टोग्राफी की पुस्तिका. CRC Press.
↑ Lam; Shparlinski; Wang; Xing (2001). Lam, Kwok-Yan; Shparlinski, Igor; Wang, Huaxiong; Xing, Chaoping (eds.). क्रिप्टोग्राफी और कम्प्यूटेशनल संख्या सिद्धांत. Progress in Computer Science and Applied Logic (in English) (1st ed.). Birkhäuser Basel. pp. 54–56. doi:10.1007/978-3-0348-8295-8. eISSN 2297-0584. ISBN 978-3-7643-6510-3. ISSN 2297-0576.
↑ Shor, Peter (1997). "प्राइम फैक्टराइजेशन के लिए बहुपद-समय एल्गोरिदम और क्वांटम कंप्यूटर पर असतत लघुगणक". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/s0097539795293172. MR 1471990. S2CID 2337707.
↑ Blake, Ian F.; Garefalakis, Theo (2004-04-01). "असतत लघुगणक और डिफी-हेलमैन समस्याओं की जटिलता पर" (PDF). Journal of Complexity. Festschrift for Harald Niederreiter, Special Issue on Coding and Cryptography (in English). 20 (2): 148–170. doi:10.1016/j.jco.2004.01.002. ISSN 0885-064X. Archived from the original on 13 September 2022.
↑ ^5.0 ^5.1 ^5.2 Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew; Thomé, Emmanuel; Valenta, Luke; VanderSloot, Benjamin; Wustrow, Eric; Zanella-Béguelin, Santiago; Zimmermann, Paul (October 2015). "इम्परफेक्ट फॉरवर्ड सेक्रेसी: कैसे डिफी-हेलमैन व्यवहार में विफल रहता है" (PDF).
↑ Harkins, D.; Carrel, D. (November 1998). "इंटरनेट कुंजी एक्सचेंज (IKE)". Network Working Group (in English). doi:10.17487/RFC2409. ISSN 2070-1721.

Rosen, Kenneth H. (2011). Elementary Number Theory and Its Application (6th ed.). Pearson. p. 368. ISBN 978-0321500311.
Weisstein, Eric W. "Discrete Logarithm". MathWorld. Wolfram Web. Retrieved 1 January 2019.

अग्रिम पठन

Richard Crandall; Carl Pomerance. Chapter 5, Prime Numbers: A computational perspective, 2nd ed., Springer.
Stinson, Douglas Robert (2006), Cryptography: Theory and Practice (3rd ed.), London: CRC Press, ISBN 978-1-58488-508-5

यह भी देखें

एडब्ल्यू फैबर मॉडल 366
पर्सी लुडगेट और आयरिश लघुगणक

[1] A. J. Menezes; P. C. van Oorschot; S. A. Vanstone. "Chapter 8.4 ElGamal public-key encryption" (PDF). एप्लाइड क्रिप्टोग्राफी की पुस्तिका. CRC Press.

[:0-2] Lam; Shparlinski; Wang; Xing (2001). Lam, Kwok-Yan; Shparlinski, Igor; Wang, Huaxiong; Xing, Chaoping (eds.). क्रिप्टोग्राफी और कम्प्यूटेशनल संख्या सिद्धांत. Progress in Computer Science and Applied Logic (in English) (1st ed.). Birkhäuser Basel. pp. 54–56. doi:10.1007/978-3-0348-8295-8. eISSN 2297-0584. ISBN 978-3-7643-6510-3. ISSN 2297-0576.

[3] Shor, Peter (1997). "प्राइम फैक्टराइजेशन के लिए बहुपद-समय एल्गोरिदम और क्वांटम कंप्यूटर पर असतत लघुगणक". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/s0097539795293172. MR 1471990. S2CID 2337707.

[4] Blake, Ian F.; Garefalakis, Theo (2004-04-01). "असतत लघुगणक और डिफी-हेलमैन समस्याओं की जटिलता पर" (PDF). Journal of Complexity. Festschrift for Harald Niederreiter, Special Issue on Coding and Cryptography (in English). 20 (2): 148–170. doi:10.1016/j.jco.2004.01.002. ISSN 0885-064X. Archived from the original on 13 September 2022.

[imperfectfs-5] 5.0 ^5.1 ^5.2 Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew; Thomé, Emmanuel; Valenta, Luke; VanderSloot, Benjamin; Wustrow, Eric; Zanella-Béguelin, Santiago; Zimmermann, Paul (October 2015). "इम्परफेक्ट फॉरवर्ड सेक्रेसी: कैसे डिफी-हेलमैन व्यवहार में विफल रहता है" (PDF).

[6] Harkins, D.; Carrel, D. (November 1998). "इंटरनेट कुंजी एक्सचेंज (IKE)". Network Working Group (in English). doi:10.17487/RFC2409. ISSN 2070-1721.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 15: / Line 15: @@
 == उदाहरण ==
-=== 10 === की घातें
+'''10 की घातें'''
 की घातें हैं
@@ Line 21: / Line 21: @@
 इस सूची में किसी भी संख्या के लिए, कोई भी log<sub>10</sub> ''a'' की गणना कर सकता है। उदाहरण के लिए, log<sub>10</sub> 10000 = 4, और log<sub>10</sub> 0.001 = −3 । ये असतत लघुगणक समस्या के उदाहरण हैं।
-वास्तविक संख्या में अन्य आधार -10 लघुगणक असतत लघुगणक समस्या के उदाहरण नहीं हैं, क्योंकि उनमें गैर-पूर्णांक घातांक शामिल हैं। उदाहरण के लिए, समीकरण log<sub>10</sub> 53 = 1.724276… का अर्थ है कि 10<sup>1.724276…</sup> = 53। जबकि पूर्णांक घातांक को उत्पादों और व्युत्क्रमों का उपयोग करके किसी भी समूह में परिभाषित किया जा सकता है, स्वेच्छ वास्तविक घातांक, जैसे कि यह 1.724276…, अन्य अवधारणाओं जैसे घातीय फलन की आवश्यकता होती है।
+वास्तविक संख्या में अन्य आधार -10 लघुगणक असतत लघुगणक समस्या के उदाहरण नहीं हैं, क्योंकि उनमें गैर-पूर्णांक घातांक सम्मिलित हैं। उदाहरण के लिए, समीकरण log<sub>10</sub> 53 = 1.724276… का अर्थ है कि 10<sup>1.724276…</sup> = 53। जबकि पूर्णांक घातांक को उत्पादों और व्युत्क्रमों का उपयोग करके किसी भी समूह में परिभाषित किया जा सकता है, स्वेच्छ वास्तविक घातांक, जैसे कि यह 1.724276…, अन्य अवधारणाओं जैसे घातीय फलन की आवश्यकता होती है।
 समूह-सैद्धांतिक शर्तों में, 10 की घात के गुणा के तहत [[चक्रीय समूह]] G बनाती हैं, और 10 इस समूह के लिए जनक है। असतत लघुगणक लॉग<sub>10</sub>a को G में किसी भी a के लिए परिभाषित किया गया है।
@@ Line 32: / Line 32: @@
 असतत लघुगणक के लिए सबसे सरल सेटिंग्स में से एक समूह (Z)<sub>''p''</sub>)<sup>×</sup> है। यह गुणन [[मॉड्यूलर अंकगणित|सापेक्षर]] [[अभाज्य संख्या]] p का समूह है। इसके तत्व सर्वांगसमता वर्ग सापेक्ष p है, और दो तत्वों के समूह उत्पाद को तत्वों के साधारण पूर्णांक गुणन द्वारा प्राप्त किया जा सकता है, जिसके बाद कमी सापेक्ष p की होता है।
-इस समूह में किसी एक संख्या के kवें [[घातांक]] की गणना उसकी kth घात को एक पूर्णांक के रूप में ज्ञात करके और फिर p द्वारा विभाजन के बाद शेषफल ज्ञात करके की जा सकती है। जब शामिल संख्याएं बड़ी होती हैं, तो गणना के दौरान सापेक्ष p को कई बार कम करना अधिक कुशल होता है। उपयोग किए गए विशिष्ट कलन विधि के बाद भी, इस ऑपरेशन को  [[मॉड्यूलर घातांक|सापेक्षर घातांक]] कहा जाता है। उदाहरण के लिए, ('Z'<sub>17</sub>)<sup>×</sup> पर विचार करें. इस समूह में, 3<sup>4</sup> की गणना करने के लिये  3<sup>4</sup> = 81 की गणना करें, और फिर 81 को 17 से भाग देकर शेषफल 13 प्राप्त होता है। इस प्रकार 3<sup>4</sup> = समूह में 13 (Z<sub>17</sub>)<sup>×</sup>.
+इस समूह में किसी एक संख्या के kवें [[घातांक]] की गणना उसकी kth घात को एक पूर्णांक के रूप में ज्ञात करके और फिर p द्वारा विभाजन के बाद शेषफल ज्ञात करके की जा सकती है। जब सम्मिलित संख्याएं बड़ी होती हैं, तो गणना के दौरान सापेक्ष p को कई बार कम करना अधिक कुशल होता है। उपयोग किए गए विशिष्ट कलन विधि के बाद भी, इस ऑपरेशन को  [[मॉड्यूलर घातांक|सापेक्षर घातांक]] कहा जाता है। उदाहरण के लिए, ('Z'<sub>17</sub>)<sup>×</sup> पर विचार करें. इस समूह में, 3<sup>4</sup> की गणना करने के लिये  3<sup>4</sup> = 81 की गणना करें, और फिर 81 को 17 से भाग देकर शेषफल 13 प्राप्त होता है। इस प्रकार 3<sup>4</sup> = समूह में 13 (Z<sub>17</sub>)<sup>×</sup>.
 असतत लघुगणक केवल व्युत्क्रम संक्रिया है। उदाहरण के लिए,  k के लिए समीकरण 3<sup>k</sup> ≡ 13 (mod 17) पर विचार करे। उपरोक्त उदाहरण से, एक समाधान k = 4 है, लेकिन यह एकमात्र समाधान नहीं है। चूंकि 3<sup>16</sup> ≡ 1 (मॉड 17)— फ़र्मा के छोटे प्रमेय से अनुसरण करता है—यह भी अनुसरण करता है कि यदि n एक पूर्णांक है तो 3<sup>4+16n</sup> ≡ 3<sup>4</sup> × (3<sup>16</sup>)<sup>n</sup> ≡ 13 × 1<sup>n</sup> ≡ 13 (मॉड 17)। अतः समीकरण के 4 + 16n रूप के अपरिमित रूप से अनेक हल हैं। इसके अतिरिक्त, क्योंकि 16 सबसे छोटा धनात्मक पूर्णांक m है जो 3<sup>m</sup> ≡ 1 (मॉड 17) को संतुष्ट करता है, यही एकमात्र समाधान हैं। समतुल्य रूप से, सभी संभावित समाधानों का सेट बाधा द्वारा व्यक्त किया जा सकता है कि k ≡ 4 (mod 16)।
@@ Line 60: / Line 60: @@
 == कलन विधि ==
 {{See also|असतत लघुगणक अभिलेख}}
-{{unsolved|computer science|Can the discrete logarithm be computed in polynomial time on a classical computer?}}
 असतत लघुगणक समस्या को अभिकलनीयतः रूप से असभ्य माना जाता है। यही है, सामान्य रूप से असतत कलन विधि की गणना के लिए कोई कुशल पारंपरिक कलन विधि ज्ञात नहीं है।
@@ Line 79: / Line 78: @@
 कुशल पारंपरिक कलन विधि भी कुछ विशेष स्थितियों में उपस्थित हैं। उदाहरण के लिए, पूर्णांक सापेक्ष p के समूह में जोड़ के तहत, घात ''b<sup>k</sup>'' एक उत्पाद ''bk'' बन जाता है, और समानता का मतलब पूर्णांकों में सर्वांगसम सापेक्ष p है। विस्तारित यूक्लिडियन कलन विधि k को जल्दी पाता है।
-Diffie–Hellman_key_exchange|Diffie–Hellman एक चक्रीय समूह मापांक के साथ a prime p का उपयोग किया जाता है, जिससे Pohlig–Hellman के साथ असतत लघुगणक की एक कुशल संगणना की अनुमति मिलती है यदि आदेश_(group_theory) (p−1 होना) पर्याप्त रूप से Smooth_number है, अर्थात कोई बड़ा नहीं है पूर्णांक कारककरण।
+डिफी-हेलमैन के साथ एक चक्रीय समूह मापांक एक प्रमुख p का उपयोग किया जाता है, जिससे पोहलिग-हेलमैन के साथ असतत लघुगणक की एक कुशल गणना की अनुमति मिलती है यदि समूह का क्रम (p-1 होना) पर्याप्त रूप से सुचारू है, अर्थात इसमें कोई बड़े प्रमुख कारक नहीं हैं।
 == पूर्णांक गुणनखंड के साथ तुलना ==
 असतत लघुगणक और पूर्णांक गुणनखंड की गणना करते समय अलग-अलग समस्याएं हैं, वे कुछ गुण साझा करते हैं:
-* दोनों परिमित [[एबेलियन समूह]]ों के लिए [[छिपी हुई उपसमूह समस्या]] के विशेष मामले हैं,
+* दोनों परिमित [[एबेलियन समूह|विनिमेय समूहों]] के लिए [[छिपी हुई उपसमूह समस्या]] के विशेष स्थिति हैं,
-*दोनों समस्याएं कठिन प्रतीत होती हैं (गैर-[[एक कंप्यूटर जितना]] के लिए कोई कुशल कलन विधि ज्ञात नहीं हैं),
+*दोनों समस्याएं कठिन प्रतीत होती हैं (गैर-[[एक कंप्यूटर जितना|एक संगणक जितना]] के लिए कोई कुशल कलन विधि ज्ञात नहीं हैं),
-*दोनों समस्याओं के लिए क्वांटम कंप्यूटरों पर कुशल कलन विधि ज्ञात हैं,
+*दोनों समस्याओं के लिए क्वांटम संगणकोण पर कुशल कलन विधि ज्ञात हैं,
-*एक समस्या के [[कलन विधि]] को अक्सर दूसरी समस्या के लिए अनुकूलित किया जाता है, और
+*एक समस्या के [[कलन विधि]] को अधिकांश दूसरी समस्या के लिए अनुकूलित किया जाता है, और
 *दोनों समस्याओं की कठिनाई का उपयोग विभिन्न [[क्रिप्टोग्राफी]] प्रणालियों के निर्माण के लिए किया गया है।
 == क्रिप्टोग्राफी ==
-ऐसे समूह उपस्थित हैं जिनके लिए असतत लघुगणक की गणना स्पष्ट रूप से कठिन है। कुछ स्थितियों में (उदाहरण के लिए समूहों के बड़े प्राइम ऑर्डर उपसमूह (Z<sub>''p''</sub>)<sup>×</sup>) सबसे खराब स्थिति के लिए न केवल कोई कुशल कलन विधि ज्ञात है, बल्कि औसत-केस की जटिलता को [[यादृच्छिक स्व-न्यूनीकरण]] का उपयोग करके सबसे खराब स्थिति के रूप में दिखाया जा सकता है।<ref>{{Cite journal |last1=Blake |first1=Ian F. |last2=Garefalakis |first2=Theo |date=2004-04-01 |title=असतत लघुगणक और डिफी-हेलमैन समस्याओं की जटिलता पर|url=https://www.sciencedirect.com/science/article/pii/S0885064X04000056 |journal=Journal of Complexity |series=Festschrift for Harald Niederreiter, Special Issue on Coding and Cryptography |language=en |volume=20 |issue=2 |pages=148–170 |doi=10.1016/j.jco.2004.01.002 |issn=0885-064X |archive-url=https://www.dropbox.com/home/File%20requests?preview=On+the+complexity+of+the+discrete+logarithim+and+diffe-hellman+problems.pdf |archive-date=13 September 2022}}</ref>
+ऐसे समूह उपस्थित हैं जिनके लिए असतत लघुगणक की गणना स्पष्ट रूप से कठिन है। कुछ स्थितियों में (उदाहरण के लिए समूहों के बड़े प्रमुख क्रम उपसमूह (Z<sub>''p''</sub>)<sup>×</sup>) सबसे खराब स्थिति के लिए न केवल कोई कुशल कलन विधि ज्ञात है, बल्कि औसत-केस की जटिलता को [[यादृच्छिक स्व-न्यूनीकरण]] का उपयोग करके सबसे खराब स्थिति के रूप में दिखाया जा सकता है।<ref>{{Cite journal |last1=Blake |first1=Ian F. |last2=Garefalakis |first2=Theo |date=2004-04-01 |title=असतत लघुगणक और डिफी-हेलमैन समस्याओं की जटिलता पर|url=https://www.sciencedirect.com/science/article/pii/S0885064X04000056 |journal=Journal of Complexity |series=Festschrift for Harald Niederreiter, Special Issue on Coding and Cryptography |language=en |volume=20 |issue=2 |pages=148–170 |doi=10.1016/j.jco.2004.01.002 |issn=0885-064X |archive-url=https://www.dropbox.com/home/File%20requests?preview=On+the+complexity+of+the+discrete+logarithim+and+diffe-hellman+problems.pdf |archive-date=13 September 2022}}</ref>
-इसी समय, असतत घातांक की व्युत्क्रम समस्या कठिन नहीं है (उदाहरण के लिए, इसे वर्गाकार करके घातांक का उपयोग करके कुशलता से गणना की जा सकती है)। यह विषमता पूर्णांक गुणनखंडन और पूर्णांक गुणन के बीच की विषमता के समान है। क्रिप्टोग्राफ़िक सिस्टम के निर्माण में दोनों विषमताओं (और अन्य संभवतः एक तरफ़ा फ़ंक्शंस) का शोषण किया गया है।
-असतत लघुगणक क्रिप्टोग्राफी (डीएलसी) में समूह जी के लिए लोकप्रिय विकल्प चक्रीय समूह ('जेड') हैं<sub>''p''</sub>)<sup>×</sup> (उदाहरण के लिए [[ElGamal एन्क्रिप्शन]], Diffie–Hellman कुंजी विनिमय, और [[डिजिटल हस्ताक्षर एल्गोरिथम|डिजिटल हस्ताक्षर कलन विधि]]) और [[परिमित क्षेत्र]]ों पर दीर्घवृत्तीय वक्रों के चक्रीय उपसमूह ([[[[अण्डाकार वक्र]] क्रिप्टोग्राफी]] देखें)।
+इसी समय, असतत घातांक की व्युत्क्रम समस्या कठिन नहीं है (उदाहरण के लिए, इसे वर्गाकार करके घातांक का उपयोग करके कुशलता से गणना की जा सकती है)। यह विषमता पूर्णांक गुणनखंडन और पूर्णांक गुणन के बीच की विषमता के समान है। क्रिप्टोग्राफ़िक सिस्टम के निर्माण में दोनों विषमताओं (और अन्य संभवतः एक तरफ़ा फलन) का शोषण किया गया है।
-जबकि सामान्य रूप से असतत लघुगणक समस्या को हल करने के लिए कोई सार्वजनिक रूप से ज्ञात कलन विधि नहीं है, संख्या क्षेत्र छलनी कलन विधि के पहले तीन चरण केवल समूह G पर निर्भर करते हैं, न कि G के विशिष्ट तत्वों पर जिनका परिमित लॉग वांछित है। किसी विशिष्ट समूह के लिए इन तीन चरणों की पूर्वगणना करके, किसी को केवल अंतिम चरण को पूरा करने की आवश्यकता होती है, जो कि उस समूह में एक विशिष्ट लघुगणक प्राप्त करने के लिए पहले तीन की तुलना में बहुत कम कम्प्यूटेशनल रूप से महंगा है।<ref name=imperfectfs/>
+असतत लघुगणक क्रिप्टोग्राफी (डीएलसी) में समूह जी के लिए लोकप्रिय विकल्प चक्रीय समूह ('Z'<sub>''p''</sub>)<sup>×</sup> हैं, (उदाहरण के लिए [[ElGamal एन्क्रिप्शन|एलगमाल एन्क्रिप्शन]], डिफी-हेलमैन कुंजी विनिमय, और [[डिजिटल हस्ताक्षर एल्गोरिथम|डिजिटल हस्ताक्षर कलन विधि]]) और [[परिमित क्षेत्र|परिमित क्षेत्रों]] पर दीर्घवृत्तीय वक्रों के चक्रीय उपसमूह [[अण्डाकार वक्र]] क्रिप्टोग्राफी देखें)।
+जबकि सामान्य रूप से असतत लघुगणक समस्या को हल करने के लिए कोई सार्वजनिक रूप से ज्ञात कलन विधि नहीं है, संख्या क्षेत्र जाँच कलन विधि के पहले तीन चरण केवल समूह G पर निर्भर करते हैं, न कि G के विशिष्ट तत्वों पर जिनका परिमित log वांछित है। किसी विशिष्ट समूह के लिए इन तीन चरणों की पूर्वगणना करके, किसी को केवल अंतिम चरण को पूरा करने की आवश्यकता होती है, जो कि उस समूह में एक विशिष्ट लघुगणक प्राप्त करने के लिए पहले तीन की तुलना में बहुत कम अभिकलनीयतः रूप से महंगा है।<ref name="imperfectfs" />
 यह पता चला है कि बहुत अधिक इंटरनेट ट्रैफ़िक उन मुट्ठी भर समूहों में से एक का उपयोग करता है जो 1024 बिट्स या उससे कम क्रम के हैं, उदा। <nowiki>RFC 2409</nowiki> में निर्दिष्ट ओकली प्राइम्स के क्रम के साथ चक्रीय समूह।<ref>{{Cite journal |last1=Harkins |first1=D. |last2=Carrel |first2=D. |date=November 1998 |title=इंटरनेट कुंजी एक्सचेंज (IKE)|url=https://www.rfc-editor.org/rfc/rfc2409 |journal=Network Working Group |language=en |doi=10.17487/RFC2409 |issn=2070-1721}}</ref> लॉगजैम (कंप्यूटर सुरक्षा) हमले ने इस भेद्यता का उपयोग विभिन्न प्रकार की इंटरनेट सेवाओं से समझौता करने के लिए किया, जो उन समूहों के उपयोग की अनुमति देता है जिनका आदेश 512-बिट प्राइम नंबर था, जिसे [[क्रिप्टोग्राफी का निर्यात]] कहा जाता है।<ref name=imperfectfs/>
-लोगजाम (कंप्यूटर सुरक्षा) हमले के लेखकों का अनुमान है कि 1024-बिट प्राइम के लिए असतत लॉग समस्या को हल करने के लिए आवश्यक अधिक कठिन पूर्व-गणना एक बड़ी राष्ट्रीय [[खुफिया एजेंसी]] जैसे यू.एस. [[राष्ट्रीय सुरक्षा एजेंसी]] (एनएसए) के बजट के भीतर होगी। ). लोगजाम लेखक अनुमान लगाते हैं कि व्यापक रूप से पुन: उपयोग किए गए 1024 डीएच प्राइम्स के खिलाफ पूर्व-गणना वैश्विक निगरानी प्रकटीकरण (2013-वर्तमान) में दावों के पीछे है कि एनएसए वर्तमान क्रिप्टोग्राफी को तोड़ने में सक्षम है।<ref name=imperfectfs>{{cite web |last1=Adrian |first1=David |last2=Bhargavan |first2=Karthikeyan |last3=Durumeric |first3=Zakir |last4=Gaudry |first4=Pierrick |last5=Green |first5=Matthew |last6=Halderman |first6=J. Alex |last7=Heninger |first7=Nadia|author7-link= Nadia Heninger |last8=Springall |first8=Drew |last9=Thomé |first9=Emmanuel |last10=Valenta |first10=Luke |last11=VanderSloot |first11=Benjamin |last12=Wustrow |first12=Eric |last13=Zanella-Béguelin |first13=Santiago |last14=Zimmermann |first14=Paul  |title=इम्परफेक्ट फॉरवर्ड सेक्रेसी: कैसे डिफी-हेलमैन व्यवहार में विफल रहता है|url=https://weakdh.org/imperfect-forward-secrecy.pdf |date=October 2015}}</ref>
+लोगजाम (कंप्यूटर सुरक्षा) हमले के लेखकों का अनुमान है कि 1024-बिट प्राइम के लिए असतत लॉग समस्या को हल करने के लिए आवश्यक अधिक कठिन पूर्व-गणना एक बड़ी राष्ट्रीय [[खुफिया एजेंसी]] जैसे यू.एस. [[राष्ट्रीय सुरक्षा एजेंसी]] (एनएसए) के बजट के अन्दर होगी। ). लोगजाम लेखक अनुमान लगाते हैं कि व्यापक रूप से पुन: उपयोग किए गए 1024 डीएच प्राइम्स के खिलाफ पूर्व-गणना वैश्विक निगरानी प्रकटीकरण (2013-वर्तमान) में दावों के पीछे है कि एनएसए वर्तमान क्रिप्टोग्राफी को तोड़ने में सक्षम है।<ref name=imperfectfs>{{cite web |last1=Adrian |first1=David |last2=Bhargavan |first2=Karthikeyan |last3=Durumeric |first3=Zakir |last4=Gaudry |first4=Pierrick |last5=Green |first5=Matthew |last6=Halderman |first6=J. Alex |last7=Heninger |first7=Nadia|author7-link= Nadia Heninger |last8=Springall |first8=Drew |last9=Thomé |first9=Emmanuel |last10=Valenta |first10=Luke |last11=VanderSloot |first11=Benjamin |last12=Wustrow |first12=Eric |last13=Zanella-Béguelin |first13=Santiago |last14=Zimmermann |first14=Paul  |title=इम्परफेक्ट फॉरवर्ड सेक्रेसी: कैसे डिफी-हेलमैन व्यवहार में विफल रहता है|url=https://weakdh.org/imperfect-forward-secrecy.pdf |date=October 2015}}</ref>
@@ Line 121: / Line 121: @@
 {{Number theoretic algorithms}}
-{{Cryptography public-key}}
 {{Computational hardness assumptions}}
 {{DEFAULTSORT:Discrete Logarithm}}
-श्रेणी: सापेक्षर अंकगणित
+[[Category:Articles with hatnote templates targeting a nonexistent page|Discrete Logarithm]]
-श्रेणी:समूह सिद्धांत
+[[Category:Articles with short description|Discrete Logarithm]]
-श्रेणी:क्रिप्टोग्राफी
+[[Category:CS1 English-language sources (en)]]
-श्रेणी:लघुगणक
+[[Category:CS1 français-language sources (fr)|Discrete Logarithm]]
-श्रेणी: परिमित क्षेत्र
+[[Category:CS1 maint|Discrete Logarithm]]
-श्रेणी:कम्प्यूटेशनल कठोरता अनुमान
+[[Category:CS1 Ελληνικά-language sources (el)|Discrete Logarithm]]
-श्रेणी:कंप्यूटर विज्ञान में अनसुलझी समस्याएं
+[[Category:Citation Style 1 templates|W]]
+[[Category:Collapse templates|Discrete Logarithm]]
+[[Category:Created On 30/11/2022|Discrete Logarithm]]
-[[Category: Machine Translated Page]]
+[[Category:Machine Translated Page|Discrete Logarithm]]
-[[Category:Created On 30/11/2022]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Discrete Logarithm]]
+[[Category:Pages with script errors|Discrete Logarithm]]
+[[Category:Short description with empty Wikidata description|Discrete Logarithm]]
+[[Category:Sidebars with styles needing conversion|Discrete Logarithm]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates based on the Citation/CS1 Lua module|Discrete Logarithm]]
+[[Category:Templates generating COinS|Cite web]]
+[[Category:Templates generating microformats|Discrete Logarithm]]
+[[Category:Templates that are not mobile friendly|Discrete Logarithm]]
+[[Category:Templates used by AutoWikiBrowser|Cite web]]
+[[Category:Templates using TemplateData|Discrete Logarithm]]
+[[Category:Wikipedia fully protected templates|Cite web]]
+[[Category:Wikipedia metatemplates|Discrete Logarithm]]

v t e संख्या-सिद्धांत एल्गोरिथ्म
प्राइमैलिटी टेस्ट	AKS अप्रैल BAILLIE -PSW अण्डाकार वक्र पॉकलिंगटन Fermat लुकास लुकास -लेहमेर लुकास -लेहमेर -रेज़ल ' प्रोथ का प्रमेय पेपिन का द्विघात फ्रोबेनियस सोलोवे -स्ट्रासेन मिलर -रबिन
प्राइम-जनरेटिंग	एटकिन की छलनी एरातोस्टेनेस की छलनी प्रिचर्ड की छलनी सुंदरम की छलनी पहिया कारक
पूर्णांक कारक	निरंतर अंश कारक। निरंतर अंश (CFRAC) डिक्सन Lenstra अण्डाकार-वक्र कारक Euler's पोलार्ड्स आरएचओ P - 1 पी + 1 द्विघात छलनी (क्यूएस) सामान्य संख्या क्षेत्र छलनी (GNFS) विशेष संख्या क्षेत्र छलनी (SNFS) तर्कसंगत छलनी फर्माट शैंक्स स्क्वायर फॉर्म ट्रायल डिवीजन शोर
गुणा	प्राचीन मिस्र लंबा करत्सुबा टूम - कुक Schönhage - Strassen Für's
Euclidean डिवीजन	बाइनरी चंकिंग फूरियर Goldschmidt न्यूटन-रफसन लंबा छोटा SRT
असतत लघुगणक	बेबी-स्टेप विशाल-चरण पोलार्ड रो पोलार्ड कंगारू Pohlig -Hellman इंडेक्स कैलकुलस फ़ंक्शन फ़ील्ड छलनी
महत्तम सामान्य भाजक	बाइनरी Euclidean विस्तारित यूक्लिडियन लेहमर
मॉड्यूलर वर्गमूल	Cipolla पॉकलिंगटन तनेली -शंक Berlekamp कुनरथ
अन्य एल्गोरिदम	चक्रवाला कॉर्नचिया वर्ग द्वारा घातक पूर्णांक वर्गमूल पूर्णांक संबंध मॉड्यूलर घातांक मोंटगोमरी में कमी शूफ़ ट्रेचेनबर्ग सिस्टम
इटैलिक इंगित करता है कि एल्गोरिथ्म विशेष रूपों की संख्या के लिए है

v t e कम्प्यूटेशनल कठोरता धारणाएं
संख्या सिद्धांत	पूर्णांक कारक फी-छिपा आरएसए समस्या मजबूत आरएसए द्विघात अवशेष निर्णायक समग्र अवशेष उच्च अवशेष
समूह सिद्धांत	असतत लॉगरिथम डिफी-हेलमैन निर्णायक डिफी -हेलमैन कम्प्यूटेशनल डिफी -हेलमैन
जोड़ियां	बाहरी diffie -hellman उप-समूह छिपा हुआ निर्णय रैखिक
जाली	सबसे छोटा वेक्टर समस्या निकटतम वेक्टर समस्या ( GAP त्रुटियों के साथ सीखना त्रुटियों के साथ रिंग सीखना लघु पूर्णांक समाधान
गैर-क्रिप्टोग्राफ़िक	घातीय समय परिकल्पना अद्वितीय खेल अनुमान लगाए गए क्लिक कॉनजेक्चर

Anonymous

Search

असतत लघुगणक: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 15:10, 26 December 2022

Contents

परिभाषा