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