असतत लघुगणक: Difference between revisions

Revision as of 07:34, 14 December 2022

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

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

परिभाषा

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

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 .

इस सूची में किसी भी संख्या के लिए, लॉग की गणना की जा सकती है₁₀एक। उदाहरण के लिए, लॉग करें₁₀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</सुप>, बी², बी³, …} अशून्य वास्तविक संख्याओं का। G के किसी भी अवयव a के लिए log की गणना की जा सकती है_bएक।}}

सापेक्षर अंकगणित

असतत लघुगणक के लिए सबसे सरल सेटिंग्स में से एक है पूर्णांकों का समूह गुणात्मक समूह n|(Z)_p)^×. यह गुणन सापेक्षर अंकगणित का समूह अभाज्य संख्या p है। इसके तत्व हैं Modular_arithmetic#Congruence_class सापेक्ष p, और दो तत्वों के समूह उत्पाद को तत्वों के साधारण पूर्णांक गुणन द्वारा प्राप्त किया जा सकता है, जिसके बाद घटाव सापेक्ष 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^{के + एल} = बी^{क</सुप> ख^{एल</सुप>.^[2]दूसरे शब्दों में, समारोह}}

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.

कलन विधि

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 के लिए व्यावहारिक है।

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

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

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

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

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

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

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

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

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

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

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

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

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

संदर्भ

↑ A. J. Menezes; P. C. van Oorschot; S. A. Vanstone. "Chapter 8.4 ElGamal public-key encryption" (PDF). एप्लाइड क्रिप्टोग्राफी की पुस्तिका. CRC Press.
↑ ^2.0 ^2.1 Lam; Shparlinski; Wang; Xing (2001). Lam, Kwok-Yan; Shparlinski, Igor; Wang, Huaxiong; Xing, Chaoping (eds.). क्रिप्टोग्राफी और कम्प्यूटेशनल संख्या सिद्धांत. Progress in Computer Science and Applied Logic (in English) (1st ed.). Birkhäuser Basel. pp. 54–56. doi:10.1007/978-3-0348-8295-8. eISSN 2297-0584. ISBN 978-3-7643-6510-3. ISSN 2297-0576.
↑ Shor, Peter (1997). "प्राइम फैक्टराइजेशन के लिए बहुपद-समय एल्गोरिदम और क्वांटम कंप्यूटर पर असतत लघुगणक". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/s0097539795293172. MR 1471990. S2CID 2337707.
↑ Blake, Ian F.; Garefalakis, Theo (2004-04-01). "असतत लघुगणक और डिफी-हेलमैन समस्याओं की जटिलता पर" (PDF). Journal of Complexity. Festschrift for Harald Niederreiter, Special Issue on Coding and Cryptography (in English). 20 (2): 148–170. doi:10.1016/j.jco.2004.01.002. ISSN 0885-064X. Archived from the original on 13 September 2022.
↑ ^5.0 ^5.1 ^5.2 Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew; Thomé, Emmanuel; Valenta, Luke; VanderSloot, Benjamin; Wustrow, Eric; Zanella-Béguelin, Santiago; Zimmermann, Paul (October 2015). "इम्परफेक्ट फॉरवर्ड सेक्रेसी: कैसे डिफी-हेलमैन व्यवहार में विफल रहता है" (PDF).
↑ Harkins, D.; Carrel, D. (November 1998). "इंटरनेट कुंजी एक्सचेंज (IKE)". Network Working Group (in English). doi:10.17487/RFC2409. ISSN 2070-1721.

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

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

[1] A. J. Menezes; P. C. van Oorschot; S. A. Vanstone. "Chapter 8.4 ElGamal public-key encryption" (PDF). एप्लाइड क्रिप्टोग्राफी की पुस्तिका. CRC Press.

[:0-2] 2.0 ^2.1 Lam; Shparlinski; Wang; Xing (2001). Lam, Kwok-Yan; Shparlinski, Igor; Wang, Huaxiong; Xing, Chaoping (eds.). क्रिप्टोग्राफी और कम्प्यूटेशनल संख्या सिद्धांत. Progress in Computer Science and Applied Logic (in English) (1st ed.). Birkhäuser Basel. pp. 54–56. doi:10.1007/978-3-0348-8295-8. eISSN 2297-0584. ISBN 978-3-7643-6510-3. ISSN 2297-0576.

[3] Shor, Peter (1997). "प्राइम फैक्टराइजेशन के लिए बहुपद-समय एल्गोरिदम और क्वांटम कंप्यूटर पर असतत लघुगणक". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/s0097539795293172. MR 1471990. S2CID 2337707.

[4] Blake, Ian F.; Garefalakis, Theo (2004-04-01). "असतत लघुगणक और डिफी-हेलमैन समस्याओं की जटिलता पर" (PDF). Journal of Complexity. Festschrift for Harald Niederreiter, Special Issue on Coding and Cryptography (in English). 20 (2): 148–170. doi:10.1016/j.jco.2004.01.002. ISSN 0885-064X. Archived from the original on 13 September 2022.

[imperfectfs-5] 5.0 ^5.1 ^5.2 Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew; Thomé, Emmanuel; Valenta, Luke; VanderSloot, Benjamin; Wustrow, Eric; Zanella-Béguelin, Santiago; Zimmermann, Paul (October 2015). "इम्परफेक्ट फॉरवर्ड सेक्रेसी: कैसे डिफी-हेलमैन व्यवहार में विफल रहता है" (PDF).

[6] Harkins, D.; Carrel, D. (November 1998). "इंटरनेट कुंजी एक्सचेंज (IKE)". Network Working Group (in English). doi:10.17487/RFC2409. ISSN 2070-1721.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 7: / Line 7: @@
 == परिभाषा ==
-माना G कोई समूह है। इसकी समूह संक्रिया को गुणन द्वारा और इसके तत्समक अवयव को 1 से निरूपित करें। मान लीजिए कि b, G का कोई अवयव है। किसी धनात्मक पूर्णांक k के लिए व्यंजक b<sup>k</sup> स्वयं k के साथ b का गुणनफल दर्शाता है:<ref name=":0">{{Cite book |last1=Lam |url=https://link.springer.com/book/10.1007/978-3-0348-8295-8 |title=क्रिप्टोग्राफी और कम्प्यूटेशनल संख्या सिद्धांत|last2=Shparlinski |last3=Wang |last4=Xing |editor-first1=Kwok-Yan |editor-first2=Igor |editor-first3=Huaxiong |editor-first4=Chaoping |editor-last1=Lam |editor-last2=Shparlinski |editor-last3=Wang |editor-last4=Xing |publisher=Birkhäuser Basel |isbn=978-3-7643-6510-3 |edition=1st |series=Progress in Computer Science and Applied Logic |year=2001 |pages=54–56 |language=en |doi=10.1007/978-3-0348-8295-8 |eissn=2297-0584 |issn=2297-0576}}</ref>
+माना G कोई समूह है। इसकी समूह संक्रिया को गुणन द्वारा और इसके सर्वसमता अवयव को 1 से निरूपित करें। मान लीजिए कि b, G का कोई अवयव है। किसी धनात्मक पूर्णांक k के लिए व्यंजक b<sup>k</sup> , b के गुणनफल को स्वयं k बार दर्शाता है:<ref name=":0">{{Cite book |last1=Lam |url=https://link.springer.com/book/10.1007/978-3-0348-8295-8 |title=क्रिप्टोग्राफी और कम्प्यूटेशनल संख्या सिद्धांत|last2=Shparlinski |last3=Wang |last4=Xing |editor-first1=Kwok-Yan |editor-first2=Igor |editor-first3=Huaxiong |editor-first4=Chaoping |editor-last1=Lam |editor-last2=Shparlinski |editor-last3=Wang |editor-last4=Xing |publisher=Birkhäuser Basel |isbn=978-3-7643-6510-3 |edition=1st |series=Progress in Computer Science and Applied Logic |year=2001 |pages=54–56 |language=en |doi=10.1007/978-3-0348-8295-8 |eissn=2297-0584 |issn=2297-0576}}</ref>
 :<math>b^k = \underbrace{b \cdot b \cdots b}_{k \; \text{factors}}.</math>
-इसी तरह, चलो बी<sup>−k</sup> b का गुणनफल दर्शाता है<sup>-1</sup> स्वयं के साथ k बार। के = 0 के लिए, केथ शक्ति पहचान तत्व है: {{nowrap|1=''b''<sup>0</sup> = 1}}.
+इसी तरह, b<sup>−k</sup> को ''b''<sup>−1</sup> के गुणनफल को स्वयं k बार दर्शाने दें।  k = 0 के लिए,  k वीं घात सर्वसमिका: {{nowrap|1=''b''<sup>0</sup> = 1}} है.
-मान लीजिए a भी G का एक अवयव है। एक पूर्णांक k जो समीकरण को हल करता है {{nowrap|1=''b''<sup>''k''</sup> = ''a''}} आधार ''b'' के लिए ''a'' का असतत लघुगणक (या बस लघुगणक, इस संदर्भ में) कहा जाता है। एक लिखता है ''क'' = लॉग<sub>''b''</sub>एक।
+मान लीजिए a भी G का एक अवयव है। एक पूर्णांक k जो समीकरण ''b<sup>k</sup>'' = ''a'' को हल करता है, a को आधार b के असतत लघुगणक (या इस संदर्भ में केवल लघुगणक) कहा जाता है। एक ''k'' = log<sub>''b''</sub> ''a'' लिखता है।
 == उदाहरण ==
-=== 10 === की शक्तियाँ
+=== 10 === की घातें
-की शक्तियाँ हैं
+की घातें हैं
 :<math>\ldots, 0.001, 0.01, 0.1, 1, 10, 100, 1000, \ldots.</math>
 इस सूची में किसी भी संख्या के लिए, लॉग की गणना की जा सकती है<sub>10</sub>एक। उदाहरण के लिए, लॉग करें<sub>10</sub>10000 = 4, और लॉग<sub>10</sub>0.001 = -3। ये असतत लघुगणक समस्या के उदाहरण हैं।
@@ Line 33: / Line 33: @@
 असतत लघुगणक के लिए सबसे सरल सेटिंग्स में से एक है पूर्णांकों का समूह गुणात्मक समूह n|(Z)<sub>''p''</sub>)<sup>×</sup>. यह गुणन  [[मॉड्यूलर अंकगणित|सापेक्षर अंकगणित]] का समूह [[अभाज्य संख्या]] p है। इसके तत्व हैं Modular_arithmetic#Congruence_class  सापेक्ष p, और दो तत्वों के समूह उत्पाद को तत्वों के साधारण पूर्णांक गुणन द्वारा प्राप्त किया जा सकता है, जिसके बाद घटाव  सापेक्ष p होता है।
-इस समूह में किसी एक संख्या के kवें [[घातांक]] की गणना उसकी kth शक्ति को एक पूर्णांक के रूप में ज्ञात करके और फिर p द्वारा विभाजन के बाद शेषफल ज्ञात करके की जा सकती है। जब शामिल संख्याएं बड़ी होती हैं, तो गणना के दौरान  सापेक्ष पी को कई बार कम करना अधिक कुशल होता है। उपयोग किए गए विशिष्ट कलन विधि के बावजूद, इस ऑपरेशन को  [[मॉड्यूलर घातांक|सापेक्षर घातांक]] कहा जाता है। उदाहरण के लिए, विचार करें ('Z'<sub>17</sub>)<sup>×</sup>. गणना करना 3<sup>4</sup> इस समूह में, 3 की गणना करें<sup>4</sup> = 81, और फिर 81 को 17 से भाग देकर शेषफल 13 प्राप्त होता है। इस प्रकार 3<sup>4</sup> = समूह में 13 (Z<sub>17</sub>)<sup>×</sup>.
+इस समूह में किसी एक संख्या के kवें [[घातांक]] की गणना उसकी kth घात को एक पूर्णांक के रूप में ज्ञात करके और फिर p द्वारा विभाजन के बाद शेषफल ज्ञात करके की जा सकती है। जब शामिल संख्याएं बड़ी होती हैं, तो गणना के दौरान  सापेक्ष पी को कई बार कम करना अधिक कुशल होता है। उपयोग किए गए विशिष्ट कलन विधि के बावजूद, इस ऑपरेशन को  [[मॉड्यूलर घातांक|सापेक्षर घातांक]] कहा जाता है। उदाहरण के लिए, विचार करें ('Z'<sub>17</sub>)<sup>×</sup>. गणना करना 3<sup>4</sup> इस समूह में, 3 की गणना करें<sup>4</sup> = 81, और फिर 81 को 17 से भाग देकर शेषफल 13 प्राप्त होता है। इस प्रकार 3<sup>4</sup> = समूह में 13 (Z<sub>17</sub>)<sup>×</sup>.
 असतत लघुगणक केवल व्युत्क्रम संक्रिया है। उदाहरण के लिए, समीकरण 3 पर विचार करें<sup>k</sup> ≡ 13 (mod 17) k के लिए। ऊपर दिए गए उदाहरण से, एक समाधान k = 4 है, लेकिन यह एकमात्र समाधान नहीं है। चूंकि 3<sup>16</sup> ≡ 1 (मॉड 17)—फर्मेट के छोटे प्रमेय से अनुसरण करता है—यह भी अनुसरण करता है कि यदि n एक पूर्णांक है तो 3<sup>4+16n</sup> ≡ 3<sup>4</sup> × (3<sup>16</sup>)<sup>n</sup> ≡ 13 × 1<sup>n</sup> ≡ 13 (मॉड 17)। अतः समीकरण के 4 + 16n रूप के अपरिमित रूप से अनेक हल हैं। इसके अलावा, क्योंकि 16 सबसे छोटा धनात्मक पूर्णांक m है जो 3 को संतुष्ट करता है<sup>m</sup> ≡ 1 (मॉड 17), यही एकमात्र समाधान हैं। समतुल्य रूप से, सभी संभावित समाधानों का सेट बाधा द्वारा व्यक्त किया जा सकता है कि k ≡ 4 (mod 16)।
-=== पहचान की शक्तियाँ ===
+=== पहचान की घातें ===
 विशेष मामले में जहां b समूह G का पहचान तत्व 1 है, असतत लघुगणक लॉग<sub>''b''</sub>a 1 के अलावा अन्य के लिए अपरिभाषित है, और प्रत्येक पूर्णांक k = 1 के लिए असतत लघुगणक है।
@@ Line 77: / Line 77: @@
 [[पीटर शोर]] के कारण एक कुशल शोर का कलन विधि है।<ref>{{cite journal |arxiv=quant-ph/9508027 |title=प्राइम फैक्टराइजेशन के लिए बहुपद-समय एल्गोरिदम और क्वांटम कंप्यूटर पर असतत लघुगणक|first=Peter |last=Shor |journal=SIAM Journal on Computing |volume=26 |issue=5 |year=1997 |pages=1484–1509 |doi=10.1137/s0097539795293172 | mr=1471990|s2cid=2337707 }}</ref>
-कुशल शास्त्रीय कलन विधि भी कुछ विशेष स्थितियों में मौजूद हैं। उदाहरण के लिए, पूर्णांक  सापेक्ष पी के समूह में इसके अतिरिक्त, शक्ति बी<sup>k</sup> एक गुणनफल bk बन जाता है, और समानता का अर्थ पूर्णांकों में सर्वांगसमता सापेक्ष p है। विस्तारित यूक्लिडियन एल्गोरिथम k को जल्दी पाता है।
+कुशल शास्त्रीय कलन विधि भी कुछ विशेष स्थितियों में मौजूद हैं। उदाहरण के लिए, पूर्णांक  सापेक्ष पी के समूह में इसके अतिरिक्त, घात बी<sup>k</sup> एक गुणनफल bk बन जाता है, और समानता का अर्थ पूर्णांकों में सर्वांगसमता सापेक्ष p है। विस्तारित यूक्लिडियन एल्गोरिथम k को जल्दी पाता है।
 Diffie–Hellman_key_exchange|Diffie–Hellman एक चक्रीय समूह मापांक के साथ a prime p का उपयोग किया जाता है, जिससे Pohlig–Hellman के साथ असतत लघुगणक की एक कुशल संगणना की अनुमति मिलती है यदि आदेश_(group_theory) (p−1 होना) पर्याप्त रूप से Smooth_number है, अर्थात कोई बड़ा नहीं है पूर्णांक कारककरण।

v t e संख्या-सिद्धांत एल्गोरिथ्म
प्राइमैलिटी टेस्ट	AKS अप्रैल BAILLIE -PSW अण्डाकार वक्र पॉकलिंगटन Fermat लुकास लुकास -लेहमेर लुकास -लेहमेर -रेज़ल ' प्रोथ का प्रमेय पेपिन का द्विघात फ्रोबेनियस सोलोवे -स्ट्रासेन मिलर -रबिन
प्राइम-जनरेटिंग	एटकिन की छलनी एरातोस्टेनेस की छलनी प्रिचर्ड की छलनी सुंदरम की छलनी पहिया कारक
पूर्णांक कारक	निरंतर अंश कारक। निरंतर अंश (CFRAC) डिक्सन Lenstra अण्डाकार-वक्र कारक Euler's पोलार्ड्स आरएचओ P - 1 पी + 1 द्विघात छलनी (क्यूएस) सामान्य संख्या क्षेत्र छलनी (GNFS) विशेष संख्या क्षेत्र छलनी (SNFS) तर्कसंगत छलनी फर्माट शैंक्स स्क्वायर फॉर्म ट्रायल डिवीजन शोर
गुणा	प्राचीन मिस्र लंबा करत्सुबा टूम - कुक Schönhage - Strassen Für's
Euclidean डिवीजन	बाइनरी चंकिंग फूरियर Goldschmidt न्यूटन-रफसन लंबा छोटा SRT
असतत लघुगणक	बेबी-स्टेप विशाल-चरण पोलार्ड रो पोलार्ड कंगारू Pohlig -Hellman इंडेक्स कैलकुलस फ़ंक्शन फ़ील्ड छलनी
महत्तम सामान्य भाजक	बाइनरी Euclidean विस्तारित यूक्लिडियन लेहमर
मॉड्यूलर वर्गमूल	Cipolla पॉकलिंगटन तनेली -शंक Berlekamp कुनरथ
अन्य एल्गोरिदम	चक्रवाला कॉर्नचिया वर्ग द्वारा घातक पूर्णांक वर्गमूल पूर्णांक संबंध मॉड्यूलर घातांक मोंटगोमरी में कमी शूफ़ ट्रेचेनबर्ग सिस्टम
इटैलिक इंगित करता है कि एल्गोरिथ्म विशेष रूपों की संख्या के लिए है

v t e कम्प्यूटेशनल कठोरता धारणाएं
संख्या सिद्धांत	पूर्णांक कारक फी-छिपा आरएसए समस्या मजबूत आरएसए द्विघात अवशेष निर्णायक समग्र अवशेष उच्च अवशेष
समूह सिद्धांत	असतत लॉगरिथम डिफी-हेलमैन निर्णायक डिफी -हेलमैन कम्प्यूटेशनल डिफी -हेलमैन
जोड़ियां	बाहरी diffie -hellman उप-समूह छिपा हुआ निर्णय रैखिक
जाली	सबसे छोटा वेक्टर समस्या निकटतम वेक्टर समस्या ( GAP त्रुटियों के साथ सीखना त्रुटियों के साथ रिंग सीखना लघु पूर्णांक समाधान
गैर-क्रिप्टोग्राफ़िक	घातीय समय परिकल्पना अद्वितीय खेल अनुमान लगाए गए क्लिक कॉनजेक्चर

Anonymous

Search

असतत लघुगणक: Difference between revisions

Namespaces

More

Page actions

Revision as of 07:34, 14 December 2022

Contents

परिभाषा