क्या छिपे हुए राज्य के बिना "अच्छा" पीआरएनजी उत्पन्न मूल्य है?

Question

मुझे कुछ अच्छे छद्म यादृच्छिक संख्या जनरेटर की आवश्यकता है जिसे किसी भी राज्य छिपाने के बिना अपने पिछले आउटपुट से शुद्ध फ़ंक्शन की तरह गणना की जा सकती है। के तहत "अच्छा" मेरा मतलब है:

1. मैं इस तरह से जनरेटर parametrize करने के लिए कि किसी भी पैरामीटर के साथ 2^n पुनरावृत्तियों के लिए इसे चलाने (या उनमें से कुछ बड़े सबसेट के साथ) के बीच सभी या लगभग सभी मूल्यों को शामिल करना चाहिए सक्षम होना चाहिए 0 और 2^n - 1, जहां n आउटपुट मूल्य में बिट्स की संख्या है।

2. n + p बिट्स की संयुक्त जनरेटर उत्पादन सभी को कवर करना होगा या लगभग 0 और 2^(n + p) - 1 बीच के सभी मानों अगर मैं इसे अपने मानकों, जहां p मानकों में बिट्स की संख्या है के हर संभव संयोजन के लिए 2^n पुनरावृत्तियों के लिए चलाते हैं।

उदाहरण के लिए, LCG एक शुद्ध समारोह की तरह गणना की जा सकता है और यह पहली शर्त को पूरा कर सकते हैं, लेकिन यह एक दूसरे को पूरा नहीं कर सकते हैं। कहें, हमारे पास 32-बिट एलसीजी, m = 2^32 है और यह स्थिर है, हमारे p = 64 (दो 32-बिट पैरामीटर a और c), n + p = 96, इसलिए हमें दूसरी स्थिति को पूरा करने के लिए आउटपुट से तीन इंच से डेटा देखना होगा। दुर्भाग्यवश, आउटपुट में अजीब और यहां तक ​​कि इनट्स के कड़ाई से वैकल्पिक अनुक्रम के कारण स्थिति को पूरा नहीं किया जा सकता है। इसे दूर करने के लिए, छुपा राज्य पेश किया जाना चाहिए, लेकिन इससे कार्य शुद्ध नहीं होता है और पहली स्थिति (लंबी छुपी अवधि) तोड़ता है।

संपादित करें: सच पूछिये तो, मैं p बिट्स द्वारा और n बिट्स से भरा राज्य के साथ, हर तरह अद्वितीय "randomish" में p + n बिट्स के सभी संभव द्विआधारी तार पैदा करने के लिए, बस लगातार (p + n) incrementing नहीं parametrized कार्यों का परिवार चाहते हैं - थोड़ा int उस अनोखे तरीके का चयन करने के लिए पैरामीट्रिजेशन आवश्यक है।

क्या मैं बहुत ज्यादा चाहता हूं?

Answer 1

LFSR
आपको केवल प्राचीन बहुपदों की सूची चाहिए।
इस तरह परिमित क्षेत्र उत्पन्न करने की अवधि, आकार 2^एन -1 के क्षेत्र उत्पन्न करता है। लेकिन आप k^n-1 की किसी भी श्वेत अवधि उत्पन्न करने के लिए इस प्रक्रिया को सामान्यीकृत कर सकते हैं।

मैं इस से लागू नहीं देखा है, लेकिन आप सभी को लागू करना द्वारा छोटी संख्या रों संख्या स्थानांतरण> n जहां gcd (रों, 2^n-1) == 1. gcd सबसे बड़ा आम भाजक के लिए खड़ा है

Answer 2

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