आदिम मूल (Primitive Root) की अवधारणा
संख्या सिद्धांत और क्रिप्टोग्राफी में, मॉड्यूलो n का आदिम मूल (Primitive Root) एक पूर्णांक g होता है जिसके घात (powers) मॉड्यूलो n सभी संख्याएं उत्पन्न करते हैं जो n के सहअभाज्य (coprime) हैं।
गणितीय परिभाषा
एक पूर्णांक g मॉड्यूलो n का आदिम मूल है यदि प्रत्येक पूर्णांक a जो n के सहअभाज्य है, के लिए एक पूर्णांक k मौजूद है जैसे कि:
gk ≡ a (mod n)
महत्वपूर्ण गुण
- केवल 1, 2, 4, pk, 2pk (जहां p विषम अभाज्य है) के लिए आदिम मूल मौजूद होते हैं
- यदि g आदिम मूल है, तो इसकी क्रम (order) φ(n) होता है (यूलर टॉशिएंट फंक्शन)
- आदिम मूलों की संख्या φ(φ(n)) होती है
उदाहरण
11 के आदिम मूल: 2, 6, 7, 8
13 के आदिम मूल: 2, 6, 7, 11
17 के आदिम मूल: 3, 5, 6, 7, 10, 11, 12, 14
नेटवर्क सुरक्षा में अनुप्रयोग
डिफी-हेलमैन कुंजी विनिमय: आदिम मूल जनरेटर के रूप में उपयोग किए जाते हैं
एलगामल एन्क्रिप्शन: सार्वजनिक कुंजी क्रिप्टोसिस्टम में आधार के रूप में
डिजिटल हस्ताक्षर एल्गोरिदम (DSA): डोमेन पैरामीटर जनरेशन में
आदिम मूल ढूंढने की विधि
- φ(n) की गणना करें
- φ(n) के अभाज्य गुणनखंड ढूंढें
- उम्मीदवार g = 2, 3, 4... के लिए परीक्षण करें: gφ(n)/q ≢ 1 (mod n) सभी अभाज्य गुणनखंड q के लिए
- पहला g जो पास करे, वह आदिम मूल है