ब्रूट-फोर्स सर्च: Difference between revisions
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
[[कंप्यूटर विज्ञान]] में, पाशविक बल खोज(ब्रूट-फोर्स सर्च) या विस्तृत खोज , जिसे उत्पन्न(जेनरेट) और परीक्षण के रूप में भी जाना जाता है, बहुत ही सामान्य समस्या-समाधान विधि और [[एल्गोरिथम प्रतिमान]] है जिसमें समाधान के लिए सभी संभावित प्रत्याशियों की व्यवस्थित रूप से गणना करना और यह जांचना सम्मिलित है कि प्रत्येक प्रत्याशी समस्या के कथन को संतुष्ट करता है या नहीं करता है। | [[कंप्यूटर विज्ञान]] में, पाशविक बल खोज(ब्रूट-फोर्स सर्च) या विस्तृत खोज , जिसे उत्पन्न(जेनरेट) और परीक्षण के रूप में भी जाना जाता है, बहुत ही सामान्य समस्या-समाधान विधि और [[एल्गोरिथम प्रतिमान]] है जिसमें समाधान के लिए सभी संभावित प्रत्याशियों की व्यवस्थित रूप से गणना करना और यह जांचना सम्मिलित है कि प्रत्येक प्रत्याशी समस्या के कथन को संतुष्ट करता है या नहीं करता है। | ||
एक पाशविक बल(ब्रूट-फोर्स) एल्गोरिथ्म जो [[प्राकृतिक संख्या]] ''n'' के [[भाजक|विभाजकों]] को खोजता है, यह 1 से n तक सभी पूर्णांकों की गणना करेगा, और जाँच करेगा कि कि क्या उनमें से प्रत्येक बिना शेष के n को विभाजित करता है। आठ रानियों की पहेली के लिए पाशविक बल अथवा ब्रूट-फोर्स अथवा पाशविक बल दृष्टिकोण 64-वर्ग शतरंज की बिसात पर 8 | एक पाशविक बल(ब्रूट-फोर्स) एल्गोरिथ्म जो [[प्राकृतिक संख्या]] ''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}}जो कई व्यावहारिक समस्याओं में समस्या के आकार के बढ़ने पर बहुत | यद्यपि पाशविक बल खोज [[ सॉफ़्टवेयर |सॉफ़्टवेयर]] को प्रयुक्त करना आसान है और यदि यह उपस्थित है तो सदैव एक समाधान मिलेगा, कार्यान्वयन निवेश उम्मीदवार समाधानों की संख्या के अनुपात में होती है{{snd}}जो कई व्यावहारिक समस्याओं में समस्या के आकार के बढ़ने पर बहुत तीव्र गति से बढ़ने लगती है (§संयुक्त विस्फोट)।<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}}रेखीय खोज कहा जाता है। | यह एकव प्रकार का स्थिति है, उदाहरण के लिए, महत्वपूर्ण अनुप्रयोगों में जहां [[कलन विधि]] में किसी भी त्रुटि के बहुत गंभीर परिणाम होंगे या जब गणितीय प्रमेय सिद्ध हो रहे हों। अन्य एल्गोरिदम या [[मेटाह्यूरिस्टिक|मेटाह्यूरिस्टिक्स]] को [[ बेंच मार्किंग |बेंच मार्किंग(मानकीकरण)]] करते समय पाशविक बल खोज आधारभूत विधि के रूप में भी उपयोगी होती है। दरअसल, पाशविक बल खोज को सबसे सरल मेटाह्यूरिस्टिक के रूप में देखा जा सकता है। ब्रूट फ़ोर्स खोज को [[ बैक ट्रैकिंग |बैक ट्रैकिंग]] के साथ भ्रमित नहीं होना चाहिए, जहां समाधानों के बड़े समुच्चयों को स्पष्ट रूप से गणना किए बिना त्याग दिया जा सकता है (जैसा कि ऊपर आठ रानियों की समस्या के पाठ्यपुस्तक कंप्यूटर समाधान में है)। किसी सारिणी में किसी वस्तु को खोजने के लिए पाशविक बल विधि{{snd}}अर्थात्, बाद की सभी प्रविष्टियों की जाँच करें, क्रमिक रूप से {{snd}}रेखीय खोज कहा जाता है। | ||
| Line 15: | Line 15: | ||
# वैध (P, c): जांचें कि प्रत्याशी c P के लिए समाधान है या नहीं है। | # वैध (P, c): जांचें कि प्रत्याशी c P के लिए समाधान है या नहीं है। | ||
# आउटपुट (P, c): आवेदन के लिए उपयुक्त के रूप में P के समाधान c का उपयोग करें। | # आउटपुट (P, c): आवेदन के लिए उपयुक्त के रूप में P के समाधान c का उपयोग करें। | ||
अगली प्रक्रिया को यह भी बताना होगा कि वर्तमान c के बाद P के लिए कोई और प्रत्याशी नहीं हैं। ऐसा करने | अगली प्रक्रिया को यह भी बताना होगा कि वर्तमान एक c के बाद P के लिए कोई और प्रत्याशी नहीं हैं। ऐसा करने की सुविधाजनक विधि "अशक्त प्रत्याशी" को वापस करना है, कुछ पारंपरिक डेटा मान Λ जो कि किसी भी वास्तविक प्रत्याशी से अलग है। इसी प्रकार पहली प्रक्रिया को Λ वापस करना चाहिए यदि उदाहरण P के लिए कोई प्रत्याशी नहीं हैं। ब्रूट-बल विधि तब एल्गोरिदम द्वारा व्यक्त की जाती है:<syntaxhighlight> | ||
c ← first(P) | c ← first(P) | ||
while c ≠ Λ do | while c ≠ Λ do | ||
| Line 24: | Line 24: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
उदाहरण के लिए, जब पूर्णांक 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 के भाजक की खोज की जाती है, तो उदाहरण डेटा 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 प्रत्याशियों पर विचार करने के लिए, जो विशिष्ट पीसी(PC) सेकंड से भी कम समय में उत्पन्न और परीक्षण कर सकता है। चूँकि, एक और पत्र जोड़ना{{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> | ||
== पाशविक बल खोजों को | == पाशविक बल खोजों को तीव्र करना == | ||
पाशविक बल एल्गोरिदम को गति देने का | पाशविक बल एल्गोरिदम को गति देने की एक विधि अर्थात प्रत्याशी समाधान का समुच्चय जो कि समस्या वर्ग के लिए विशिष्ट [[ अनुमानी |अनुमानिकता(ह्यूरिस्टिक्स)]] ्स का उपयोग करके, खोज स्थान को कम करना है '''अर्थात प्रत्याशी समाधान का समुच्चय'''। उदाहरण के लिए, आठ रानियों की पहेली में आठ रानियों को मानक शतरंज की [[बिसात|बिसात(सामर्थ्य)]] पर रखने की चुनौती है जिससे कोई भी रानी किसी दूसरे पर हमला न कर सके । चूंकि प्रत्येक रानी को 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 के उचित विभाजक की खोज करते | उन अनुप्रयोगों में जिन्हें सभी समाधानों के अतिरिक्त मात्र एक समाधान की आवश्यकता होती है, ब्रूट फ़ोर्स खोज का अपेक्षित मान चलने का समय प्रायः उस क्रम पर निर्भर करेगा जिसमें प्रत्याशियों का परीक्षण किया जाता है। एक सामान्य नियम के रूप में, पहले सबसे होनहार प्रत्याशियों का परीक्षण करना चाहिए। उदाहरण के लिए, यादृच्छिक संख्या n के उचित विभाजक की खोज करते हैं, तो दूसरी विधि की तुलना में, 2 से {{nowrap|''n'' − 1}} से बढ़ते क्रम में प्रत्याशी विभाजक की गणना करना उत्तम होता है, '''इसके विपरीत'''{{snd}}क्योंकि n के c से विभाज्य होने की प्रायिकता 1/c है। इसके अतिरिक्त, प्रत्याशी के वैध होने की प्रायिकता प्रायः पिछले असफल परीक्षणों से प्रभावित होती है। उदाहरण के लिए, दिए गए 1000-बिट स्ट्रिंग P में '1' बिट खोजने की समस्या पर विचार करें। इस स्थिति में, प्रत्याशी समाधान 1 से 1000 तक के सूचकांक हैं, और '''प्रत्याशी c मान्य है''' यदि P(c)= '1 ' हो तो प्रत्याशी c मान्य है । अब, मान लीजिए कि P का पहला बिट '0' या '1' होने की समान प्रायिकता है, किन्तु उसके बाद प्रत्येक बिट 90% प्रायिकता के साथ पिछले के बराबर है। यदि प्रत्याशियों को बढ़ते क्रम में 1 से 1000 तक गिना जाता है, तो सफलता से पहले जांचे गए प्रत्याशियों की संख्या औसतन लगभग 6 होगी। दूसरी ओर, यदि प्रत्याशियों की गणना 1,11,21,31...991,2,12,22,32 आदि के क्रम में की जाती है, तो ''t'' का अपेक्षित मूल्य 2 से थोड़ा ही अधिक होगा। सामान्य रूप से अधिक '''सामान्यतः''' , खोज स्थान को इस तरह से गिना जाना चाहिए कि अगले प्रत्याशी के वैध होने की सबसे अधिक प्रायिकता है, यह देखते हुए कि पिछले परीक्षण नहीं थे। इसलिए यदि वैध समाधानों को किसी अर्थ में "क्लस्टर" या "समूहीकृत" किए जाने की प्रायिकता है, तो प्रत्येक नए प्रत्याशी को उसी अर्थ में पिछले वाले से जितना संभव हो उतना दूर होना चाहिए। निश्चित रूप से, यदि समाधान संयोग से अपेक्षा से अधिक समान रूप से फैले होने की प्रायिकता है, तो निश्चित रूप से इसका विलोम होता है। | ||
== पाशविक बल खोज के विकल्प == | == पाशविक बल खोज के विकल्प == | ||
कई अन्य खोज विधियाँ, या मेटाह्यूरिस्टिक्स हैं, जिन्हें समाधान के | कई अन्य खोज विधियाँ, या मेटाह्यूरिस्टिक्स हैं, जिन्हें समाधान के विषय में विभिन्न प्रकार के आंशिक ज्ञान का लाभ उठाने के लिए रचित किया गया है। खोज के कुछ हिस्सों का प्रारंभिक कटऑफ़ बनाने के लिए अनुमानिकता का भी उपयोग किया जा सकता है। इसका उदाहरण गेम-ट्रीज की खोज के लिए [[अल्पमहिष्ठ|अल्पमहिष्ठ सिद्धांत]] '''सिद्धांत''' है, जो खोज के प्रारंभिक चरण में कई सबट्रीज को निष्काशित कर देता है। कुछ क्षेत्रों में, जैसे भाषा विश्लेषण, [[ चार्ट विश्लेषण |चार्ट विश्लेषण]] जैसी विधियां घातीय जटिलता समस्या को बहुपद जटिलता समस्या में कम करने के लिए समस्या में बाधाओं का लाभ उठा सकती हैं। कई स्थितियों में, जैसे कि [[बाधा संतुष्टि समस्या|बाधा संतुष्टि समस्याओं]] में, [[बाधा प्रचार]] के माध्यम से खोज स्थान को नाटकीय रूप से कम कर सकते हैं, जो [[बाधा प्रोग्रामिंग]] भाषाओं में कुशलतापूर्वक कार्यान्वित किया जाता है। पूरी समस्या को सरलीकृत संस्करण के साथ बदलकर समस्याओं के लिए खोज स्थान को भी कम किया जा सकता है। उदाहरण के लिए, [[कंप्यूटर शतरंज]] में, खेल के शेष भाग के लिए सभी संभावित चालों के पूर्ण न्यूनतम ट्रीज की गणना करने के अतिरिक्त , न्यूनतम प्रायिकताओं के अधिक सीमित ट्रीज की गणना की जाती है, जिसमें ट्रीज को निश्चित संख्या में चालों में काट दिया जाता है, और शेष [[मूल्यांकन समारोह|मूल्यांकन प्रकार्य]] द्वारा ट्रीज का अनुमान लगाया जा रहा है। | ||
== क्रिप्टोग्राफी में == | == कूटलिपि शास्त्र(क्रिप्टोग्राफी) में == | ||
{{main|पाशविक-बल आक्रमण}} | {{main|पाशविक-बल आक्रमण}} | ||
[[क्रिप्टोग्राफी]] में, पाशविक बल | [[क्रिप्टोग्राफी|कूटलिपि शास्त्र]] में, पाशविक बल आक्रमण में सही कुंजी मिलने तक व्यवस्थित रूप से सभी संभावित [[कुंजी (क्रिप्टोग्राफी)|कुंजी '''(कूटलिपि शास्त्र)''']] की जांच करना सम्मिलित है।<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> ('''एक बार के''' पैड या गद्दी के अतिरिक्त) आक्रमणकारी द्वारा जो एन्क्रिप्शन अथवा कूटलेखन प्रणाली में किसी भी अशक्तता का लाभ उठाने में असमर्थ है जो अन्यथा उसके कार्य को सरल बना देगा। | ||
एन्क्रिप्शन में उपयोग की जाने वाली [[कुंजी लंबाई]] पाशविक बल के | एन्क्रिप्शन में उपयोग की जाने वाली [[कुंजी लंबाई]] पाशविक बल के आक्रमण को करने की व्यावहारिक व्यवहार्यता को निर्धारित करती है, जिसमें छोटी कुंजियों की तुलना में लंबी कुंजियों को भंग करना अधिक कठिन होता है। पाशविक बल के आक्रमणों को सांकेतिक शब्दों में परिवर्तित किए जाने वाले डेटा को बाधित करके कम प्रभावी बनाया जा सकता है, ऐसा कुछ जो किसी आक्रमणकारी के लिए यह पहचानना अधिक कठिन बना देता है कि उसने संहिता को कब भंग किया है। एन्क्रिप्शन प्रणाली की शक्ति के उपायों में से यह है कि सैद्धांतिक रूप से आक्रमणकारी को इसके विरुद्ध सफल पाशविक बल आक्रमण करने में कितना समय लगेगा। | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 10:23, 10 March 2023
कंप्यूटर विज्ञान में, पाशविक बल खोज(ब्रूट-फोर्स सर्च) या विस्तृत खोज , जिसे उत्पन्न(जेनरेट) और परीक्षण के रूप में भी जाना जाता है, बहुत ही सामान्य समस्या-समाधान विधि और एल्गोरिथम प्रतिमान है जिसमें समाधान के लिए सभी संभावित प्रत्याशियों की व्यवस्थित रूप से गणना करना और यह जांचना सम्मिलित है कि प्रत्येक प्रत्याशी समस्या के कथन को संतुष्ट करता है या नहीं करता है।
एक पाशविक बल(ब्रूट-फोर्स) एल्गोरिथ्म जो प्राकृतिक संख्या n के विभाजकों को खोजता है, यह 1 से n तक सभी पूर्णांकों की गणना करेगा, और जाँच करेगा कि कि क्या उनमें से प्रत्येक बिना शेष के n को विभाजित करता है। आठ रानियों की पहेली के लिए पाशविक बल अथवा ब्रूट-फोर्स अथवा पाशविक बल दृष्टिकोण 64-वर्ग शतरंज की बिसात पर 8 भागों की सभी संभावित व्यवस्थाओं की जांच करेगा और प्रत्येक व्यवस्था के लिए यह जांच करेगा कि प्रत्येक(रानी) भाग किसी अन्य पर हमला कर सकता है या नहीं कर सकता है ।[1]
यद्यपि पाशविक बल खोज सॉफ़्टवेयर को प्रयुक्त करना आसान है और यदि यह उपस्थित है तो सदैव एक समाधान मिलेगा, कार्यान्वयन निवेश उम्मीदवार समाधानों की संख्या के अनुपात में होती है – जो कई व्यावहारिक समस्याओं में समस्या के आकार के बढ़ने पर बहुत तीव्र गति से बढ़ने लगती है (§संयुक्त विस्फोट)।[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 प्रत्याशियों पर विचार करने के लिए, जो विशिष्ट पीसी(PC) सेकंड से भी कम समय में उत्पन्न और परीक्षण कर सकता है। चूँकि, एक और पत्र जोड़ना – जो डेटा आकार में मात्र 10% की वृद्धि है – प्रत्याशियों की संख्या को 11 से गुणा कर, 1000% की वृद्धि कर देगा। 20 अक्षरों के लिए, प्रत्याशियों की संख्या 20! है, जो लगभग 2.4×1018 या 2.4 क्विंटिलियन है; और खोज में लगभग 10 वर्ष लगेंगे। इस अप्रिय घटना को सामान्यतः दहनशील विस्फोट या आयामीता का अभिशाप कहा जाता है।
ऐसी स्थितियों का उदाहरण शतरंज को हल करने में है, जहां संयोजी जटिलता से विलेयता की सीमा हो जाती है, शतरंज को हल करने में है। शतरंज कोई सुलझा हुआ खेल नहीं है। 2005 में, छह भाग या उससे कम वाले सभी शतरंज के खेल को हल किया गया था, जो पूरी तरह से खेले जाने पर प्रत्येक स्थिति का परिणाम दिखाते थे। टेबलबेस को एक और शतरंज के भाग के साथ पूरा करने में दस वर्ष लग गए, इस प्रकार एक 7-भाग टेबलबेस पूरा हो गया। शतरंज के समापन में एक और भाग जोड़ने (इस प्रकार एक 8-भाग टेबलबेस बनाना) को जोड़ा संयोजन जटिलता के कारण अट्रैक्टिव माना जाता है।[3][4]
पाशविक बल खोजों को तीव्र करना
पाशविक बल एल्गोरिदम को गति देने की एक विधि अर्थात प्रत्याशी समाधान का समुच्चय जो कि समस्या वर्ग के लिए विशिष्ट अनुमानिकता(ह्यूरिस्टिक्स) ्स का उपयोग करके, खोज स्थान को कम करना है अर्थात प्रत्याशी समाधान का समुच्चय। उदाहरण के लिए, आठ रानियों की पहेली में आठ रानियों को मानक शतरंज की बिसात(सामर्थ्य) पर रखने की चुनौती है जिससे कोई भी रानी किसी दूसरे पर हमला न कर सके । चूंकि प्रत्येक रानी को 64 वर्गों में से किसी में भी रखा जा सकता है, सिद्धांत रूप में विचार करने की 648 = 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 ' हो तो प्रत्याशी c मान्य है । अब, मान लीजिए कि P का पहला बिट '0' या '1' होने की समान प्रायिकता है, किन्तु उसके बाद प्रत्येक बिट 90% प्रायिकता के साथ पिछले के बराबर है। यदि प्रत्याशियों को बढ़ते क्रम में 1 से 1000 तक गिना जाता है, तो सफलता से पहले जांचे गए प्रत्याशियों की संख्या औसतन लगभग 6 होगी। दूसरी ओर, यदि प्रत्याशियों की गणना 1,11,21,31...991,2,12,22,32 आदि के क्रम में की जाती है, तो t का अपेक्षित मूल्य 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.
यह भी देखें
- सुडोकू पहेलियों को हल करने के लिए पाशविक बल एल्गोरिदम।
- पाशविक बल का आक्रमण
- बिग ओ-अंकन
श्रेणी:खोज एल्गोरिदम
