मान लें G n तत्वों के साथ एक परिमित चक्रीय समुच्चय है। यह मानता है कि समूह गुणात्मक रूप से लिखा गया है। मान लें b G का एक जनरेटर है और इस प्रकार G के प्रत्येक तत्व g को g = bk के रूप में किसी पूर्णांक k के लिए लिखा जा सकता है।
इसके अलावा, g को परिभाषित करने वाले ऐसे कोई भी दो पूर्णांक n मॉड्यूलो सर्वांगसम होंगे। यह एक फ़ंक्शन logb: G → Zn (जहां Zn n मॉड्यूलो पूर्णांकों की रिंग को इंगित करता है) को k के सर्वांगसमता वर्ग को n मॉड्यूलो द्वारा g को असाइन करके दर्शा सकता है। यह फ़ंक्शन एक समूह आइसोमोर्फिज्म है जिसे आधार b के लिए डिस्क्रीट एल्गोरिदम के रूप में जाना जाता है।
गणित में, विशेष रूप से अमूर्त बीजगणित और इसके अनुप्रयोगों में, डिस्क्रीट लॉगरिदम सामान्य एल्गोरिदम के समुच्चय-सैद्धांतिक अनुरूप हैं। विशेष रूप से, एक सामान्य एल्गोरिदम loga(b) वास्तविक या जटिल संख्या पर समीकरण ax = b का एक समाधान है।
समान रूप से यदि g और h एक परिमित चक्रीय समूह G के तत्व हैं तो समीकरण gx = h का एक समाधान x, समूह G में h के आधार g के डिस्क्रीट लॉगरिदम के रूप में जाना जाता है।
डिस्क्रीट लॉग का संख्या सिद्धांत में एक बड़ा इतिहास है। मूल रूप से, उनका उपयोग परिमित क्षेत्र में गणनाओं में मूल रूप से किया जाता था। हालांकि, वे पूर्णांक गुणनखंड समस्या (IFP) की तरह ही अस्पष्ट थे।
सार्वजनिक-कुंजी क्रिप्टोसिस्टम के कार्यान्वयन के लिए आवश्यक सबसे महत्वपूर्ण उपकरण डिस्क्रीट लॉग समस्या (DLP) है। कुछ लोकप्रिय आधुनिक क्रिप्टो-एल्गोरिदम अपनी सुरक्षा को DLP की जटिलता पर आधारित करते हैं। डिफी-हेलमैन ने 1976 में प्रसिद्ध डिफी-हेलमैन कुंजी समझौता योजना का सुझाव दिया।
उदाहरण
डिस्क्रीट लॉगरिदम समूह (Zp) में सीखने में सबसे आसान हैं। यह मॉड्यूलो गुणन के तहत सर्वांगसमता वर्गों (1,..., p-1) का समूह है, अभाज्य p।
यदि इस समूह में संख्याओं में से एक की k-वें घात को खोजने की आवश्यकता है, तो यह इसे एक पूर्णांक के रूप में इसकी k-वें घात को खोजकर और फिर p से विभाजन के बाद शेष खोजकर कर सकता है।
इस प्रक्रिया को डिस्क्रीट एक्सपोनेंशिएशन के रूप में जाना जाता है।
उदाहरण के लिए, (Z17)x पर विचार करें। इस समूह में 34 की गणना करने के लिए, यह पहले 34 = 81 की गणना कर सकता है, और फिर यह 81 को 17 से विभाजित कर 13 का शेष प्राप्त कर सकता है।
इसलिए, 34 = 13 समूह (Z17)x में। डिस्क्रीट लॉगरिदम केवल व्युत्क्रम संक्रिया है। उदाहरण के लिए, यह k के लिए समीकरण 3k = 13 (mod 17) ले सकता है।
इसमें k = 4 एक समाधान है। चूंकि 316 ≡ 1(mod 17), यह भी अनुसरण करता है कि यदि n एक पूर्णांक है तो 34+16n ≡ 13 x 1n ≡ 13 (mod 17)।
इसलिए, समीकरण के 4 + 16n के रूप में अनंत समाधान हैं। इसके अलावा, क्योंकि 16 सबसे छोटा धनात्मक पूर्णांक m है जो 3m ≡ 1 (mod 17) को संतुष्ट करता है, यानी, 16, (Z17)x में 3 का क्रम है, ये केवल समाधान हैं। इसी तरह, समाधान को k ≡ 4 (mod)16 के रूप में परिभाषित किया जा सकता है।
सामान्य डिस्क्रीट लॉगरिदम logbg की गणना के लिए कोई कुशल एल्गोरिदम ज्ञात नहीं है।
