Inversive congruential generator
व्युत्क्रमात्मक सर्वांगसम जनित्र एक प्रकार का अरैखिक सर्वांगसम सूडोरैंडम संख्या जनित्र है, जो एक अनुक्रम में अगली संख्या उत्पन्न करने के लिए मॉड्यूलर गुणक व्युत्क्रम (यदि यह मौजूद है) का उपयोग करता है। एक व्युत्क्रम सर्वांगसम जनित्र के लिए मानक सूत्र, मॉड्यूलो कुछ अभाज्य q हैः इस तरह के जनित्र को प्रतीकात्मक रूप से दर्शाया जाता है और इसे q, a, c और बीज बीज मापदंडों के साथ एक ICG कहा जाता है। अवधि अनुक्रम में सीमित रूप से कई चरण होने चाहिए, और चूंकि अगला तत्व केवल अपने प्रत्यक्ष पूर्ववर्ती, आदि पर भी निर्भर करता है। मापांक q के लिए अधिकतम संभव अवधि स्वयं q है, अर्थात। अनुक्रम में दोहराने से पहले 0 से q−1 तक का प्रत्येक मान शामिल होता है। अनुक्रम के लिए अधिकतम संभव अवधि रखने के लिए एक पर्याप्त शर्त ए और सी का चयन करना है ताकि बहुपद (बहुपद वलय) आदिम हो। यह एक आवश्यक शर्त नहीं है; q, a और c के विकल्प हैं जिनके लिए आदिम नहीं है, लेकिन अनुक्रम में फिर भी q की अवधि है। कोई भी बहुपद, आदिम या नहीं, जो अधिकतम-अवधि अनुक्रम की ओर ले जाता है, उसे व्युत्क्रमात्मक अधिकतम-अवधि (आई. एम. पी.) बहुपद कहा जाता है। चाउ इस तरह के बहुपदों को प्राप्त करने के लिए मापदंडों a और c को चुनने के लिए एक एल्गोरिथ्म का वर्णन करता है। आइचेनॉयर-हर्मन, लेन, ग्रोथ और नाइडेराइटर ने दिखाया है कि व्युत्क्रमात्मक सर्वांगसम जनरेटर में अच्छी एकरूपता गुण होते हैं, विशेष रूप से जाली संरचना और क्रमिक सहसंबंधों के संबंध में। उदाहरण आई. सी. जी. (5,2,3,1) अनुक्रम 1,0,3,2,4,1,0,3,4,2,1,0 देता है। इस उदाहरण में, इरेड्यूसिबल है, क्योंकि 0,1,2,3 या 4 में से कोई भी रूट नहीं है। यह भी सत्यापित किया जा सकता है कि x एक आदिम तत्व है और इसलिए f आदिम है। यौगिक व्युत्क्रम जनित्र (सी. आई. जी.) का निर्माण नीचे वर्णित विधि के अनुसार दो या दो से अधिक व्युत्क्रम सर्वांगसम जनित्रों के संयोजन पर निर्भर करता है। मान लीजिए कि प्रत्येक अलग-अलग अभाज्य पूर्णांक हैं। प्रत्येक सूचकांक जे के लिए, 1 ≤ जे ≤ आर, अवधि की लंबाई के साथ आवधिक तत्वों का एक अनुक्रम माना जाता है। दूसरे शब्दों में,। प्रत्येक सूचकांक जे के लिए, 1 ≤ जे ≤ आर, हम विचार करते हैं, जहां निम्नलिखित अनुक्रम की अवधि की लंबाई है। यौगिक सूडोरैंडम संख्याओं के अनुक्रम को योग के रूप में परिभाषित किया गया है। यौगिक दृष्टिकोण व्युत्क्रमात्मक सर्वांगसम जनरेटर के संयोजन की अनुमति देता है, बशर्ते कि उनके पास समानांतर उत्पादन प्रणालियों में पूर्ण अवधि हो। सी. आई. जी. के लाभ सी. आई. जी. को कई कारणों से व्यावहारिक उद्देश्यों के लिए स्वीकार किया जाता है। सबसे पहले, इस तरह से उत्पादित द्विआधारी अनुक्रम अवांछनीय सांख्यिकीय विचलन से मुक्त हैं। विभिन्न प्रकार के सांख्यिकीय परीक्षणों के साथ व्यापक रूप से परीक्षण किए गए व्युत्क्रम अनुक्रम मापदंड की भिन्नता के तहत स्थिर रहते हैं। दूसरा, चौ एल्गोरिदम के आधार पर पैरामीटर चयन का एक स्थिर और सरल तरीका मौजूद है जो अधिकतम अवधि की लंबाई की गारंटी देता है। तीसरा, यौगिक दृष्टिकोण में एकल व्युत्क्रम जनरेटर के समान गुण होते हैं, लेकिन यह एकल व्युत्क्रम सर्वांगसम जनरेटर द्वारा प्राप्त अवधि की लंबाई भी प्रदान करता है। ऐसा लगता है कि उन्हें मल्टीप्रोसेसर समानांतर हार्डवेयर प्लेटफार्मों के साथ अनुप्रयोग के लिए डिज़ाइन किया गया है। एक एल्गोरिथ्म मौजूद है जो अनुमानित अवधि की लंबाई, अनुमानित रैखिक जटिलता स्तर, उत्पादित बिट धाराओं के उत्कृष्ट सांख्यिकीय गुणों के साथ यौगिक जनरेटर को डिजाइन करने की अनुमति देता है। इस जटिल संरचना को डिजाइन करने की प्रक्रिया पी तत्वों के सीमित क्षेत्र को परिभाषित करने के साथ शुरू होती है और यौगिक जनरेटर के घटक होने के कारण प्रत्येक व्युत्क्रम सर्वांगसम जनरेटर के लिए मापदंडों ए और सी को चुनने के साथ समाप्त होती है। इसका मतलब है कि प्रत्येक जनरेटर एक निश्चित आई. एम. पी. बहुपद से जुड़ा होता है। ऐसी स्थिति प्रत्येक व्युत्क्रम सर्वांगसम जनरेटर की अधिकतम अवधि के लिए और अंत में यौगिक जनरेटर की अधिकतम अवधि के लिए पर्याप्त है। आई. एम. पी. बहुपदों का निर्माण अधिकतम अवधि की लंबाई के साथ व्युत्क्रम सर्वांगसम जनरेटर के लिए मापदंड खोजने का सबसे कुशल तरीका है। विसंगति और इसकी सीमाएँ उत्पन्न अनुक्रमों के समान वितरण और सांख्यिकीय स्वतंत्रता गुण, जो एक यादृच्छिक अनुकरण में उनकी उपयोगिता के लिए बहुत महत्वपूर्ण हैं, का विश्लेषण क्रमशः और साथ क्रमिक छद्म यादृच्छिक संख्याओं के एस-टुपल्स की विसंगति के आधार पर किया जा सकता है। विसंगति एक समान जनरेटर से जनरेटर की दूरी की गणना करती है। एक कम विसंगति का मतलब है कि उत्पन्न अनुक्रम का उपयोग क्रिप्टोग्राफिक उद्देश्यों के लिए किया जा सकता है, और व्युत्क्रम सर्वांगसम जनरेटर का पहला उद्देश्य छद्म यादृच्छिक संख्या प्रदान करना है। परिभाषा मनमाने बिंदुओं के लिए विसंगति को इस प्रकार परिभाषित किया जाता है, जहां सर्वोच्चता को सभी उप-अंतरालों पर विस्तारित किया जाता है, जिसमें गिरने वाले बिंदुओं की संख्या का गुना होता है और के-आयामी आयतन को दर्शाता है। अब तक, हमारे पास 0 से पूर्णांकों के अनुक्रम थे, ताकि अनुक्रम हो सकें, कोई भी पूर्णांकों के अनुक्रमों को उनकी अवधि से विभाजित कर सकता है। इस परिभाषा से, हम कह सकते हैं कि यदि अनुक्रम पूरी तरह से यादृच्छिक है तो यह अंतराल पर अच्छी तरह से वितरित है और सभी बिंदु इसलिए हैं लेकिन इसके बजाय यदि अनुक्रम एक बिंदु के करीब केंद्रित है तो उप अंतराल बहुत छोटा है और इसलिए हमारे पास बेहतर और सबसे खराब स्थिति हैः संकेतन कुछ और संकेतन आवश्यक हैं। पूर्णांकों के लिए और के लिए के साथ गैर-शून्य जाली बिंदुओं का सेट होने दें। के लिए परिभाषित करें। वास्तविक के लिए संक्षिप्त नाम का उपयोग किया जाता है, और मानक आंतरिक उत्पाद के लिए खड़ा है। उच्चतर बाध्य मान लीजिए और पूर्णांक बनें। के लिए छोड़ दें। फिर अंकों की विसंगति ≤ + निचली सीमा को संतुष्ट करती है मनमाने बिंदुओं की विसंगति किसी भी गैर-शून्य जाली बिंदु के लिए संतुष्ट करती है, जहां के गैर-शून्य निर्देशांक की संख्या को दर्शाता है। इन दो प्रमेयों से पता चलता है कि सी. आई. जी. सही नहीं है क्योंकि विसंगति एक सकारात्मक मूल्य की तुलना में सख्ती से अधिक है, लेकिन यह भी कि सी. आई. जी. सबसे खराब जनरेटर नहीं है क्योंकि विसंगति 1 से कम मूल्य से कम है। ऐसे प्रमेय भी मौजूद हैं जो यौगिक व्युत्क्रम उत्पादकों के लिए विसंगति के औसत मूल्य को बाध्य करते हैं और वे भी जो ऐसे मूल्य लेते हैं कि विसंगति मापदंडों के आधार पर कुछ मूल्य से बंधी होती है। अधिक जानकारी के लिए मूल लेख देखें। स्यूडोरैंडम संख्या जनरेटर यादृच्छिक संख्या जनरेटर की सूची भी देखें रैखिक सर्वांगसम जनरेटर सामान्यीकृत व्युत्क्रम सर्वांगसम स्यूडोरैंडम संख्या नाओर-रिंगोल्ड स्यूडोरैंडम कार्य संदर्भ बाहरी लिंक साल्ज़बर्ग विश्वविद्यालय में व्युत्क्रम जनरेटर। स्यूडोरैंडम नंबर जनरेटर