💻 computer science

Cellular Automata based Resource Efficient Maximally Equidistributed Pseudo-Random Number Generators

यह शोधपत्र लाइटवेट, संयुक्त लीनियर सेलुलर ऑटोमेटा-आधारित छद्म-यादृच्छिक संख्या जनरेटरों (pseudo-random number generators) के एक परिवार का प्रस्ताव और सत्यापन करता है जो अधिकतम आवर्त (maximal period), अधिकतम सम-वितरण (maximal equidistribution) और मर्सिन ट्विस्टर (Mersenne Twister) के तुल्य प्रदर्शन प्राप्त करके मौजूदा CA-PRNGs की सम-वितरण कमजोरियों को दूर करते हैं।

मूल लेखक: Bhuvaneswari A, Kamalika Bhattacharjee

प्रकाशित 2026-03-23

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Bhuvaneswari A, Kamalika Bhattacharjee

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

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

समस्या यह है कि कंप्यूटर वास्तव में बहुत अनुमानित (predictable) होते हैं। वे सख्त नियमों का पालन करते हैं। इसलिए, उन्हें "रैंडम" जैसा व्यवहार करने के लिए मजबूर करना एक बड़ी चुनौती है। यदि नंबर वास्तव में रैंडम नहीं हैं, तो कैसीनो पैसे हार सकता है, या कोई गुप्त कोड क्रैक किया जा सकता है।

यह शोध पत्र एक बेहतर, तेज़ और अधिक कुशल "पासा मशीन" बनाने के बारे में है, जो सेलुलर ऑटोमेटा (Cellular Automata) नामक एक अवधारणा का उपयोग करता है।

यहाँ इस बात की कहानी है कि लेखकों ने टूटी हुई मशीनों को कैसे ठीक किया, जिसे सरल शब्दों में समझाया गया है:

1. समस्या: "बोरिंग" पासे

लेखकों ने मौजूदा मशीनों (जिन्हें लीनियर सेलुलर ऑटोमेटा कहा जाता है) का अध्ययन किया। उन्होंने एक प्रमुख दोष पाया: इक्विडिस्ट्रिब्यूशन (Equidistribution - समान वितरण)।

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

2. समाधान: "दो सिरों वाली" मशीन

इसे ठीक करने के लिए, लेखकों ने एक के बजाय दो मशीनों को मिलाने का निर्णय लिया।

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

3. गुप्त नुस्खा: "स्किप" (समय अंतराल)

यहीं पर जादू हुआ। दो मशीनों को मिलाने के बाद भी, उनके पास एक समस्या थी। क्योंकि ये मशीनें सरल नियमों का पालन करती हैं, वे सुंदर, दोहराए जाने वाले पैटर्न बनाने की प्रवृत्ति रखती हैं—जैसे कि एक सिएरपिंस्की ट्राएंगल (Sierpinski Triangle) (एक फ्रैक्टल त्रिकोणीय आकार)।

उपमा: कल्पना कीजिए कि दो नर्तक (dancers) बिल्कुल तालमेल में नाच रहे हैं। यदि आप उन्हें देखते हैं, तो आप एक सुंदर, अनुमानित पैटर्न देखते हैं। यह रैंडम नहीं है; यह एक कोरियोग्राफी है।
समाधान: लेखकों ने टाइम स्पेसिंग (Time Spacing) पेश किया। मशीनों को हर सेकंड देखने के बजाय, उन्होंने कंप्यूटर को निर्देश दिया कि वह अवलोकन करने के बीच में कुछ सेकंड के लिए स्किप (छोड़ना) करे।
- 1 सेकंड का अंतराल: आप अभी भी पैटर्न देखते हैं।
- 5 सेकंड का अंतराल: पैटर्न टूट जाता है। नर्तक अराजक (chaotic) रूप से चलते हुए दिखाई देते हैं।
- 7 या 8 सेकंड का अंतराल: पैटर्न पूरी तरह से गायब हो जाता है। हलचल शुद्ध शोर (pure noise) जैसी दिखने लगती है।

कदमों को छोड़कर (विशेष रूप से 2 से 10 चरणों के बीच), उन्होंने अनुमानित पैटर्न को नष्ट कर दिया, जिससे "कोरियोग्राफ किए गए नृत्य" को एक अराजक, अप्रत्याशित अव्यवस्था में बदल दिया। इसे ही वे मैक्सिमल इक्विडिस्ट्रिब्यूशन (Maximal Equidistribution) कहते हैं।

4. यह क्यों मायने रखता है: हल्का और तेज़

लेखक केवल एक रैंडम मशीन नहीं चाहते थे; वे एक लाइट-वेट (हल्की) मशीन चाहते थे।

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

सफलता का सारांश

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

संक्षेप में: लेखकों ने सरल, अनुमानित पैटर्न लिए, उन्हें दो पैटर्नों के साथ मिला दिया, और फिर परिणाम को "स्किप-अ-बीट" फिल्टर के माध्यम से देखा। परिणाम एक ऐसा रैंडम नंबर जेनरेटर है जो एक स्मार्टवॉच के लिए छोटा है लेकिन इंटरनेट को सुरक्षित करने के लिए पर्याप्त शक्तिशाली है।

यहाँ शोध पत्र "Cellular Automata based Resource Efficient Maximally Equidistributed Pseudo-Random Number Generators" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र मौजूदा लीनियर छद्म-यादृच्छिक संख्या जनरेटरों (Linear Pseudo-Random Number Generators - PRNGs) की सीमाओं को संबोधित करता है, विशेष रूप से जो सेलुलर ऑटोमेटा (Cellular Automata - CA) और लीनियर फीडबैक शिफ्ट रजिस्टरों (Linear Feedback Shift Registers - LFSRs) पर आधारित हैं।

समदूरता की कमी (Equidistribution Deficit): जबकि मौजूदा लीनियर CA-आधारित PRNGs संसाधन-कुशल और लंबी अवधि वाले होते हैं, वे अधिकतम समदूरता (maximal equidistribution) के गुण को संतुष्ट करने में विफल रहते हैं। यह एक सैद्धांतिक गुणवत्ता मीट्रिक है जो सभी संभावित आयामों (dimensions) में उत्पन्न संख्याओं की एकरूपता को मापता है। मौजूदा CA-PRNGs अक्सर अपनी अराजक प्रकृति के कारण स्व-समान पैटर्न (जैसे कि सिएरपिंस्की त्रिकोण/Sierpinski triangles) प्रदर्शित करते हैं, जिससे उच्च आयामों में सांख्यिकीय यादृच्छिकता (statistical randomness) खराब हो जाती है।
वर्तमान समाधानों में समझौता (Trade-off in Current Solutions):
- टेम्परिंग (Tempering): समदूरता को ठीक करने के लिए आउटपुट ट्रांसफॉर्मेशन फंक्शन (टेम्परिंग) का उपयोग करने से कम्प्यूटेशनल ओवरहेड और हार्डवेयर जटिलता बढ़ जाती है, जो "हल्के-वजन" (light-weight) की आवश्यकता का उल्लंघन करता है।
- संयुक्त जनरेटर (Combined Generators): केवल XOR के माध्यम से कई CAs को संयोजित करना तब विफल हो जाता है जब घटक अवधियों (component periods) को सावधानीपूर्वक प्रबंधित नहीं किया जाता है या यदि अंतर्निहित संरचना में समरूपता बनी रहती है।
- हल्के-वजन की बाधाएं (Light-weight Constraints): आधुनिक अनुप्रयोगों (FPGA, एम्बेडेड सिस्टम, मल्टीकोर CPU) को ऐसे PRNGs की आवश्यकता होती है जो मानक वर्ड साइज (32–128 बिट्स) में फिट हो सकें और संसाधनों का न्यूनतम उपयोग करें, फिर भी वर्तमान हल्के-वजन वाले CA-PRNGs सांख्यिकीय परीक्षणों में विफल हो जाते हैं।

2. कार्यप्रणाली (Methodology)

लेखक लाइट-वेट कंबाइंड CA-आधारित PRNGs डिजाइन करने के लिए एक नया ढांचा प्रस्तावित करते हैं जो जटिल टेम्परिंग फंक्शन के बिना अधिकतम समदूरता प्राप्त करता है।

A. घटक चयन (Component Selection)

लेखक लीनियर मैक्सिमल लेंथ सेलुलर ऑटोमेटा (विशेष रूप से नियम 90 और 150 का उपयोग करने वाले एलिमेंट्री सेलुलर ऑटोमेटा) का उपयोग करते हैं।

स्रोत (Sources): वे दो स्थापित स्रोतों (Ref [4] और Ref [7]) से घटकों का चयन करते हैं जहाँ नियम वेक्टर अत्यधिक समान (मुख्य रूप से नियम 90 या 150, केवल 1 या 2 अपवादों के साथ) हैं। यह हार्डवेयर दक्षता सुनिश्चित करता है।
बाधाएं (Constraints): घटकों का आकार ( $k$ ) कंप्यूटर वर्ड साइज में फिट होने के लिए $32 \le k \le 128$ बिट्स तक सीमित है। सरलता बनाए रखने के लिए घटकों की संख्या दो तक सीमित है।
अराजकता सत्यापन (Chaos Verification): लेखक यह सत्यापित करने के लिए कि ये विशिष्ट CA कॉन्फ़िगरेशन अराजक (chaotic) हैं, P-पैरामीटर का उपयोग करते हैं, ताकि यह सुनिश्चित हो सके कि वे यादृच्छिकता के उपयुक्त स्रोत हैं।

B. समय अंतराल के साथ संयुक्त जनरेटर (The Combined Generator with Time Spacing)

अराजक CAs में अंतर्निहित स्व-समान पैटर्न को तोड़ने और अधिकतम समदूरता प्राप्त करने के लिए, लेखक टाइम स्पेसिंग ( $s$ ) पेश करते हैं:

संयोजन (Combination): दो मैक्सिमल लेंथ CAs ( $CA_1, CA_2$ ) को अपेक्षाकृत प्राइम (relatively prime) अवधियों के साथ इनिशियलाइज़ किया जाता है।
छोड़ना (Skipping): हर टाइम स्टेप पर स्टेट को संयोजित करने के बजाय, जनरेटर $s$ स्टेप्स के लिए विकसित होता है, और आउटपुट को केवल $s$ -वें स्टेप पर संयोजित (XOR के माध्यम से) किया जाता है।
गणितीय आधार (Mathematical Basis): संयुक्त अनुक्रम को मैट्रिक्स $A = T^s$ से प्राप्त किया जाता है, जहाँ $T$ CA का विशेषता मैट्रिक्स (characteristic matrix) है। यदि $\gcd(s, \rho) = 1$ (जहाँ $\rho$ अवधि है), तो संयुक्त जनरेटर मैक्सिमल अवधि के करीब प्राप्त करता है ( $LCM(\rho_1, \rho_2) \approx 2^{k_1+k_2}$ )।
अनुकूलन (Optimization): लेखक यादृच्छिकता की गुणवत्ता और कम्प्यूटेशनल गति के बीच संतुलन बनाने के लिए $s$ को $2 \le s \le 10$ की सीमा में प्रतिबंधित करते हैं।

C. मूल्यांकन मानदंड (Evaluation Criteria)

सैद्धांतिक (Theoretical): रेजोल्यूशन गैप ( $\Lambda_t$ ) और बाइनरी मैट्रिसेस के रैंक चेक (प्रपोजिशन 2, 3, और 4) का उपयोग करके मैक्सिमल इक्विडिस्ट्रिब्यूशन (ME) का सत्यापन।
अनुभवजन्य (Empirical): मानक सांख्यिकीय टेस्टबेड: Dieharder, SmallCrust, और BigCrush (TestU01 सूट) के विरुद्ध परीक्षण।
दृश्य (Visual): स्व-समान पैटर्न को देखने के लिए स्पेस-टाइम डायग्राम (Space-Time Diagrams) का विश्लेषण।
प्रदर्शन (Performance): मर्सेन ट्विस्टर (Mersenne Twister), टॉसवर्थ (Tausworthe), और WELL जनरेटर के विरुद्ध CPU समय का तुलनात्मक अध्ययन।

3. मुख्य योगदान (Key Contributions)

कमजोरी की पहचान: यह शोध पत्र प्रदर्शित करता है कि मौजूदा लीनियर CA-आधारित PRNGs (मैक्सिमल अवधि वाले होने के बावजूद) मैक्सिमल इक्विडिस्ट्रिब्यूशन टेस्ट में विफल रहते हैं, जिससे वे उच्च-आयामी अनुप्रयोगों के लिए सैद्धांतिक रूप से उप-इष्टतम (suboptimal) बन जाते हैं।
टाइम-स्पेसिंग तंत्र (Time-Spacing Mechanism): बाहरी टेम्परिंग फंक्शन के बिना अराजक स्व-समानता को तोड़ने और अधिकतम समदूरता प्राप्त करने के लिए एक हल्के-वजन वाले तरीके के रूप में टाइम स्पेसिंग ( $s$ ) का परिचय।
व्यापक खोज (Comprehensive Search): लेखकों ने CA साइज ( $32 \le k \le 128$ $32 \leq k \leq 128$ ) और टाइम स्पेसिंग मानों ( $2 \le s \le 10$ $2 \leq s \leq 10$ ) के हजारों संयोजनों का व्यवस्थित मूल्यांकन किया।
- उन्होंने 368 विशिष्ट संयोजनों की पहचान की जो अधिकतम समदूरता प्राप्त करते हैं।
- इनमें से, उन्होंने उन जनरेटरों को अलग किया जो अधिकांश अनुभवजन्य सांख्यिकीय परीक्षणों को भी पास करते हैं।
संसाधन दक्षता (Resource Efficiency): प्रस्तावित जनरेटरों को हार्डवेयर-फ्रेंडली बनाया गया है, जो सरल XOR गेट्स और न्यूनतम नियम विविधताओं का उपयोग करते हैं, जिससे वे FPGA और एम्बेडेड कार्यान्वयन के लिए आदर्श बनते हैं।

4. परिणाम (Results)

सैद्धांतिक गुणवत्ता: प्रस्तावित संयुक्त PRNGs टाइम स्पेसिंग के साथ सफलतापूर्वक मैक्सिमल इक्विडिस्ट्रिब्यूशन (ME) प्राप्त करते हैं, जो पहले सरल लीनियर CA-PRNGs द्वारा अप्राप्य था।
सांख्यिकीय प्रदर्शन:
- कई प्रस्तावित जनरेटर (जैसे कि $(31, 32, s=7/8)$ , $(47, 72, s=10)$ जैसे संयोजन) Dieharder, SmallCrush, और BigCrush के सभी या अधिकांश परीक्षणों में सफल रहे।
- कुछ संयोजन जिन्होंने ME प्राप्त किया लेकिन टाइम स्पेसिंग कारक द्वारा थोड़ी कम अवधि थी, फिर भी सभी परीक्षणों को पास कर गए।
दृश्य सत्यापन: स्पेस-टाइम डायग्राम ने पुष्टि की कि टाइम स्पेसिंग मानक CA विकास (जैसे सिएरपिंस्की त्रिकोण) में देखे जाने वाले स्व-समान पैटर्न को प्रभावी ढंग से नष्ट कर देता है, जिसके परिणामस्वरूप "नॉइजी" और यादृच्छिक दिखने वाले पैटर्न मिलते हैं।
प्रदर्शन तुलना:
- गति: प्रस्तावित PRNGs मर्सेन ट्विस्टर से तेज़ हैं लेकिन स्किपिंग स्टेप्स के कारण गैर-टाइम-स्पेस वाले जनरेटर्स (जैसे मानक टॉसवर्थ या GFSR4) की तुलना में थोड़े धीमे हैं।
- समझौता (Trade-off): सबसे तेज़ लीनियर जनरेटर्स की तुलना में मामूली गति दंड (speed penalty) के बावजूद, वे मर्सेन ट्विस्टर (जो मैक्सिमली इक्विडिस्ट्रिब्यूटेड नहीं है) की तुलना में बेहतर समदूरता और सांख्यिकीय मजबूती प्रदान करते हैं।

5. महत्व (Significance)

यह कार्य हार्डवेयर दक्षता और सैद्धांतिक यादृच्छिकता गुणवत्ता के बीच के अंतर को पाटता है।

व्यावहारिक अनुप्रयोग: यह उन संसाधन-सीमित वातावरणों (FPGA, IoT डिवाइस) के लिए PRNGs डिजाइन करने के लिए एक ब्लूप्रिंट प्रदान करता है जो क्रिप्टोग्राफिक या सिमुलेशन-ग्रेड यादृच्छिकता से समझौता नहीं करते हैं।
सैद्धांतिक प्रगति: यह सिद्ध करता है कि जटिल आउटपुट ट्रांसफॉर्मेशन के बजाय संरचनात्मक संशोधनों (टाइम स्पेसिंग) के माध्यम से मैक्सिमल इक्विडिस्ट्रिब्यूशन प्राप्त किया जा सकता है।
भविष्य का प्रभाव: पहचाने गए पैरामीटर सेट (विशिष्ट $k_1, k_2, s$ संयोजन) उन डेवलपर्स के लिए एक तैयार-उपयोग (ready-to-use) लाइब्रेरी के रूप में कार्य करते हैं जिन्हें उच्च-गुणवत्ता वाले, हल्के-वजन वाले रैंडम नंबर जनरेशन की आवश्यकता है। लेखक भविष्य के कार्य के लिए सुझाव देते हैं कि उच्च गुणवत्ता वाले मेट्रिक्स को बनाए रखते हुए कम्प्यूटेशनल ओवरहेड को और कम करने के लिए टाइम स्पेसिंग तंत्र को अनुकूलित करने पर ध्यान केंद्रित किया जा सकता है।