छद्म यादृच्छिक संख्या पीढ़ी

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

परिचय

यह कहने लायक है कि यह एक समान वितरण कानून के साथ केवल यादृच्छिक संख्या उत्पन्न करने के लिए समझ में आता है, क्योंकि अन्य सभी वितरण समानताओं से संभाव्यता सिद्धांत से ज्ञात परिवर्तनों द्वारा प्राप्त किए जा सकते हैं।
उन लोगों के लिए जो अभी तक संभावना सिद्धांत का अध्ययन नहीं कर पाए हैं या नहीं कर रहे हैं, मुझे याद है कि शून्य और लोगों के समान रूप से वितरित अनुक्रम में, औसतन (!) मामलों के 50% मामलों में होगा। लेकिन इसका मतलब यह बिल्कुल नहीं है कि 1000 अंकों के अनुक्रम में बिल्कुल 500 शून्य होंगे। इसके अलावा, 1000 अंकों के अनुक्रम में, 999 शून्य हो सकते हैं, और संभावना है कि हजारवां तत्व शून्य अभी भी 0.5 के बराबर है। पहली नज़र में, यह विरोधाभास लगता है, लेकिन यह समझना महत्वपूर्ण है कि सभी अनुक्रम समान रूप से संभावित हैं। यदि हम इस तरह के अनुक्रमों के एक पर्याप्त बड़े सेट पर विचार करते हैं, तो औसतन (!) उनमें से प्रत्येक में 500 शून्य होंगे।
सिद्धांत को थोड़ा याद करने के बाद, हम इतिहास को पारित करेंगे। पूर्व-कंप्यूटर समय में, बैग, ड्राइंग कार्ड और पासा फेंकने से बहु-रंगीन गेंदों को खींचकर यादृच्छिक संख्या प्राप्त की गई थी। यह स्पष्ट है कि इस तरह से गंभीर शोध करना असंभव था, इसलिए 1927 में टिप्पीट ने यादृच्छिक संख्याओं की पहली तालिका प्रकाशित की। थोड़ी देर बाद, लोगों ने किसी तरह इस प्रक्रिया को स्वचालित करने की कोशिश की। यादृच्छिक संख्या उत्पन्न करने वाली मशीनें दिखाई देने लगीं। अब इस तरह के उपकरणों का भी उपयोग किया जाता है और एंट्रोपी के स्रोत (जनरेटर) कहलाते हैं। यह ध्यान देने योग्य है कि केवल ऐसे उपकरण वास्तव में यादृच्छिक संख्या दे सकते हैं। लेकिन, दुर्भाग्य से, एन्ट्रापी जनरेटर काफी महंगे हैं, और उन्हें हर पीसी में स्थापित करना संभव नहीं है। यही कारण है कि यादृच्छिक संख्या प्राप्त करने के लिए एल्गोरिदम की आवश्यकता है।

मेमोरी बैंडविड्थ प्राप्त करने का पहला प्रयास

कुछ लोग सोचते हैं कि यादृच्छिक संख्या प्राप्त करना आसान है। उनकी राय में, इसके लिए यह मूल संख्या पर यादृच्छिक जटिल गणितीय संचालन करने के लिए पर्याप्त है। अगर हम जाने-माने नॉट का दूसरा वॉल्यूम खोलते हैं, तो हमें पता चलेगा कि 1959 में नॉट ने भी इस तरह के विचार के आधार पर एक जनरेटर बनाने की कोशिश की थी। उनका एल्गोरिथम इस तरह दिखता था:
K1। [पुनरावृत्तियों की संख्या का चयन करें।] Y को सबसे बड़ा महत्वपूर्ण अंक X असाइन करें। (हम K2-K13 के चरणों को ठीक Y + 1 बार निष्पादित करेंगे, अर्थात, हम यादृच्छिक परिवर्तनों को एक यादृच्छिक संख्या में लागू करेंगे।)
K2। [एक यादृच्छिक कदम चुनें] अगले सबसे बड़े महत्वपूर्ण अंक को निर्दिष्ट करें। चरण K (3 + Z) पर जाएं, अर्थात, प्रोग्राम में एक यादृच्छिक रूप से चयनित चरण के लिए।
शॉर्ट सर्किट। [प्रदान करें> 5 x 109] यदि X <5,000,000,000, X को X + 5,000,000,000 का मान प्रदान करें।
K4। [वर्ग का मध्य।] X को X के वर्ग के मध्य से बदलें।
K5। [गुणा करें।] एक्स को नंबर (1001001001 X) मॉड 1010 के साथ बदलें।
K6। [छद्म-पूरक।] यदि X <100000000 है, तो X को मान X + 9814055677 निर्दिष्ट करें; अन्यथा X से 1010-X पर सेट करें।
K7। [पुनर्वसन आधा करें।] पुराने वाले पांच निचले क्रम के वर्णों को स्वैप करें।
K8। [गुणा करें।] चरण K5 करें।
K9। [संख्याओं में कमी करें।] संख्या X के दशमलव प्रतिनिधित्व के प्रत्येक गैर-शून्य अंक को एक-एक करके घटाएं।
K10। [99999 पर संशोधित करें।] यदि A '<105, X मान असाइन करें - X 2 +99999; अन्यथा X का मान निर्दिष्ट करें - 99999।
K11। [सामान्य करें।] (इस चरण पर, A 'शून्य के बराबर नहीं हो सकता।) यदि X <109, तो X को 10 से गुणा करें।
K12। [मध्य-वर्ग पद्धति का संशोधन।] X को X (X - 1) के मध्य 10 अंकों से बदलें।
K13। [दोहराएं?] यदि Y> 0, Y को 1 से घटाएं और चरण K2 पर लौटें। यदि Y = 0, एल्गोरिथ्म पूरा हो गया है। पिछले चरण में प्राप्त संख्या X का मान वांछित "यादृच्छिक" मूल्य होगा।
स्पष्ट जटिलता के बावजूद, यह एल्गोरिथ्म जल्दी से संख्या 6065038420 में परिवर्तित हो गया, जो कि कुछ ही कदमों के बाद खुद में बदल गया। इस कहानी का नैतिक यह है कि आप यादृच्छिक संख्याओं को प्राप्त करने के लिए एक यादृच्छिक एल्गोरिथ्म का उपयोग नहीं कर सकते हैं।

रैखिक सर्वांगसम विधि

अधिकांश प्रोग्रामिंग भाषाओं में, इस पद्धति का उपयोग यादृच्छिक संख्याओं को प्राप्त करने के लिए मानक फ़ंक्शन में किया जाता है। यह विधि पहली बार 1949 में लेहमर द्वारा प्रस्तावित की गई थी। 4 नंबर चुने गए हैं:

1. मॉड्यूल एम (एम> 0);
2. कारक a (0 <= a <m);
3. वेतन वृद्धि c (0 <= c <m);
4. प्रारंभिक मान X ₀ (0 <= X ₀ <m)

अनुक्रम निम्न पुनरावृत्ति सूत्र का उपयोग करके प्राप्त किया जाता है: X _{n + 1} = (* * X _n + c) mod m।
यह विधि वास्तव में अच्छा छद्म आयामी संख्या देती है, लेकिन यदि आप संख्याओं को एक, सी, मनमाने ढंग से लेते हैं, तो परिणाम हमें सबसे अधिक निराश करेगा। M = 7, X ₀ = 1, a = 2, c = 4 के साथ, हमें निम्नलिखित अनुक्रम मिलते हैं: 1,6,2,1,6,2,1, ...
जाहिर है, यह अनुक्रम यादृच्छिक की परिभाषा में बिल्कुल फिट नहीं है। हालाँकि, इस विफलता ने हमें दो महत्वपूर्ण निष्कर्ष निकालने की अनुमति दी:

1. संख्या m, a, c, X ₀ यादृच्छिक नहीं होना चाहिए;
2. रैखिक सर्वांगसम विधि हमें दोहराव प्रदान करती है।

वास्तव में, कोई भी फ़ंक्शन जो एक सीमित सेट X से X को मैप करता है, वह चक्रीय रूप से दोहराया मूल्यों का उत्पादन करेगा। इस प्रकार हमारा कार्य अनुक्रम के अनूठे हिस्से को जितना संभव हो उतना लंबा करना है (वैसे, यह स्पष्ट है कि अद्वितीय भाग की लंबाई मी से अधिक नहीं हो सकती है)।
साक्ष्य के विवरण में जाने के बिना, हम कहते हैं कि अनुक्रम की अवधि केवल मी के बराबर होगी यदि निम्नलिखित तीन शर्तें पूरी होती हैं:

1. संख्या सी और एम नकल है;
2. a-1 प्रत्येक अभाज्य p का एक गुणक है जो m का विभाजक है;
3. यदि m 4 का गुणक है, तो a-1 का गुणक 4 होना चाहिए।

रैखिक अनुरूप विधि के बारे में कहानी के अंत में, यह कहा जाना चाहिए कि इसकी मदद से प्राप्त अनुक्रम, हालांकि वे पर्याप्त रूप से यादृच्छिक हैं, फिर भी क्रिप्टोग्राफिक रूप से स्थिर नहीं हैं। क्योंकि लगातार 4 संख्याओं को जानने के बाद, एक क्रिप्टोकरंसी समीकरणों की एक प्रणाली की रचना कर सकती है जिसमें से कोई एक, सी, एम पा सकता है।

एक बहुपद काउंटर (शिफ्ट रजिस्टर) के आधार पर छद्म यादृच्छिक संख्या प्राप्त करना

अब हम जिस एल्गोरिथ्म पर विचार करेंगे उसका आधार एक्सक्लूसिव OR ऑपरेशन (योग मोडुलो दो) है। बस मामले में, मैं आपको याद दिलाता हूं कि इस फ़ंक्शन की सत्य तालिका क्या दिखती है:

नीचे चित्र में दिखाए गए सर्किट सबसे सरल बहुपद काउंटर हैं। ऐसी योजनाओं में शून्य बिट की गणना अनन्य या फ़ंक्शन के आधार पर की जाती है, और अन्य सभी बिट्स को एक सरल बदलाव द्वारा प्राप्त किया जाता है। जिन बिट्स से सिग्नल एक्सक्लूसिव ओर जाता है, उन्हें टैप कहा जाता है।

गौर करें कि इन रजिस्टरों के मूल्य प्रारंभिक मूल्य 001 के साथ कैसे बदल जाएंगे:


दोनों रजिस्टर समान मूल्य के साथ काम करना शुरू करते हैं, लेकिन फिर रजिस्टरों द्वारा उत्पन्न मूल्यों को जल्दी से विचलन करना शुरू हो जाता है। लेकिन 6 चरणों के बाद, दोनों रजिस्टर अपनी मूल स्थिति में लौट आते हैं।
यह दिखाना आसान है कि इन दोनों रजिस्टरों ने सबसे लंबे समय तक संभव अनुक्रम उत्पन्न किया, जिसमें शून्य को छोड़कर सभी संयोजन शामिल हैं। यानी जब रजिस्टर m की थोड़ी चौड़ाई हो, तो आप लंबाई 2 ^m -1 का अनुक्रम प्राप्त कर सकते हैं।
किसी भी क्षमता के एक बहुपद काउंटर में नल के संयोजन की संख्या होती है जो अधिकतम लंबाई का एक क्रम प्रदान करती है, गलत संयोजनों के उपयोग से छोटे अनुक्रमों की उत्पत्ति होगी। एक अलग और बल्कि कठिन काम झुकता के इन संयोजनों की खोज है।
यह ध्यान देने योग्य है कि ये संयोजन हमेशा अद्वितीय नहीं होते हैं। उदाहरण के लिए, 10-बिट काउंटर के लिए उनमें से दो हैं: [6; 9] और [2; 9], छह अंकों के काउंटर के लिए इस तरह के अट्ठाईस संयोजन हैं।
इन संयोजनों को खोजने के लिए, बहुपद के रूप में काउंटर को प्रस्तुत करना आवश्यक है। उदाहरण से काउंटर इस तरह दिखेंगे: x ² XOR 1 और x ² XOR x XOR 1।

यह सिद्धांत से ज्ञात है कि एक पूर्ण अनुक्रम उत्पन्न करने के लिए आवश्यक और पर्याप्त स्थिति विशेषता बहुपद की प्रधानता है। इसका मतलब है कि:

• एक विशिष्ट बहुपद को कम डिग्री के बहुपद के उत्पाद के रूप में प्रस्तुत नहीं किया जा सकता है;
• विशेषता बहुपद बहुपद z 1 XOR 1 का विभाजक है, δ = 2 ^m -1 के लिए, और 2 <2 ^m -1 के किसी भी अन्य मान के लिए भाजक नहीं है।

एक बहुपद काउंटर के फायदे सॉफ्टवेयर और हार्डवेयर कार्यान्वयन, संचालन की गति और क्रिप्टोग्राफिक ताकत दोनों की सरलता है।

आशा है कि यह लेख आपके लिए उपयोगी रहा होगा।