ब्रूट-फोर्स सर्च: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Problem-solving technique and algorithmic paradigm}} | {{Short description|Problem-solving technique and algorithmic paradigm}} | ||
{{about|कंप्यूटर विज्ञान में समस्या समाधान तकनीक|अन्य विषयों में इसी प्रकार नामित विधियाँ|पाशविक शक्ति (असंबद्धता)}} | {{about|कंप्यूटर विज्ञान में समस्या समाधान तकनीक|अन्य विषयों में इसी प्रकार नामित विधियाँ|पाशविक शक्ति (असंबद्धता)}} | ||
[[कंप्यूटर विज्ञान]] में, ब्रूट-फोर्स सर्च या | [[कंप्यूटर विज्ञान]] में, पाशविक बल खोज(ब्रूट-फोर्स सर्च) या विस्तृत खोज , जिसे उत्पन्न(जेनरेट) और परीक्षण के रूप में भी जाना जाता है, बहुत ही सामान्य समस्या-समाधान तकनीक और [[एल्गोरिथम प्रतिमान]] है जिसमें समाधान के लिए सभी संभावित प्रत्याशियों की व्यवस्थित रूप से गणना करना और यह जांचना सम्मिलित है कि प्रत्येक प्रत्याशी समस्या के बयान को संतुष्ट करता है या नहीं करता है। | ||
एक ब्रूट-फोर्स एल्गोरिथ्म जो [[प्राकृतिक संख्या]] ''n'' के [[भाजक|विभाजकों]] को खोजता है, 1 से n तक सभी पूर्णांकों की गणना करेगा, और जाँच करेगा कि क्या उनमें से प्रत्येक | एक पाशविक बल(ब्रूट-फोर्स) एल्गोरिथ्म जो [[प्राकृतिक संख्या]] ''n'' के [[भाजक|विभाजकों]] को खोजता है, यह 1 से n तक सभी पूर्णांकों की गणना करेगा, और जाँच करेगा कि कि क्या उनमें से प्रत्येक बिना शेष के n को विभाजित करता है। आठ रानियों की पहेली के लिए पाशविक बल अथवा ब्रूट-फोर्स अथवा पाशविक बल दृष्टिकोण 64-वर्ग शतरंज की बिसात पर 8 टुकड़ों की सभी संभावित व्यवस्थाओं की जांच करेगा और प्रत्येक व्यवस्था के लिए यह जांच करेगा कि प्रत्येक (रानी) टुकड़ा किसी अन्य पर हमला कर सकता है या नहीं कर सकता है ।<ref>{{Cite web|date=2020-01-06|title=ब्रूट फ़ोर्स एल्गोरिदम समझाया गया|url=https://www.freecodecamp.org/news/brute-force-algorithms-explained/|access-date=2021-04-11|website=freeCodeCamp.org|language=en}}</ref> | ||
यद्यपि पाशविक बल खोज [[ सॉफ़्टवेयर |सॉफ़्टवेयर]] को लागू करना आसान है और यदि यह मौजूद है तो हमेशा एक समाधान मिलेगा, कार्यान्वयन लागत उम्मीदवार समाधानों की संख्या के अनुपात में होती है{{snd}}जो कई व्यावहारिक समस्याओं में समस्या के आकार के बढ़ने पर बहुत तेज़ी से बढ़ने लगती है ('''#Combinatorial विस्फोट|''' §संयुक्त विस्फोट)।<ref>{{cite web |title=क्रूर बल खोज की जटिलता|url=https://www.coursera.org/learn/ml-clustering-and-retrieval/lecture/5R6q3/complexity-of-brute-force-search |website=coursera |access-date=14 June 2018}}</ref> इसलिए, पाशविक बल खोज का उपयोग आमतौर पर तब किया जाता है जब समस्या का आकार सीमित होता है, या जब समस्या-विशिष्ट अनुमानिकीय '''(कंप्यूटर साइंस)''' होते हैं, जिनका उपयोग प्रत्याशी के समाधान के समुच्चय को प्रबंधनीय आकार में कम करने के लिए किया जा सकता है। विधि का उपयोग तब भी किया जाता है जब कार्यान्वयन की सरलता गति से अधिक महत्वपूर्ण होती है। | |||
== | यह एकव प्रकार का मामला है, उदाहरण के लिए, महत्वपूर्ण अनुप्रयोगों में जहां [[कलन विधि]] में किसी भी त्रुटि के बहुत गंभीर परिणाम होंगे या जब गणितीय प्रमेय सिद्ध हो रहे हों। अन्य एल्गोरिदम या [[मेटाह्यूरिस्टिक|मेटाह्यूरिस्टिक्स]] को [[ बेंच मार्किंग |बेंच मार्किंग(मानकीकरण)]] करते समय पाशविक बल खोज आधारभूत विधि के रूप में भी उपयोगी होती है। दरअसल, पाशविक बल खोज को सबसे सरल मेटाह्यूरिस्टिक के रूप में देखा जा सकता है। ब्रूट फ़ोर्स खोज को [[ बैक ट्रैकिंग |बैक ट्रैकिंग]] के साथ भ्रमित नहीं होना चाहिए, जहां समाधानों के बड़े समुच्चयों ों को स्पष्ट रूप से गणना किए बिना त्याग दिया जा सकता है (जैसा कि ऊपर आठ रानियों की समस्या के पाठ्यपुस्तक कंप्यूटर समाधान में है)। किसी तालिका में किसी आइटम को खोजने के लिए पाशविक बल विधि{{snd}}अर्थात्, बाद की सभी प्रविष्टियों की जाँच करें, क्रमिक रूप से '''जाँच करें'''{{snd}}रेखीय खोज कहा जाता है। | ||
== पाशविक बल खोज को कार्यान्वित करना == | |||
=== बेसिक एल्गोरिथम === | === बेसिक एल्गोरिथम === | ||
क्रम में वर्तमान के बाद | क्रम में वर्तमान के बाद P के लिए प्रत्याशी c। | ||
# वैध ( | # वैध (P, c): जांचें कि प्रत्याशी c P के लिए समाधान है या नहीं है। | ||
# आउटपुट ( | # आउटपुट (P, c): आवेदन के लिए उपयुक्त के रूप में P के समाधान c का उपयोग करें। | ||
अगली प्रक्रिया को यह भी बताना होगा कि वर्तमान | अगली प्रक्रिया को यह भी बताना होगा कि वर्तमान c के बाद P के लिए कोई और प्रत्याशी नहीं हैं। ऐसा करने का सुविधाजनक तरीका "अशक्त प्रत्याशी" को वापस करना है, कुछ पारंपरिक डेटा मान Λ जो कि किसी भी वास्तविक प्रत्याशी से अलग है। इसी प्रकार पहली प्रक्रिया को Λ वापस करना चाहिए यदि उदाहरण P के लिए कोई प्रत्याशी नहीं हैं। ब्रूट-बल विधि तब एल्गोरिदम द्वारा व्यक्त की जाती है:<syntaxhighlight> | ||
c ← first(P) | |||
while c ≠ Λ do | |||
if valid(P,c) then | |||
output(P, c) | |||
c ← next(P, c) | |||
end while | |||
</syntaxhighlight> | |||
उदाहरण के लिए, जब पूर्णांक n के भाजक की | उदाहरण के लिए, जब पूर्णांक n के भाजक की खोज की जाती है, तो उदाहरण डेटा P संख्या n होता है। पहली पुकार (n) को पूर्णांक 1 वापस करना चाहिए यदि n ≥ 1, या Λ अन्यथा; अगली पुकार (n, c) को c + 1 वापस करना चाहिए यदि c <n, और Λ अन्यथा; और वैध (n, c) को 'सत्य' वापस करना चाहिए अगर और केवल अगर c , n का विभाजक है। (वास्तव में, यदि हम Λ को n + 1 चुनते हैं, तो परीक्षण n ≥ 1 और c <n अनावश्यक हैं।) उपरोक्त पाशविक बल खोज एल्गोरिदम प्रत्येक प्रत्याशी के लिए आउटपुट पुकार करेगा जो दिए गए उदाहरण P का समाधान है। पहला समाधान, या निर्दिष्ट संख्या में समाधान या उम्मीदवारों की निर्दिष्ट संख्या का परीक्षण करने के बाद या सीपीयू समय की एक निश्चित राशि खर्च करने के बाद एल्गोरिथ्म को रोकने के लिए आसानी से संशोधित किया जाता है। | ||
== मिश्रित विस्फोट == | == मिश्रित विस्फोट == | ||
पाशविक बल पद्धति का मुख्य हानि यह है कि, वास्तविक-विश्व की कई समस्याओं के लिए, प्राकृतिक प्रत्याशियों की संख्या निषेधात्मक रूप से बड़ी है। उदाहरण के लिए, यदि हम ऊपर वर्णित संख्या के विभाजक की खोज करते हैं, तो परीक्षण किए गए प्रत्याशियों की संख्या दी गई संख्या n होगी। इसलिए यदि n में 16 दशमलव अंक हैं, तो खोज के लिए कम से कम 10<sup>15</sup> कंप्यूटर निर्देश क्रियान्वित करने की आवश्यकता होगी '''कंप्यूटर निर्देश''', जिसमें विशिष्ट व्यक्तिगत कंप्यूटर पर कई दिन लगेंगे। यदि n यादृच्छिक 64-बाइनरी अंकों की प्राकृतिक संख्या है, जिसमें औसतन लगभग 19 दशमलव अंक हैं, तो खोज में लगभग 10 वर्ष लगेंगे। प्रत्याशियों की संख्या में यह तीव्र वृद्धि, जैसे-जैसे डेटा का आकार बढ़ता है, सभी प्रकार की समस्याओं में होता है। उदाहरण के लिए, यदि हम 10 अक्षरों की विशेष पुनर्व्यवस्था की मांग कर रहे हैं, तो हमारे पास 10 हैं! = 3,628,800 प्रत्याशियों पर विचार करने के लिए, जो विशिष्ट पीसी सेकंड से भी कम समय में उत्पन्न और परीक्षण कर सकता है। हालाँकि, और पत्र जोड़ना{{snd}}जो डेटा आकार में केवल 10% की वृद्धि है{{snd}}प्रत्याशियों की संख्या को 11 से गुणा कर देगा, 1000% की वृद्धि। 20 अक्षरों के लिए, प्रत्याशियों की संख्या 20! है, जो लगभग 2.4×10 है<sup>18</sup> या 2.4 [[क्विंटिलियन]]; और खोज में लगभग 10 वर्ष लगेंगे। इस अप्रिय घटना को आमतौर पर दहनशील विस्फोट या आयामीता का अभिशाप कहा जाता है। | |||
ऐसे मामले का उदाहरण जहां संयोजी जटिलता से विलेयता की सीमा हो जाती है, शतरंज को हल करने में है। शतरंज कोई [[सुलझा हुआ खेल]] नहीं है। 2005 में, छह पीस या उससे कम वाले सभी शतरंज के खेल को हल किया गया था, जो पूरी तरह से खेले जाने पर प्रत्येक स्थिति का परिणाम दिखाते थे। टेबलबेस को और शतरंज के टुकड़े के साथ पूरा करने में दस साल लग गए, इस प्रकार 7-टुकड़ा टेबलबेस पूरा हो गया। शतरंज के समापन में और टुकड़ा जोड़ना (इस प्रकार 8-टुकड़ा टेबलबेस बनाना) को जोड़ा संयोजन जटिलता के कारण अट्रैक्टिव माना जाता है।<ref>{{cite web |title=Is there a freely available online 7 piece Endgame tablebase? |url=https://chess.stackexchange.com/questions/5253/is-there-a-freely-available-online-7-piece-endgame-tablebase |website=Stack Exchange}}</ref><ref>{{cite web |title=लोमोनोसोव एंडगेम टेबलबेस|url=http://chessok.com/?page_id=27966 |website=ChessOK}}</ref> | ऐसे मामले का उदाहरण जहां संयोजी जटिलता से विलेयता की सीमा हो जाती है, शतरंज को हल करने में है। शतरंज कोई [[सुलझा हुआ खेल]] नहीं है। 2005 में, छह पीस या उससे कम वाले सभी शतरंज के खेल को हल किया गया था, जो पूरी तरह से खेले जाने पर प्रत्येक स्थिति का परिणाम दिखाते थे। टेबलबेस को और शतरंज के टुकड़े के साथ पूरा करने में दस साल लग गए, इस प्रकार 7-टुकड़ा टेबलबेस पूरा हो गया। शतरंज के समापन में और टुकड़ा जोड़ना (इस प्रकार 8-टुकड़ा टेबलबेस बनाना) को जोड़ा संयोजन जटिलता के कारण अट्रैक्टिव माना जाता है।<ref>{{cite web |title=Is there a freely available online 7 piece Endgame tablebase? |url=https://chess.stackexchange.com/questions/5253/is-there-a-freely-available-online-7-piece-endgame-tablebase |website=Stack Exchange}}</ref><ref>{{cite web |title=लोमोनोसोव एंडगेम टेबलबेस|url=http://chessok.com/?page_id=27966 |website=ChessOK}}</ref> | ||
== | == पाशविक बल खोजों को तेज करना == | ||
पाशविक बल एल्गोरिदम को गति देने का तरीका समस्या वर्ग के लिए विशिष्ट [[ अनुमानी |अनुमानी]] ्स का उपयोग करके, खोज स्थान को कम करना है, यानी प्रत्याशी समाधान का सेट। उदाहरण के लिए, आठ रानियों की पहेली में आठ रानियों को मानक शतरंज की [[बिसात]] पर रखने की चुनौती है ताकि कोई भी रानी किसी दूसरे पर हमला न करे। चूंकि प्रत्येक रानी को 64 वर्गों में से किसी में भी रखा जा सकता है, सिद्धांत रूप में 64 हैं<sup>8</sup> = 281,474,976,710,656 विचार करने की संभावनाएं। हालाँकि, क्योंकि रानियाँ सभी जैसी हैं, और कोई भी दो रानियाँ ही वर्ग पर नहीं रखी जा सकती हैं, प्रत्याशी सभी 64 वर्गों के समुच्चय से 8 वर्गों के संयोजन हैं; जिसका मतलब है कि 64 चुनें 8 = 64!/(56!*8!) = 4,426,165,368 प्रत्याशी समाधान{{snd}}पिछले अनुमान का लगभग 1/60,000। इसके अलावा, ही पंक्ति या ही स्तंभ पर दो रानियों के साथ कोई व्यवस्था समाधान नहीं हो सकती है। इसलिए, हम प्रत्याशियों के समुच्चय को उन व्यवस्थाओं तक सीमित कर सकते हैं। | |||
जैसा कि इस उदाहरण से पता चलता है, थोड़ा सा विश्लेषण अक्सर | जैसा कि इस उदाहरण से पता चलता है, थोड़ा सा विश्लेषण अक्सर प्रत्याशी समाधानों की संख्या में नाटकीय कमी लाएगा, और जटिल समस्या को तुच्छ में बदल सकता है। | ||
कुछ मामलों में, विश्लेषण | कुछ मामलों में, विश्लेषण प्रत्याशियों को सभी वैध समाधानों के समुच्चय तक कम कर सकता है; अर्थात्, यह एल्गोरिदम उत्पन्न कर सकता है जो परीक्षणों के साथ समय बर्बाद किए बिना और अमान्य प्रत्याशियों की पीढ़ी के बिना सभी वांछित समाधानों को सीधे गणना करता है (या उपयुक्त समाधान पाता है)। उदाहरण के लिए, समस्या के लिए 1 और 1,000,000 के बीच के सभी पूर्णांकों को खोजें जो समान रूप से 417 से विभाज्य हैं, भोली जानवर-बल समाधान श्रेणी में सभी पूर्णांक उत्पन्न करेगा, उनमें से प्रत्येक को विभाज्यता के लिए परीक्षण करेगा। हालाँकि, उस समस्या को 417 से शुरू करके और 1,000,000 से अधिक होने तक बार-बार 417 जोड़कर और अधिक कुशलता से हल किया जा सकता है{{snd}}जो केवल 2398 (= 1,000,000 ÷ 417) कदम उठाता है, और कोई परीक्षण नहीं करता है। | ||
== खोज स्थान को पुनर्क्रमित करना == | == खोज स्थान को पुनर्क्रमित करना == | ||
उन अनुप्रयोगों में जिन्हें सभी समाधानों के बजाय केवल समाधान की आवश्यकता होती है, ब्रूट फ़ोर्स खोज का अपेक्षित मान चलने का समय अक्सर उस क्रम पर निर्भर करेगा जिसमें | उन अनुप्रयोगों में जिन्हें सभी समाधानों के बजाय केवल समाधान की आवश्यकता होती है, ब्रूट फ़ोर्स खोज का अपेक्षित मान चलने का समय अक्सर उस क्रम पर निर्भर करेगा जिसमें प्रत्याशियों का परीक्षण किया जाता है। सामान्य नियम के रूप में, पहले सबसे होनहार प्रत्याशियों का परीक्षण करना चाहिए। उदाहरण के लिए, यादृच्छिक संख्या n के उचित विभाजक की खोज करते समय, 2 से बढ़ते क्रम में प्रत्याशी विभाजक की गणना करना बेहतर होता है {{nowrap|''n'' − 1}}, इसके विपरीत{{snd}}क्योंकि n के c से विभाज्य होने की संभावना 1/c है। इसके अलावा, प्रत्याशी के वैध होने की संभावना अक्सर पिछले असफल परीक्षणों से प्रभावित होती है। उदाहरण के लिए, दिए गए 1000-बिट स्ट्रिंग P में '1' बिट खोजने की समस्या पर विचार करें। इस मामले में, प्रत्याशी समाधान 1 से 1000 तक के सूचकांक हैं, और प्रत्याशी c मान्य है यदि P[c] = '1 '। अब, मान लीजिए कि P का पहला बिट '0' या '1' होने की समान संभावना है, लेकिन उसके बाद प्रत्येक बिट 90% संभावना के साथ पिछले के बराबर है। यदि प्रत्याशियों को बढ़ते क्रम में 1 से 1000 तक गिना जाता है, तो सफलता से पहले जांचे गए प्रत्याशियों की संख्या औसतन लगभग 6 होगी। दूसरी ओर, यदि प्रत्याशियों की गणना 1,11,21,31...991,2,12,22,32 आदि के क्रम में की जाती है, तो टी का अपेक्षित मूल्य 2 से थोड़ा ही अधिक होगा।अधिक आम तौर पर, खोज स्थान को इस तरह से गिना जाना चाहिए कि अगले प्रत्याशी के वैध होने की सबसे अधिक संभावना है, यह देखते हुए कि पिछले परीक्षण नहीं थे। इसलिए यदि वैध समाधानों को किसी अर्थ में क्लस्टर किए जाने की संभावना है, तो प्रत्येक नए प्रत्याशी को उसी अर्थ में पिछले वाले से जितना संभव हो उतना दूर होना चाहिए। निश्चित रूप से, यदि समाधान संयोग से अपेक्षा से अधिक समान रूप से फैले होने की संभावना है, तो निश्चित रूप से इसका विलोम होता है। | ||
== | == पाशविक बल खोज के विकल्प == | ||
कई अन्य खोज विधियाँ, या मेटाह्यूरिस्टिक्स हैं, जिन्हें समाधान के बारे में विभिन्न प्रकार के आंशिक ज्ञान का लाभ उठाने के लिए डिज़ाइन किया गया है। खोज के कुछ हिस्सों का शुरुआती कटऑफ़ बनाने के लिए ह्यूरिस्टिक्स का भी उपयोग किया जा सकता है। इसका उदाहरण गेम ट्री की खोज के लिए [[अल्पमहिष्ठ]] सिद्धांत है, जो खोज के प्रारंभिक चरण में कई सबट्री को हटा देता है। कुछ क्षेत्रों में, जैसे भाषा पार्सिंग, [[ चार्ट विश्लेषण |चार्ट विश्लेषण]] जैसी तकनीकें घातीय जटिलता समस्या को बहुपद जटिलता समस्या में कम करने के लिए समस्या में बाधाओं का फायदा उठा सकती हैं। कई मामलों में, जैसे कि [[बाधा संतुष्टि समस्या]]ओं में, [[बाधा प्रचार]] के माध्यम से खोज स्थान को नाटकीय रूप से कम कर सकते हैं, जो [[बाधा प्रोग्रामिंग]] भाषाओं में कुशलतापूर्वक कार्यान्वित किया जाता है। पूरी समस्या को सरलीकृत संस्करण के साथ बदलकर समस्याओं के लिए खोज स्थान को भी कम किया जा सकता है। उदाहरण के लिए, [[कंप्यूटर शतरंज]] में, खेल के शेष भाग के लिए सभी संभावित चालों के पूर्ण न्यूनतम वृक्ष की गणना करने के बजाय, न्यूनतम संभावनाओं के अधिक सीमित वृक्ष की गणना की जाती है, जिसमें पेड़ को निश्चित संख्या में चालों में काट दिया जाता है, और शेष [[मूल्यांकन समारोह]] द्वारा वृक्ष का अनुमान लगाया जा रहा है। | कई अन्य खोज विधियाँ, या मेटाह्यूरिस्टिक्स हैं, जिन्हें समाधान के बारे में विभिन्न प्रकार के आंशिक ज्ञान का लाभ उठाने के लिए डिज़ाइन किया गया है। खोज के कुछ हिस्सों का शुरुआती कटऑफ़ बनाने के लिए ह्यूरिस्टिक्स का भी उपयोग किया जा सकता है। इसका उदाहरण गेम ट्री की खोज के लिए [[अल्पमहिष्ठ]] सिद्धांत है, जो खोज के प्रारंभिक चरण में कई सबट्री को हटा देता है। कुछ क्षेत्रों में, जैसे भाषा पार्सिंग, [[ चार्ट विश्लेषण |चार्ट विश्लेषण]] जैसी तकनीकें घातीय जटिलता समस्या को बहुपद जटिलता समस्या में कम करने के लिए समस्या में बाधाओं का फायदा उठा सकती हैं। कई मामलों में, जैसे कि [[बाधा संतुष्टि समस्या]]ओं में, [[बाधा प्रचार]] के माध्यम से खोज स्थान को नाटकीय रूप से कम कर सकते हैं, जो [[बाधा प्रोग्रामिंग]] भाषाओं में कुशलतापूर्वक कार्यान्वित किया जाता है। पूरी समस्या को सरलीकृत संस्करण के साथ बदलकर समस्याओं के लिए खोज स्थान को भी कम किया जा सकता है। उदाहरण के लिए, [[कंप्यूटर शतरंज]] में, खेल के शेष भाग के लिए सभी संभावित चालों के पूर्ण न्यूनतम वृक्ष की गणना करने के बजाय, न्यूनतम संभावनाओं के अधिक सीमित वृक्ष की गणना की जाती है, जिसमें पेड़ को निश्चित संख्या में चालों में काट दिया जाता है, और शेष [[मूल्यांकन समारोह]] द्वारा वृक्ष का अनुमान लगाया जा रहा है। | ||
| Line 39: | Line 47: | ||
{{main|Brute-force attack}} | {{main|Brute-force attack}} | ||
[[क्रिप्टोग्राफी]] में, | [[क्रिप्टोग्राफी]] में, पाशविक बल हमले में सही कुंजी मिलने तक व्यवस्थित रूप से सभी संभावित [[कुंजी (क्रिप्टोग्राफी)]] की जांच करना सम्मिलित है।<ref>Mark Burnett, [http://www.cs.virginia.edu/~csadmin/gen_support/brute_force.php "Blocking Brute Force Attacks"] {{Webarchive|url=https://web.archive.org/web/20161203020306/http://www.cs.virginia.edu/~csadmin/gen_support/brute_force.php |date=2016-12-03 }}, ''UVA Computer Science'', 2007</ref> यह [[रणनीति]] सैद्धांतिक रूप से किसी भी एन्क्रिप्टेड डेटा के खिलाफ इस्तेमाल की जा सकती है<ref>{{cite book|url=http://www.crypto-textbook.com|page=7|title=Understanding Cryptography: A Textbook for Students and Practitioners|author1=Christof Paar |author2=Jan Pelzl |author3=Bart Preneel |publisher=Springer|year=2010|isbn=3-642-04100-0}}</ref> (एक बार के पैड को छोड़कर) हमलावर द्वारा जो एन्क्रिप्शन प्रणाली में किसी भी कमजोरी का लाभ उठाने में असमर्थ है जो अन्यथा उसके कार्य को आसान बना देगा। | ||
एन्क्रिप्शन में उपयोग की जाने वाली [[कुंजी लंबाई]] | एन्क्रिप्शन में उपयोग की जाने वाली [[कुंजी लंबाई]] पाशविक बल के हमले को करने की व्यावहारिक व्यवहार्यता को निर्धारित करती है, जिसमें छोटी कुंजियों की तुलना में लंबी कुंजियों को क्रैक करना अधिक कठिन होता है। ब्रूट फ़ोर्स के हमलों को एन्कोड किए जाने वाले डेटा को बाधित करके कम प्रभावी बनाया जा सकता है, ऐसा कुछ जो किसी हमलावर के लिए यह पहचानना अधिक कठिन बना देता है कि उसने कोड को कब क्रैक किया है। एन्क्रिप्शन प्रणाली की ताकत के उपायों में से यह है कि सैद्धांतिक रूप से हमलावर को इसके खिलाफ सफल पाशविक बल हमला करने में कितना समय लगेगा। | ||
==संदर्भ== | ==संदर्भ== | ||
| Line 47: | Line 55: | ||
== यह भी देखें == | == यह भी देखें == | ||
* सुडोकू | * सुडोकू पहेलियों को हल करने के लिए पाशविक बल एल्गोरिदम। | ||
* [[पशुबल का आक्रमण]] | * [[पशुबल का आक्रमण|पाशविक बल का आक्रमण]] | ||
* [[बिग ओ नोटेशन]] | * [[बिग ओ नोटेशन|बिग ओ-अंकन]] | ||
{{Algorithmic paradigms}} | {{Algorithmic paradigms}} | ||
Revision as of 12:36, 7 March 2023
कंप्यूटर विज्ञान में, पाशविक बल खोज(ब्रूट-फोर्स सर्च) या विस्तृत खोज , जिसे उत्पन्न(जेनरेट) और परीक्षण के रूप में भी जाना जाता है, बहुत ही सामान्य समस्या-समाधान तकनीक और एल्गोरिथम प्रतिमान है जिसमें समाधान के लिए सभी संभावित प्रत्याशियों की व्यवस्थित रूप से गणना करना और यह जांचना सम्मिलित है कि प्रत्येक प्रत्याशी समस्या के बयान को संतुष्ट करता है या नहीं करता है।
एक पाशविक बल(ब्रूट-फोर्स) एल्गोरिथ्म जो प्राकृतिक संख्या n के विभाजकों को खोजता है, यह 1 से n तक सभी पूर्णांकों की गणना करेगा, और जाँच करेगा कि कि क्या उनमें से प्रत्येक बिना शेष के n को विभाजित करता है। आठ रानियों की पहेली के लिए पाशविक बल अथवा ब्रूट-फोर्स अथवा पाशविक बल दृष्टिकोण 64-वर्ग शतरंज की बिसात पर 8 टुकड़ों की सभी संभावित व्यवस्थाओं की जांच करेगा और प्रत्येक व्यवस्था के लिए यह जांच करेगा कि प्रत्येक (रानी) टुकड़ा किसी अन्य पर हमला कर सकता है या नहीं कर सकता है ।[1]
यद्यपि पाशविक बल खोज सॉफ़्टवेयर को लागू करना आसान है और यदि यह मौजूद है तो हमेशा एक समाधान मिलेगा, कार्यान्वयन लागत उम्मीदवार समाधानों की संख्या के अनुपात में होती है – जो कई व्यावहारिक समस्याओं में समस्या के आकार के बढ़ने पर बहुत तेज़ी से बढ़ने लगती है (#Combinatorial विस्फोट| §संयुक्त विस्फोट)।[2] इसलिए, पाशविक बल खोज का उपयोग आमतौर पर तब किया जाता है जब समस्या का आकार सीमित होता है, या जब समस्या-विशिष्ट अनुमानिकीय (कंप्यूटर साइंस) होते हैं, जिनका उपयोग प्रत्याशी के समाधान के समुच्चय को प्रबंधनीय आकार में कम करने के लिए किया जा सकता है। विधि का उपयोग तब भी किया जाता है जब कार्यान्वयन की सरलता गति से अधिक महत्वपूर्ण होती है।
यह एकव प्रकार का मामला है, उदाहरण के लिए, महत्वपूर्ण अनुप्रयोगों में जहां कलन विधि में किसी भी त्रुटि के बहुत गंभीर परिणाम होंगे या जब गणितीय प्रमेय सिद्ध हो रहे हों। अन्य एल्गोरिदम या मेटाह्यूरिस्टिक्स को बेंच मार्किंग(मानकीकरण) करते समय पाशविक बल खोज आधारभूत विधि के रूप में भी उपयोगी होती है। दरअसल, पाशविक बल खोज को सबसे सरल मेटाह्यूरिस्टिक के रूप में देखा जा सकता है। ब्रूट फ़ोर्स खोज को बैक ट्रैकिंग के साथ भ्रमित नहीं होना चाहिए, जहां समाधानों के बड़े समुच्चयों ों को स्पष्ट रूप से गणना किए बिना त्याग दिया जा सकता है (जैसा कि ऊपर आठ रानियों की समस्या के पाठ्यपुस्तक कंप्यूटर समाधान में है)। किसी तालिका में किसी आइटम को खोजने के लिए पाशविक बल विधि – अर्थात्, बाद की सभी प्रविष्टियों की जाँच करें, क्रमिक रूप से जाँच करें – रेखीय खोज कहा जाता है।
पाशविक बल खोज को कार्यान्वित करना
बेसिक एल्गोरिथम
क्रम में वर्तमान के बाद P के लिए प्रत्याशी c।
- वैध (P, c): जांचें कि प्रत्याशी c P के लिए समाधान है या नहीं है।
- आउटपुट (P, c): आवेदन के लिए उपयुक्त के रूप में P के समाधान c का उपयोग करें।
अगली प्रक्रिया को यह भी बताना होगा कि वर्तमान c के बाद P के लिए कोई और प्रत्याशी नहीं हैं। ऐसा करने का सुविधाजनक तरीका "अशक्त प्रत्याशी" को वापस करना है, कुछ पारंपरिक डेटा मान Λ जो कि किसी भी वास्तविक प्रत्याशी से अलग है। इसी प्रकार पहली प्रक्रिया को Λ वापस करना चाहिए यदि उदाहरण P के लिए कोई प्रत्याशी नहीं हैं। ब्रूट-बल विधि तब एल्गोरिदम द्वारा व्यक्त की जाती है:
c ← first(P)
while c ≠ Λ do
if valid(P,c) then
output(P, c)
c ← next(P, c)
end while
उदाहरण के लिए, जब पूर्णांक n के भाजक की खोज की जाती है, तो उदाहरण डेटा P संख्या n होता है। पहली पुकार (n) को पूर्णांक 1 वापस करना चाहिए यदि n ≥ 1, या Λ अन्यथा; अगली पुकार (n, c) को c + 1 वापस करना चाहिए यदि c <n, और Λ अन्यथा; और वैध (n, c) को 'सत्य' वापस करना चाहिए अगर और केवल अगर c , n का विभाजक है। (वास्तव में, यदि हम Λ को n + 1 चुनते हैं, तो परीक्षण n ≥ 1 और c <n अनावश्यक हैं।) उपरोक्त पाशविक बल खोज एल्गोरिदम प्रत्येक प्रत्याशी के लिए आउटपुट पुकार करेगा जो दिए गए उदाहरण P का समाधान है। पहला समाधान, या निर्दिष्ट संख्या में समाधान या उम्मीदवारों की निर्दिष्ट संख्या का परीक्षण करने के बाद या सीपीयू समय की एक निश्चित राशि खर्च करने के बाद एल्गोरिथ्म को रोकने के लिए आसानी से संशोधित किया जाता है।
मिश्रित विस्फोट
पाशविक बल पद्धति का मुख्य हानि यह है कि, वास्तविक-विश्व की कई समस्याओं के लिए, प्राकृतिक प्रत्याशियों की संख्या निषेधात्मक रूप से बड़ी है। उदाहरण के लिए, यदि हम ऊपर वर्णित संख्या के विभाजक की खोज करते हैं, तो परीक्षण किए गए प्रत्याशियों की संख्या दी गई संख्या n होगी। इसलिए यदि n में 16 दशमलव अंक हैं, तो खोज के लिए कम से कम 1015 कंप्यूटर निर्देश क्रियान्वित करने की आवश्यकता होगी कंप्यूटर निर्देश, जिसमें विशिष्ट व्यक्तिगत कंप्यूटर पर कई दिन लगेंगे। यदि n यादृच्छिक 64-बाइनरी अंकों की प्राकृतिक संख्या है, जिसमें औसतन लगभग 19 दशमलव अंक हैं, तो खोज में लगभग 10 वर्ष लगेंगे। प्रत्याशियों की संख्या में यह तीव्र वृद्धि, जैसे-जैसे डेटा का आकार बढ़ता है, सभी प्रकार की समस्याओं में होता है। उदाहरण के लिए, यदि हम 10 अक्षरों की विशेष पुनर्व्यवस्था की मांग कर रहे हैं, तो हमारे पास 10 हैं! = 3,628,800 प्रत्याशियों पर विचार करने के लिए, जो विशिष्ट पीसी सेकंड से भी कम समय में उत्पन्न और परीक्षण कर सकता है। हालाँकि, और पत्र जोड़ना – जो डेटा आकार में केवल 10% की वृद्धि है – प्रत्याशियों की संख्या को 11 से गुणा कर देगा, 1000% की वृद्धि। 20 अक्षरों के लिए, प्रत्याशियों की संख्या 20! है, जो लगभग 2.4×10 है18 या 2.4 क्विंटिलियन; और खोज में लगभग 10 वर्ष लगेंगे। इस अप्रिय घटना को आमतौर पर दहनशील विस्फोट या आयामीता का अभिशाप कहा जाता है।
ऐसे मामले का उदाहरण जहां संयोजी जटिलता से विलेयता की सीमा हो जाती है, शतरंज को हल करने में है। शतरंज कोई सुलझा हुआ खेल नहीं है। 2005 में, छह पीस या उससे कम वाले सभी शतरंज के खेल को हल किया गया था, जो पूरी तरह से खेले जाने पर प्रत्येक स्थिति का परिणाम दिखाते थे। टेबलबेस को और शतरंज के टुकड़े के साथ पूरा करने में दस साल लग गए, इस प्रकार 7-टुकड़ा टेबलबेस पूरा हो गया। शतरंज के समापन में और टुकड़ा जोड़ना (इस प्रकार 8-टुकड़ा टेबलबेस बनाना) को जोड़ा संयोजन जटिलता के कारण अट्रैक्टिव माना जाता है।[3][4]
पाशविक बल खोजों को तेज करना
पाशविक बल एल्गोरिदम को गति देने का तरीका समस्या वर्ग के लिए विशिष्ट अनुमानी ्स का उपयोग करके, खोज स्थान को कम करना है, यानी प्रत्याशी समाधान का सेट। उदाहरण के लिए, आठ रानियों की पहेली में आठ रानियों को मानक शतरंज की बिसात पर रखने की चुनौती है ताकि कोई भी रानी किसी दूसरे पर हमला न करे। चूंकि प्रत्येक रानी को 64 वर्गों में से किसी में भी रखा जा सकता है, सिद्धांत रूप में 64 हैं8 = 281,474,976,710,656 विचार करने की संभावनाएं। हालाँकि, क्योंकि रानियाँ सभी जैसी हैं, और कोई भी दो रानियाँ ही वर्ग पर नहीं रखी जा सकती हैं, प्रत्याशी सभी 64 वर्गों के समुच्चय से 8 वर्गों के संयोजन हैं; जिसका मतलब है कि 64 चुनें 8 = 64!/(56!*8!) = 4,426,165,368 प्रत्याशी समाधान – पिछले अनुमान का लगभग 1/60,000। इसके अलावा, ही पंक्ति या ही स्तंभ पर दो रानियों के साथ कोई व्यवस्था समाधान नहीं हो सकती है। इसलिए, हम प्रत्याशियों के समुच्चय को उन व्यवस्थाओं तक सीमित कर सकते हैं।
जैसा कि इस उदाहरण से पता चलता है, थोड़ा सा विश्लेषण अक्सर प्रत्याशी समाधानों की संख्या में नाटकीय कमी लाएगा, और जटिल समस्या को तुच्छ में बदल सकता है।
कुछ मामलों में, विश्लेषण प्रत्याशियों को सभी वैध समाधानों के समुच्चय तक कम कर सकता है; अर्थात्, यह एल्गोरिदम उत्पन्न कर सकता है जो परीक्षणों के साथ समय बर्बाद किए बिना और अमान्य प्रत्याशियों की पीढ़ी के बिना सभी वांछित समाधानों को सीधे गणना करता है (या उपयुक्त समाधान पाता है)। उदाहरण के लिए, समस्या के लिए 1 और 1,000,000 के बीच के सभी पूर्णांकों को खोजें जो समान रूप से 417 से विभाज्य हैं, भोली जानवर-बल समाधान श्रेणी में सभी पूर्णांक उत्पन्न करेगा, उनमें से प्रत्येक को विभाज्यता के लिए परीक्षण करेगा। हालाँकि, उस समस्या को 417 से शुरू करके और 1,000,000 से अधिक होने तक बार-बार 417 जोड़कर और अधिक कुशलता से हल किया जा सकता है – जो केवल 2398 (= 1,000,000 ÷ 417) कदम उठाता है, और कोई परीक्षण नहीं करता है।
खोज स्थान को पुनर्क्रमित करना
उन अनुप्रयोगों में जिन्हें सभी समाधानों के बजाय केवल समाधान की आवश्यकता होती है, ब्रूट फ़ोर्स खोज का अपेक्षित मान चलने का समय अक्सर उस क्रम पर निर्भर करेगा जिसमें प्रत्याशियों का परीक्षण किया जाता है। सामान्य नियम के रूप में, पहले सबसे होनहार प्रत्याशियों का परीक्षण करना चाहिए। उदाहरण के लिए, यादृच्छिक संख्या n के उचित विभाजक की खोज करते समय, 2 से बढ़ते क्रम में प्रत्याशी विभाजक की गणना करना बेहतर होता है n − 1, इसके विपरीत – क्योंकि n के c से विभाज्य होने की संभावना 1/c है। इसके अलावा, प्रत्याशी के वैध होने की संभावना अक्सर पिछले असफल परीक्षणों से प्रभावित होती है। उदाहरण के लिए, दिए गए 1000-बिट स्ट्रिंग P में '1' बिट खोजने की समस्या पर विचार करें। इस मामले में, प्रत्याशी समाधान 1 से 1000 तक के सूचकांक हैं, और प्रत्याशी c मान्य है यदि P[c] = '1 '। अब, मान लीजिए कि P का पहला बिट '0' या '1' होने की समान संभावना है, लेकिन उसके बाद प्रत्येक बिट 90% संभावना के साथ पिछले के बराबर है। यदि प्रत्याशियों को बढ़ते क्रम में 1 से 1000 तक गिना जाता है, तो सफलता से पहले जांचे गए प्रत्याशियों की संख्या औसतन लगभग 6 होगी। दूसरी ओर, यदि प्रत्याशियों की गणना 1,11,21,31...991,2,12,22,32 आदि के क्रम में की जाती है, तो टी का अपेक्षित मूल्य 2 से थोड़ा ही अधिक होगा।अधिक आम तौर पर, खोज स्थान को इस तरह से गिना जाना चाहिए कि अगले प्रत्याशी के वैध होने की सबसे अधिक संभावना है, यह देखते हुए कि पिछले परीक्षण नहीं थे। इसलिए यदि वैध समाधानों को किसी अर्थ में क्लस्टर किए जाने की संभावना है, तो प्रत्येक नए प्रत्याशी को उसी अर्थ में पिछले वाले से जितना संभव हो उतना दूर होना चाहिए। निश्चित रूप से, यदि समाधान संयोग से अपेक्षा से अधिक समान रूप से फैले होने की संभावना है, तो निश्चित रूप से इसका विलोम होता है।
पाशविक बल खोज के विकल्प
कई अन्य खोज विधियाँ, या मेटाह्यूरिस्टिक्स हैं, जिन्हें समाधान के बारे में विभिन्न प्रकार के आंशिक ज्ञान का लाभ उठाने के लिए डिज़ाइन किया गया है। खोज के कुछ हिस्सों का शुरुआती कटऑफ़ बनाने के लिए ह्यूरिस्टिक्स का भी उपयोग किया जा सकता है। इसका उदाहरण गेम ट्री की खोज के लिए अल्पमहिष्ठ सिद्धांत है, जो खोज के प्रारंभिक चरण में कई सबट्री को हटा देता है। कुछ क्षेत्रों में, जैसे भाषा पार्सिंग, चार्ट विश्लेषण जैसी तकनीकें घातीय जटिलता समस्या को बहुपद जटिलता समस्या में कम करने के लिए समस्या में बाधाओं का फायदा उठा सकती हैं। कई मामलों में, जैसे कि बाधा संतुष्टि समस्याओं में, बाधा प्रचार के माध्यम से खोज स्थान को नाटकीय रूप से कम कर सकते हैं, जो बाधा प्रोग्रामिंग भाषाओं में कुशलतापूर्वक कार्यान्वित किया जाता है। पूरी समस्या को सरलीकृत संस्करण के साथ बदलकर समस्याओं के लिए खोज स्थान को भी कम किया जा सकता है। उदाहरण के लिए, कंप्यूटर शतरंज में, खेल के शेष भाग के लिए सभी संभावित चालों के पूर्ण न्यूनतम वृक्ष की गणना करने के बजाय, न्यूनतम संभावनाओं के अधिक सीमित वृक्ष की गणना की जाती है, जिसमें पेड़ को निश्चित संख्या में चालों में काट दिया जाता है, और शेष मूल्यांकन समारोह द्वारा वृक्ष का अनुमान लगाया जा रहा है।
क्रिप्टोग्राफी में
क्रिप्टोग्राफी में, पाशविक बल हमले में सही कुंजी मिलने तक व्यवस्थित रूप से सभी संभावित कुंजी (क्रिप्टोग्राफी) की जांच करना सम्मिलित है।[5] यह रणनीति सैद्धांतिक रूप से किसी भी एन्क्रिप्टेड डेटा के खिलाफ इस्तेमाल की जा सकती है[6] (एक बार के पैड को छोड़कर) हमलावर द्वारा जो एन्क्रिप्शन प्रणाली में किसी भी कमजोरी का लाभ उठाने में असमर्थ है जो अन्यथा उसके कार्य को आसान बना देगा।
एन्क्रिप्शन में उपयोग की जाने वाली कुंजी लंबाई पाशविक बल के हमले को करने की व्यावहारिक व्यवहार्यता को निर्धारित करती है, जिसमें छोटी कुंजियों की तुलना में लंबी कुंजियों को क्रैक करना अधिक कठिन होता है। ब्रूट फ़ोर्स के हमलों को एन्कोड किए जाने वाले डेटा को बाधित करके कम प्रभावी बनाया जा सकता है, ऐसा कुछ जो किसी हमलावर के लिए यह पहचानना अधिक कठिन बना देता है कि उसने कोड को कब क्रैक किया है। एन्क्रिप्शन प्रणाली की ताकत के उपायों में से यह है कि सैद्धांतिक रूप से हमलावर को इसके खिलाफ सफल पाशविक बल हमला करने में कितना समय लगेगा।
संदर्भ
- ↑ "ब्रूट फ़ोर्स एल्गोरिदम समझाया गया". freeCodeCamp.org (in English). 2020-01-06. Retrieved 2021-04-11.
- ↑ "क्रूर बल खोज की जटिलता". coursera. Retrieved 14 June 2018.
- ↑ "Is there a freely available online 7 piece Endgame tablebase?". Stack Exchange.
- ↑ "लोमोनोसोव एंडगेम टेबलबेस". ChessOK.
- ↑ Mark Burnett, "Blocking Brute Force Attacks" Archived 2016-12-03 at the Wayback Machine, UVA Computer Science, 2007
- ↑ Christof Paar; Jan Pelzl; Bart Preneel (2010). Understanding Cryptography: A Textbook for Students and Practitioners. Springer. p. 7. ISBN 3-642-04100-0.
यह भी देखें
- सुडोकू पहेलियों को हल करने के लिए पाशविक बल एल्गोरिदम।
- पाशविक बल का आक्रमण
- बिग ओ-अंकन
श्रेणी:खोज एल्गोरिदम
