असतत लघुगणक

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

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

परिभाषा

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

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

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

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

उदाहरण

=== 10 === की शक्तियाँ

10 की शक्तियाँ हैं

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

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

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

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

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

इसी तरह का उदाहरण किसी भी गैर-शून्य वास्तविक संख्या b के लिए है। घात एक गुणात्मक उपसमूह G = {…, b बनाते हैं^-3, बी^-2, बी^{-1</सुप>, 1, बी1</सुप>, बी2, बी3, …} अशून्य वास्तविक संख्याओं का। G के किसी भी अवयव a के लिए log की गणना की जा सकती है_bएक।}

मॉड्यूलर अंकगणित

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

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

असतत लघुगणक केवल व्युत्क्रम संक्रिया है। उदाहरण के लिए, समीकरण 3 पर विचार करें^k ≡ 13 (mod 17) k के लिए। ऊपर दिए गए उदाहरण से, एक समाधान 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 है, असतत लघुगणक लॉग_ba 1 के अलावा अन्य के लिए अपरिभाषित है, और प्रत्येक पूर्णांक k = 1 के लिए असतत लघुगणक है।

गुण

घात सामान्य बीजगणितीय सर्वसमिका का पालन करते हैं b^{के + एल} = बी^{क</सुप> खएल</सुप>.दूसरे शब्दों में, समारोह}

$f\colon \mathbf {Z} \to G$

एफ (के) = बी द्वारा परिभाषित^k पूर्णांकों 'Z' से एक समूह समरूपता है, जो G के उपसमूह H के उपसमूह के अंतर्गत b द्वारा एक समूह का समूह उत्पन्न करता है। एच में सभी के लिए, लॉग इन करें_bएक मौजूद है। इसके विपरीत लॉग करें_ba का अस्तित्व नहीं है a के लिए जो H में नहीं है।

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

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

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

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

जहां जेड_n पूर्णांक मॉड्यूलो n के योज्य समूह को दर्शाता है।

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

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

एल्गोरिदम

See also: Discrete logarithm records

Unsolved problem in computer science:

Can the discrete logarithm be computed in polynomial time on a classical computer?

(more unsolved problems in computer science)

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

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

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

• बेबी-स्टेप जाइंट-स्टेप
• समारोह क्षेत्र चलनी
• इंडेक्स कैलकुलस एल्गोरिथम
• संख्या क्षेत्र छलनी
• पोहलिग-हेलमैन एल्गोरिथम
• लॉगरिदम के लिए पोलार्ड का आरओ एल्गोरिथम
• पोलार्ड का कंगारू एल्गोरिथम (उर्फ पोलार्ड का लैम्ब्डा एल्गोरिथम)

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

Diffie–Hellman_key_exchange|Diffie–Hellman एक चक्रीय समूह मापांक के साथ a prime p का उपयोग किया जाता है, जिससे Pohlig–Hellman के साथ असतत लघुगणक की एक कुशल संगणना की अनुमति मिलती है यदि आदेश_(group_theory) (p−1 होना) पर्याप्त रूप से Smooth_number है, अर्थात कोई बड़ा नहीं है पूर्णांक कारककरण।

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

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

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

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

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

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

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

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

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

संदर्भ

• 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
• पर्सी लुडगेट और आयरिश लघुगणक

श्रेणी:मॉड्यूलर अंकगणित श्रेणी:समूह सिद्धांत श्रेणी:क्रिप्टोग्राफी श्रेणी:लघुगणक श्रेणी: परिमित क्षेत्र श्रेणी:कम्प्यूटेशनल कठोरता अनुमान श्रेणी:कंप्यूटर विज्ञान में अनसुलझी समस्याएं