यादृच्छिकता परीक्षण: Difference between revisions

From Vigyanwiki
(Created page with "{{confuse|randomised test}} डेटा मूल्यांकन में एक यादृच्छिकता परीक्षण (या यादृच्छि...")
 
No edit summary
Line 1: Line 1:
{{confuse|randomised test}}
{{confuse|यादृच्छिकता परीक्षण}}
डेटा मूल्यांकन में एक यादृच्छिकता परीक्षण (या यादृच्छिकता के लिए परीक्षण), डेटा के एक सेट के वितरण का विश्लेषण करने के लिए उपयोग किया जाने वाला एक परीक्षण है, यह देखने के लिए कि क्या इसे यादृच्छिक (पैटर्न रहित) के रूप में वर्णित किया जा सकता है। [[स्टोकेस्टिक मॉडलिंग]] में, कुछ [[कंप्यूटर सिमुलेशन]] के रूप में, संभावित इनपुट डेटा की यादृच्छिकता के लिए आशा की जा सकती है, यादृच्छिकता के लिए एक औपचारिक परीक्षण द्वारा सत्यापित किया जा सकता है, यह दिखाने के लिए कि सिमुलेशन रन में उपयोग के लिए डेटा मान्य हैं। कुछ मामलों में, डेटा एक स्पष्ट गैर-यादृच्छिक पैटर्न प्रकट करता है, जैसा कि डेटा में तथाकथित रन के साथ होता है (जैसे कि यादृच्छिक 0–9 की उम्मीद करना लेकिन 4 3 2 1 0 4 3 2 1 ... और शायद ही कभी 4 से ऊपर जाना) . यदि डेटा का एक चयनित सेट परीक्षणों में विफल रहता है, तो मापदंडों को बदला जा सकता है या अन्य यादृच्छिक डेटा का उपयोग किया जा सकता है जो यादृच्छिकता के लिए परीक्षण पास करता है।
 
डेटा मूल्यांकन में '''यादृच्छिकता परीक्षण''' (या '''यादृच्छिकता के लिए परीक्षण''') डेटा के सेट के वितरण का विश्लेषण करने के लिए उपयोग किया जाने वाला परीक्षण है एवं यह देखने के लिए कि क्या इसे यादृच्छिक (पैटर्न रहित) के रूप में वर्णित किया जा सकता है। [[स्टोकेस्टिक मॉडलिंग]] में कुछ [[कंप्यूटर सिमुलेशन]] के रूप में संभावित इनपुट डेटा की यादृच्छिकता के लिए आशा की जा सकती है तथा यादृच्छिकता के लिए औपचारिक परीक्षण द्वारा सत्यापित किया जा सकता है एवं यह दिखाने के लिए कि सिमुलेशन रन में उपयोग के लिए डेटा मान्य हैं। कुछ स्थितियों में डेटा स्पष्ट गैर-यादृच्छिक बनावट प्रकट करता है जैसा कि डेटा में तथाकथित रन के साथ होता है (जैसे कि यादृच्छिक 0–9 की आशा करना परन्तु 4 3 2 1 0 4 3 2 1 ... और संभवतः ही कभी 4 से ऊपर जाना)। यदि डेटा का चयनित सेट परीक्षणों में विफल रहता है तो मापदंडों को परिवर्तित किया जा सकता है या अन्य यादृच्छिक डेटा का उपयोग किया जा सकता है जो यादृच्छिकता के लिए परीक्षण में सफल होता है।


== पृष्ठभूमि ==
== पृष्ठभूमि ==
यादृच्छिकता का मुद्दा एक महत्वपूर्ण दार्शनिक और सैद्धांतिक प्रश्न है। यादृच्छिकता के लिए टेस्ट का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि डेटा सेट में पहचानने योग्य पैटर्न है या नहीं, जो इंगित करेगा कि जिस प्रक्रिया ने इसे उत्पन्न किया है वह काफी गैर-यादृच्छिक है। अधिकांश भाग के लिए, सांख्यिकीय विश्लेषण, व्यवहार में, यादृच्छिकता के परीक्षण के विपरीत डेटा में नियमितता खोजने के लिए अधिक चिंतित रहा है। आज उपयोग में आने वाले कई यादृच्छिक संख्या जेनरेटर एल्गोरिदम द्वारा परिभाषित किए जाते हैं, और वास्तव में छद्म-यादृच्छिक संख्या जेनरेटर भी हैं। वे जो अनुक्रम उत्पन्न करते हैं उन्हें छद्म-यादृच्छिक अनुक्रम कहा जाता है। ये जनरेटर हमेशा अनुक्रम उत्पन्न नहीं करते हैं जो पर्याप्त रूप से यादृच्छिक होते हैं, बल्कि इसके बजाय ऐसे अनुक्रम उत्पन्न कर सकते हैं जिनमें पैटर्न होते हैं। उदाहरण के लिए, कुख्यात [[RANDU]] दिनचर्या वर्णक्रमीय परीक्षण सहित कई यादृच्छिकता परीक्षणों को नाटकीय रूप से विफल करती है।
यादृच्छिकता का विवाद महत्वपूर्ण दार्शनिक और सैद्धांतिक प्रश्न है। यादृच्छिकता के लिए परीक्षण का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि डेटा सेट में पहचानने योग्य पैटर्न है या नहीं जो इंगित करेगा कि जिस प्रक्रिया ने इसे उत्पन्न किया है वह अधिक गैर-यादृच्छिक है। अधिकांश भाग के लिए सांख्यिकीय विश्लेषण व्यवहार में यादृच्छिकता के परीक्षण के विपरीत डेटा में नियमितता खोजने के लिए अधिक चिंतित रहा है। आज उपयोग में आने वाले कई यादृच्छिक संख्या जेनरेटर एल्गोरिदम द्वारा परिभाषित किए जाते हैं और वास्तव में छद्म-यादृच्छिक संख्या जेनरेटर भी हैं। वे जो अनुक्रम उत्पन्न करते हैं उन्हें छद्म-यादृच्छिक अनुक्रम कहा जाता है। ये जनरेटर सदैव अनुक्रम उत्पन्न नहीं करते हैं जो पर्याप्त रूप से यादृच्छिक होते हैं बल्कि इसके स्थान पर ऐसे अनुक्रम उत्पन्न कर सकते हैं जिनमें पैटर्न होते हैं। उदाहरण के लिए कुख्यात [[RANDU]] नियमित वर्णक्रमीय परीक्षण सहित कई यादृच्छिकता परीक्षणों को नाटकीय रूप से विफल करती है।


[[स्टीफन वोल्फ्राम]] ने यादृच्छिक संख्या उत्पन्न करने की अपनी क्षमता की जांच करने के लिए [[नियम 30]] के आउटपुट पर यादृच्छिकता परीक्षण का इस्तेमाल किया,<ref>{{Cite book|last=Wolfram|first=Stephen|title=एक नए तरह का विज्ञान|publisher=Wolfram Media, Inc.|year=2002|pages=[https://archive.org/details/newkindofscience00wolf/page/975 975–976]|isbn=978-1-57955-008-0|url-access=registration|url=https://archive.org/details/newkindofscience00wolf/page/975}}</ref> हालांकि यह दिखाया गया था कि इसका प्रभावी कुंजी आकार इसके वास्तविक आकार से बहुत छोटा है<ref>{{citation|author1=Willi Meier|author2=Othmar Staffelbach|title=Analysis of pseudo random sequences generated by cellular automata|journal=Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91. Lecture Notes in Computer Science 547|pages=186|year=1991}}</ref> और [[ची-चुकता परीक्षण]] में खराब प्रदर्शन करने के लिए।<ref>{{citation|author1=Moshe Sipper|author2=Marco Tomassini|title=Generating parallel random number generators by cellular programming|journal=International Journal of Modern Physics C|volume=7|number=2|year=1996|pages=181–190|doi=10.1142/S012918319600017X|bibcode=1996IJMPC...7..181S |citeseerx=10.1.1.21.870}}.</ref> एक अकल्पनीय यादृच्छिक संख्या जनरेटर का उपयोग सांख्यिकीय मान्यताओं का उल्लंघन करके एक प्रयोग की वैधता को संदेह में डाल सकता है। हालांकि आमतौर पर एनआईएसटी मानकों जैसे सांख्यिकीय परीक्षण तकनीकों का उपयोग किया जाता है, योंगगे वांग ने दिखाया कि एनआईएसटी मानक पर्याप्त नहीं हैं। इसके अलावा, योंगगे वैंग<ref>Yongge Wang.  On the Design of LIL Tests for (Pseudo) Random Generators and Some Experimental Results, http://webpages.uncc.edu/yonwang/, 2014</ref> डिजाइन किए गए सांख्यिकीय-दूरी-आधारित और कानून-के-पुनरावृत्त-लघुगणक-आधारित परीक्षण तकनीकें। इस तकनीक का उपयोग करते हुए, योंगगे वैंग और टोनी निकोल<ref>{{citation|author1=Yongge Wang |author2=Tony Nicol|title=Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL|journal= Esorics 2014, LNCS 8712 |pages=454–471|year=2014}}</ref> आमतौर पर उपयोग किए जाने वाले छद्म यादृच्छिक जनरेटर जैसे प्रसिद्ध रैंडम नंबर जनरेटर अटैक # डेबियन ओपनएसएसएल में कमजोरी का पता लगाया गया था जिसे 2008 में तय किया गया था।
[[स्टीफन वोल्फ्राम]] ने यादृच्छिक संख्या उत्पन्न करने की अपनी क्षमता की जांच करने के लिए [[नियम 30]] के आउटपुट पर यादृच्छिकता परीक्षण का उपयोग किया<ref>{{Cite book|last=Wolfram|first=Stephen|title=एक नए तरह का विज्ञान|publisher=Wolfram Media, Inc.|year=2002|pages=[https://archive.org/details/newkindofscience00wolf/page/975 975–976]|isbn=978-1-57955-008-0|url-access=registration|url=https://archive.org/details/newkindofscience00wolf/page/975}}</ref> तथा इसके माध्यम से यह प्रदर्शित किया गया था कि इसका प्रभावी कुंजी आकार इसके वास्तविक आकार से बहुत छोटा है<ref>{{citation|author1=Willi Meier|author2=Othmar Staffelbach|title=Analysis of pseudo random sequences generated by cellular automata|journal=Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91. Lecture Notes in Computer Science 547|pages=186|year=1991}}</ref> और [[ची-चुकता परीक्षण|ची-वर्ग परीक्षण]] में अनुपयुक्त प्रदर्शन करता है।<ref>{{citation|author1=Moshe Sipper|author2=Marco Tomassini|title=Generating parallel random number generators by cellular programming|journal=International Journal of Modern Physics C|volume=7|number=2|year=1996|pages=181–190|doi=10.1142/S012918319600017X|bibcode=1996IJMPC...7..181S |citeseerx=10.1.1.21.870}}.</ref> अकल्पनीय यादृच्छिक संख्या जनरेटर का उपयोग सांख्यिकीय मान्यताओं का उल्लंघन करके एक प्रयोग की वैधता को संदेह में डाल सकता है। जबकि सामान्य रूप से NIST मानकों जैसे सांख्यिकीय परीक्षण तकनीकों का उपयोग किया जाता है तथा योंगगे वांग ने दिखाया कि NIST मानक पर्याप्त नहीं हैं। इसके अतिरिक्त योंगगे वैंग<ref>Yongge Wang.  On the Design of LIL Tests for (Pseudo) Random Generators and Some Experimental Results, http://webpages.uncc.edu/yonwang/, 2014</ref> रूपित किए गए सांख्यिकीय-दूरी-आधारित और नियम-के-पुनरावृत्त-लघुगणक-आधारित परीक्षण तकनीकें। इस तकनीक का उपयोग करते हुए योंगगे वैंग और टोनी निकोल<ref>{{citation|author1=Yongge Wang |author2=Tony Nicol|title=Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL|journal= Esorics 2014, LNCS 8712 |pages=454–471|year=2014}}</ref> ने आमतौर पर उपयोग किए जाने वाले छद्म यादृच्छिक जनरेटर में कमजोरी का पता लगाया जैसे कि ओपनएसएसएल छद्म यादृच्छिक जनरेटर का प्रसिद्ध डेबियन संस्करण जिसे 2008 में ठीक किया गया था।


== यादृच्छिकता के लिए विशिष्ट परीक्षण ==
== यादृच्छिकता के लिए विशिष्ट परीक्षण ==
व्यवहार में उपयोग किए जाने वाले विभिन्न प्रकार के (छद्म-) यादृच्छिक संख्या जनरेटर की काफी कम संख्या रही है। वे [[यादृच्छिक संख्या जनरेटर की सूची]] में पाए जा सकते हैं, और इसमें शामिल हैं:
व्यवहार में उपयोग किए जाने वाले विभिन्न प्रकार के (छद्म-) यादृच्छिक संख्या जनरेटर की बहुत कम संख्या रही है। वे [[यादृच्छिक संख्या जनरेटर की सूची]] में प्राप्त किये जा सकते हैं और इसमें सम्मिलित हैं:
*रैखिक सर्वांगसम जनरेटर और [[लीनियर-फीडबैक शिफ्ट रजिस्टर]]
*रैखिक सर्वांगसम जनरेटर और [[लीनियर-फीडबैक शिफ्ट रजिस्टर]]
* सामान्यीकृत फाइबोनैचि जनरेटर
* सामान्यीकृत फाइबोनैचि जनरेटर
Line 16: Line 17:
* [[छद्म आयामी [[द्विआधारी अनुक्रम]]]]
* [[छद्म आयामी [[द्विआधारी अनुक्रम]]]]


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


एक द्विआधारी अनुक्रम के लिए यादृच्छिकता के कई व्यावहारिक उपाय हैं। इनमें [[सांख्यिकीय परीक्षण]], हैडमार्ड परिवर्तन, और [[जटिलता]] या इनके मिश्रण के आधार पर उपाय शामिल हैं। परीक्षणों का एक प्रसिद्ध और व्यापक रूप से उपयोग किया जाने वाला संग्रह डाईहार्ड परीक्षण था, जिसे मार्सग्लिया द्वारा प्रस्तुत किया गया था; इसे L'Ecuyer और Simard द्वारा [[TestU01]] सुइट तक बढ़ाया गया था। यादृच्छिकता को मापने के लिए हैडमार्ड रूपांतरण का उपयोग सुभाष काक | एस द्वारा प्रस्तावित किया गया था। काक और फिलिप्स, यूएन, हॉपकिंस, बेथ और दाई, मुंड और [[जॉर्ज मार्सग्लिया]] और ज़मान द्वारा विकसित किया गया।<ref name="Rit">
द्विआधारी अनुक्रम के लिए यादृच्छिकता के कई व्यावहारिक उपाय हैं। इनमें [[सांख्यिकीय परीक्षण]], हैडमार्ड परिवर्तन, और [[जटिलता]] या इनके मिश्रण के आधार पर उपाय सम्मिलित हैं। परीक्षणों का एक प्रसिद्ध और व्यापक रूप से उपयोग किया जाने वाला संग्रह डाईहार्ड परीक्षण था जिसे मार्सग्लिया द्वारा प्रस्तुत किया गया था तथा इसे L'Ecuyer और सीमार्ड द्वारा [[TestU01|U01परीक्षण]] सुइट तक बढ़ाया गया था। यादृच्छिकता को मापने के लिए हैडमार्ड रूपांतरण का उपयोग सुभाष काक द्वारा प्रस्तावित किया गया था। काक और फिलिप्स, यूएन, हॉपकिंस, बेथ और दाई, मुंड और [[जॉर्ज मार्सग्लिया]] और ज़मान द्वारा विकसित किया गया।<ref name="Rit">
   Terry Ritter, "Randomness tests: a literature survey", webpage:
   Terry Ritter, "Randomness tests: a literature survey", webpage:
   [http://www.ciphersbyritter.com/RES/RANDTEST.HTM CBR-rand].
   [http://www.ciphersbyritter.com/RES/RANDTEST.HTM CBR-rand].
</ref>
</ref>
इनमें से कई परीक्षण, जो रैखिक जटिलता के हैं, यादृच्छिकता के वर्णक्रमीय उपाय प्रदान करते हैं। टी. बेथ और जेड-डी। दाई ने दिखाया कि कोल्मोगोरोव जटिलता और रैखिक जटिलता व्यावहारिक रूप से समान हैं,<ref>Beth, T. and Z-D. Dai. 1989. On the Complexity of Pseudo-Random Sequences -- or: If You Can Describe a Sequence It Can't be Random. Advances in Cryptology -- EUROCRYPT '89. 533-543. Springer-Verlag</ref> हालांकि वाई. वांग ने बाद में दिखाया कि उनके दावे गलत हैं।<ref>Yongge Wang 1999. Linear complexity versus pseudorandomness: on Beth and Dai's result. In: Proc. Asiacrypt 99, pages 288--298. LNCS 1716, Springer Verlag</ref> फिर भी, वांग ने यह भी प्रदर्शित किया कि मार्टिन-लोफ यादृच्छिक अनुक्रमों के लिए, कोल्मोगोरोव जटिलता अनिवार्य रूप से रैखिक जटिलता के समान है।


ये व्यावहारिक परीक्षण [[स्ट्रिंग (कंप्यूटर विज्ञान)]] की यादृच्छिकता की तुलना करना संभव बनाते हैं। संभाव्य आधार पर, दी गई लंबाई के सभी तारों में समान यादृच्छिकता होती है। हालाँकि अलग-अलग तारों में एक अलग कोलमोगोरोव जटिलता है। उदाहरण के लिए, निम्नलिखित दो तारों पर विचार करें।
इनमें से कई परीक्षण जो रैखिक जटिलता के हैं, यादृच्छिकता के वर्णक्रमीय उपाय प्रदान करते हैं। टी. बेथ और जेड-डी. दाई ने प्रदर्शित किया कि कोल्मोगोरोव जटिलता और रैखिक जटिलता व्यावहारिक रूप से समान हैं<ref>Beth, T. and Z-D. Dai. 1989. On the Complexity of Pseudo-Random Sequences -- or: If You Can Describe a Sequence It Can't be Random. Advances in Cryptology -- EUROCRYPT '89. 533-543. Springer-Verlag</ref> जबकि वाई. वांग ने इसके पश्चात दिखाया कि उनके कथन गलत हैं।<ref>Yongge Wang 1999. Linear complexity versus pseudorandomness: on Beth and Dai's result. In: Proc. Asiacrypt 99, pages 288--298. LNCS 1716, Springer Verlag</ref> इसके पश्चात भी वांग ने यह भी प्रदर्शित किया कि मार्टिन-लोफ यादृच्छिक अनुक्रमों के लिए कोल्मोगोरोव जटिलता अनिवार्य रूप से रैखिक जटिलता के समान है।
 
ये व्यावहारिक परीक्षण [[स्ट्रिंग (कंप्यूटर विज्ञान)]] की यादृच्छिकता की तुलना करना संभव बनाते हैं। संभाव्य आधार पर दी गई लंबाई के सभी स्ट्रिंग में समान यादृच्छिकता होती है। जबकि भिन्न-भिन्न स्ट्रिंग में एक अलग कोलमोगोरोव जटिलता है। उदाहरण के लिए निम्नलिखित दो स्ट्रिंग पर विचार करें।


: स्ट्रिंग 1: <code>0101010101010101010101010101010101010101010101010101010101010101</code>
: स्ट्रिंग 1: <code>0101010101010101010101010101010101010101010101010101010101010101</code>
: स्ट्रिंग 2: <code>1100100001100001110111101110110011111010010000100101011110010110</code>
: स्ट्रिंग 2: <code>1100100001100001110111101110110011111010010000100101011110010110</code>
स्ट्रिंग 1 एक संक्षिप्त भाषाई विवरण स्वीकार करता है: '01' के 32 दोहराव। इस विवरण में 22 अक्षर हैं, और इसे कुछ आधार अनुक्रमों से कुशलतापूर्वक बनाया जा सकता है।{{clarify|date=November 2017}} स्ट्रिंग 2 में स्वयं स्ट्रिंग लिखने के अलावा कोई स्पष्ट सरल विवरण नहीं है, जिसमें 64 वर्ण हैं,{{clarify|date=November 2017|reason=The description 'base64 yGHe7PpCV5Y=' would just have 19 characters. See talk page.}} और इसका कोई तुलनात्मक रूप से कुशल आधार फ़ंक्शन प्रतिनिधित्व नहीं है। लीनियर हैडमार्ड स्पेक्ट्रल टेस्ट (हैडमार्ड ट्रांसफ़ॉर्म देखें) का उपयोग करते हुए, इनमें से पहला क्रम दूसरे की तुलना में बहुत कम यादृच्छिकता वाला पाया जाएगा, जो अंतर्ज्ञान से सहमत है।
स्ट्रिंग 1 संक्षिप्त भाषाई विवरण स्वीकार करता है: '01' के 32 दोहराव। इस विवरण में 22 अक्षर हैं और इसे कुछ आधार अनुक्रमों से कुशलतापूर्वक बनाया जा सकता है।{{clarify|date=November 2017}} स्ट्रिंग 2 में स्वयं स्ट्रिंग लिखने के अतिरिक्त कोई स्पष्ट सरल विवरण नहीं है जिसमें 64 वर्ण हैं{{clarify|date=November 2017|reason=The description 'base64 yGHe7PpCV5Y=' would just have 19 characters. See talk page.}} और इसका कोई तुलनात्मक रूप से कुशल आधार फ़ंक्शन प्रतिनिधित्व नहीं है। लीनियर हैडमार्ड स्पेक्ट्रल परीक्षण (हैडमार्ड ट्रांसफ़ॉर्म देखें) का उपयोग करते हुए इनमें से पहला क्रम दूसरे की तुलना में बहुत कम यादृच्छिकता वाला पाया जाएगा जो सहज ज्ञान से सहमत है।


== उल्लेखनीय सॉफ्टवेयर कार्यान्वयन ==
== उल्लेखनीय सॉफ्टवेयर कार्यान्वयन ==
* कठोर परीक्षण
* कठोर परीक्षण
* परीक्षणU01
* U01 परीक्षण
* फोरमिलाब से ईएनटी उपयोगिता<ref>[https://www.fourmilab.ch/random/ ENT: A Pseudorandom Number Sequence Test Program], Fourmilab, 2008.</ref>
* फोरमिलाब द्वारा ENT उपयोगिता<ref>[https://www.fourmilab.ch/random/ ENT: A Pseudorandom Number Sequence Test Program], Fourmilab, 2008.</ref>
* [[एनआईएसटी]] सांख्यिकीय टेस्ट सूट<ref>[https://github.com/terrillmoore/NIST-Statistical-Test-Suite/raw/master/assets/nistspecialpublication800-22r1a.pdf A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications], Special Publication 800-22 Revision 1a, [[National Institute of Standards and Technology]], 2010.</ref><ref>[https://github.com/terrillmoore/NIST-Statistical-Test-Suite Implementation of the NIST Statistical Test Suite]</ref>
* [[एनआईएसटी|NIST]] सांख्यिकीय परीक्षण सूट<ref>[https://github.com/terrillmoore/NIST-Statistical-Test-Suite/raw/master/assets/nistspecialpublication800-22r1a.pdf A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications], Special Publication 800-22 Revision 1a, [[National Institute of Standards and Technology]], 2010.</ref><ref>[https://github.com/terrillmoore/NIST-Statistical-Test-Suite Implementation of the NIST Statistical Test Suite]</ref>




Revision as of 23:49, 30 June 2023

Not to be confused with यादृच्छिकता परीक्षण.

डेटा मूल्यांकन में यादृच्छिकता परीक्षण (या यादृच्छिकता के लिए परीक्षण) डेटा के सेट के वितरण का विश्लेषण करने के लिए उपयोग किया जाने वाला परीक्षण है एवं यह देखने के लिए कि क्या इसे यादृच्छिक (पैटर्न रहित) के रूप में वर्णित किया जा सकता है। स्टोकेस्टिक मॉडलिंग में कुछ कंप्यूटर सिमुलेशन के रूप में संभावित इनपुट डेटा की यादृच्छिकता के लिए आशा की जा सकती है तथा यादृच्छिकता के लिए औपचारिक परीक्षण द्वारा सत्यापित किया जा सकता है एवं यह दिखाने के लिए कि सिमुलेशन रन में उपयोग के लिए डेटा मान्य हैं। कुछ स्थितियों में डेटा स्पष्ट गैर-यादृच्छिक बनावट प्रकट करता है जैसा कि डेटा में तथाकथित रन के साथ होता है (जैसे कि यादृच्छिक 0–9 की आशा करना परन्तु 4 3 2 1 0 4 3 2 1 ... और संभवतः ही कभी 4 से ऊपर जाना)। यदि डेटा का चयनित सेट परीक्षणों में विफल रहता है तो मापदंडों को परिवर्तित किया जा सकता है या अन्य यादृच्छिक डेटा का उपयोग किया जा सकता है जो यादृच्छिकता के लिए परीक्षण में सफल होता है।

पृष्ठभूमि

यादृच्छिकता का विवाद महत्वपूर्ण दार्शनिक और सैद्धांतिक प्रश्न है। यादृच्छिकता के लिए परीक्षण का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि डेटा सेट में पहचानने योग्य पैटर्न है या नहीं जो इंगित करेगा कि जिस प्रक्रिया ने इसे उत्पन्न किया है वह अधिक गैर-यादृच्छिक है। अधिकांश भाग के लिए सांख्यिकीय विश्लेषण व्यवहार में यादृच्छिकता के परीक्षण के विपरीत डेटा में नियमितता खोजने के लिए अधिक चिंतित रहा है। आज उपयोग में आने वाले कई यादृच्छिक संख्या जेनरेटर एल्गोरिदम द्वारा परिभाषित किए जाते हैं और वास्तव में छद्म-यादृच्छिक संख्या जेनरेटर भी हैं। वे जो अनुक्रम उत्पन्न करते हैं उन्हें छद्म-यादृच्छिक अनुक्रम कहा जाता है। ये जनरेटर सदैव अनुक्रम उत्पन्न नहीं करते हैं जो पर्याप्त रूप से यादृच्छिक होते हैं बल्कि इसके स्थान पर ऐसे अनुक्रम उत्पन्न कर सकते हैं जिनमें पैटर्न होते हैं। उदाहरण के लिए कुख्यात RANDU नियमित वर्णक्रमीय परीक्षण सहित कई यादृच्छिकता परीक्षणों को नाटकीय रूप से विफल करती है।

स्टीफन वोल्फ्राम ने यादृच्छिक संख्या उत्पन्न करने की अपनी क्षमता की जांच करने के लिए नियम 30 के आउटपुट पर यादृच्छिकता परीक्षण का उपयोग किया[1] तथा इसके माध्यम से यह प्रदर्शित किया गया था कि इसका प्रभावी कुंजी आकार इसके वास्तविक आकार से बहुत छोटा है[2] और ची-वर्ग परीक्षण में अनुपयुक्त प्रदर्शन करता है।[3] अकल्पनीय यादृच्छिक संख्या जनरेटर का उपयोग सांख्यिकीय मान्यताओं का उल्लंघन करके एक प्रयोग की वैधता को संदेह में डाल सकता है। जबकि सामान्य रूप से NIST मानकों जैसे सांख्यिकीय परीक्षण तकनीकों का उपयोग किया जाता है तथा योंगगे वांग ने दिखाया कि NIST मानक पर्याप्त नहीं हैं। इसके अतिरिक्त योंगगे वैंग[4] रूपित किए गए सांख्यिकीय-दूरी-आधारित और नियम-के-पुनरावृत्त-लघुगणक-आधारित परीक्षण तकनीकें। इस तकनीक का उपयोग करते हुए योंगगे वैंग और टोनी निकोल[5] ने आमतौर पर उपयोग किए जाने वाले छद्म यादृच्छिक जनरेटर में कमजोरी का पता लगाया जैसे कि ओपनएसएसएल छद्म यादृच्छिक जनरेटर का प्रसिद्ध डेबियन संस्करण जिसे 2008 में ठीक किया गया था।

यादृच्छिकता के लिए विशिष्ट परीक्षण

व्यवहार में उपयोग किए जाने वाले विभिन्न प्रकार के (छद्म-) यादृच्छिक संख्या जनरेटर की बहुत कम संख्या रही है। वे यादृच्छिक संख्या जनरेटर की सूची में प्राप्त किये जा सकते हैं और इसमें सम्मिलित हैं:

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

द्विआधारी अनुक्रम के लिए यादृच्छिकता के कई व्यावहारिक उपाय हैं। इनमें सांख्यिकीय परीक्षण, हैडमार्ड परिवर्तन, और जटिलता या इनके मिश्रण के आधार पर उपाय सम्मिलित हैं। परीक्षणों का एक प्रसिद्ध और व्यापक रूप से उपयोग किया जाने वाला संग्रह डाईहार्ड परीक्षण था जिसे मार्सग्लिया द्वारा प्रस्तुत किया गया था तथा इसे L'Ecuyer और सीमार्ड द्वारा U01परीक्षण सुइट तक बढ़ाया गया था। यादृच्छिकता को मापने के लिए हैडमार्ड रूपांतरण का उपयोग सुभाष काक द्वारा प्रस्तावित किया गया था। काक और फिलिप्स, यूएन, हॉपकिंस, बेथ और दाई, मुंड और जॉर्ज मार्सग्लिया और ज़मान द्वारा विकसित किया गया।[6]

इनमें से कई परीक्षण जो रैखिक जटिलता के हैं, यादृच्छिकता के वर्णक्रमीय उपाय प्रदान करते हैं। टी. बेथ और जेड-डी. दाई ने प्रदर्शित किया कि कोल्मोगोरोव जटिलता और रैखिक जटिलता व्यावहारिक रूप से समान हैं[7] जबकि वाई. वांग ने इसके पश्चात दिखाया कि उनके कथन गलत हैं।[8] इसके पश्चात भी वांग ने यह भी प्रदर्शित किया कि मार्टिन-लोफ यादृच्छिक अनुक्रमों के लिए कोल्मोगोरोव जटिलता अनिवार्य रूप से रैखिक जटिलता के समान है।

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

स्ट्रिंग 1: 0101010101010101010101010101010101010101010101010101010101010101
स्ट्रिंग 2: 1100100001100001110111101110110011111010010000100101011110010110

स्ट्रिंग 1 संक्षिप्त भाषाई विवरण स्वीकार करता है: '01' के 32 दोहराव। इस विवरण में 22 अक्षर हैं और इसे कुछ आधार अनुक्रमों से कुशलतापूर्वक बनाया जा सकता है।[clarification needed] स्ट्रिंग 2 में स्वयं स्ट्रिंग लिखने के अतिरिक्त कोई स्पष्ट सरल विवरण नहीं है जिसमें 64 वर्ण हैं[clarification needed] और इसका कोई तुलनात्मक रूप से कुशल आधार फ़ंक्शन प्रतिनिधित्व नहीं है। लीनियर हैडमार्ड स्पेक्ट्रल परीक्षण (हैडमार्ड ट्रांसफ़ॉर्म देखें) का उपयोग करते हुए इनमें से पहला क्रम दूसरे की तुलना में बहुत कम यादृच्छिकता वाला पाया जाएगा जो सहज ज्ञान से सहमत है।

उल्लेखनीय सॉफ्टवेयर कार्यान्वयन

  • कठोर परीक्षण
  • U01 परीक्षण
  • फोरमिलाब द्वारा ENT उपयोगिता[9]
  • NIST सांख्यिकीय परीक्षण सूट[10][11]


यह भी देखें

टिप्पणियाँ

  1. ↑ Wolfram, Stephen (2002). एक नए तरह का विज्ञान. Wolfram Media, Inc. pp. 975–976. ISBN 978-1-57955-008-0.
  2. ↑ Willi Meier; Othmar Staffelbach (1991), "Analysis of pseudo random sequences generated by cellular automata", Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91. Lecture Notes in Computer Science 547: 186
  3. ↑ Moshe Sipper; Marco Tomassini (1996), "Generating parallel random number generators by cellular programming", International Journal of Modern Physics C, 7 (2): 181–190, Bibcode:1996IJMPC...7..181S, CiteSeerX 10.1.1.21.870, doi:10.1142/S012918319600017X.
  4. ↑ Yongge Wang. On the Design of LIL Tests for (Pseudo) Random Generators and Some Experimental Results, http://webpages.uncc.edu/yonwang/, 2014
  5. ↑ Yongge Wang; Tony Nicol (2014), "Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL", Esorics 2014, LNCS 8712: 454–471
  6. ↑ Terry Ritter, "Randomness tests: a literature survey", webpage: CBR-rand.
  7. ↑ Beth, T. and Z-D. Dai. 1989. On the Complexity of Pseudo-Random Sequences -- or: If You Can Describe a Sequence It Can't be Random. Advances in Cryptology -- EUROCRYPT '89. 533-543. Springer-Verlag
  8. ↑ Yongge Wang 1999. Linear complexity versus pseudorandomness: on Beth and Dai's result. In: Proc. Asiacrypt 99, pages 288--298. LNCS 1716, Springer Verlag
  9. ↑ ENT: A Pseudorandom Number Sequence Test Program, Fourmilab, 2008.
  10. ↑ A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, Special Publication 800-22 Revision 1a, National Institute of Standards and Technology, 2010.
  11. ↑ Implementation of the NIST Statistical Test Suite


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=यादृच्छिकता_परीक्षण&oldid=208439’