असतत लघुगणक

गणित में, दी गई वास्तविक संख्याओं 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 का एक अभाज्य मूल है।

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

परिभाषा

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

$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.$

कलन विधि

See also: असतत लघुगणक अभिलेख

Unsolved problem in computer science:

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

(more unsolved problems in computer science)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

यह पता चला है कि बहुत अधिक इंटरनेट ट्रैफ़िक उन मुट्ठी भर समूहों में से एक का उपयोग करता है जो 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
• पर्सी लुडगेट और आयरिश लघुगणक

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