(सुरक्षित) यादृच्छिक स्ट्रिंग?

Question

लुआ में, आमतौर पर math.random & math.randomseed का उपयोग करके यादृच्छिक मान, और/या स्ट्रिंग उत्पन्न होता है, जहां math.randomseed के लिए उपयोग किया जाता है।

हालांकि इस विधि में एक बड़ी कमजोरी है; लौटाया गया नंबर हमेशा वर्तमान समय के रूप में यादृच्छिक है, और प्रत्येक यादृच्छिक संख्या के लिए अंतराल एक सेकंड है, जो बहुत कम समय में कई यादृच्छिक मानों की आवश्यकता होने पर बहुत लंबा है।

यह समस्या लुआ उपयोगकर्ता विकी द्वारा भी इंगित की गई है: http://lua-users.org/wiki/MathLibraryTutorial, और इसी RandomStringS रसीद: http://lua-users.org/wiki/RandomStrings।

तो मैं बैठ गए हैं और एक अलग एल्गोरिथ्म लिखा था (अगर यह भी है कि कहा जा सकता है), कि (अ-) द्वारा यादृच्छिक संख्या उत्पन्न करता तालिकाओं की स्मृति पतों का उपयोग कर:

math.randomseed(os.time()) 
function realrandom(maxlen) 
    local tbl = {} 
    local num = tonumber(string.sub(tostring(tbl), 8)) 
    if maxlen ~= nil then 
     num = num % maxlen 
    end 
    return num 
end 

function string.random(length,pattern) 
    local length = length or 11 
    local pattern = pattern or '%a%d' 
    local rand = "" 
    local allchars = "" 
    for loop=0, 255 do 
     allchars = allchars .. string.char(loop) 
    end 
    local str=string.gsub(allchars, '[^'..pattern..']','') 
    while string.len(rand) ~= length do 
     local randidx = realrandom(string.len(str)) 
     local randbyte = string.byte(str, randidx) 
     rand = rand .. string.char(randbyte) 
    end 

    return rand 
end 

सबसे पहले , सब कुछ पूरी तरह से यादृच्छिक लगता है, और मुझे यकीन है कि वे ... वर्तमान कार्यक्रम के लिए कम से कम हैं।

तो मेरा सवाल यह है कि realrandom वास्तव में ये संख्या कितनी यादृच्छिक है?

या कोई और भी बेहतर तरीका, एक सेकंड (जो एक तरह से संकेत मिलता है कि os.time, नहीं किया जाना चाहिए, जैसा कि ऊपर explaind) की तुलना में छोटे अंतराल में यादृच्छिक संख्या उत्पन्न करने के लिए, और बाहरी पुस्तकालयों पर निर्भर रहे बिना है, यदि संभव हो, तो पूरी तरह से क्रॉसप्लेटफार्म तरीके से?

संपादित करें:
आरएनजी बीज के तरीके के बारे में एक बड़ी गलतफहमी प्रतीत होती है; उत्पादन कोड में, math.randomseed() पर कॉल केवल एक बार होता है, यह यहां एक बुरी तरह से चुना गया उदाहरण था।

क्या मैं मतलब यादृच्छिक मान केवल यादृच्छिक एक बार प्रति सेकंड, आसानी से इस पेस्ट द्वारा प्रदर्शन किया जाता है: http://codepad.org/4cDsTpcD

---

इस सवाल भले ही मेरे संपादन downvoted हो जाएगा के रूप में, मैं भी रद्द कर दिया मेरी पहले स्वीकार किए गए उत्तर - एक बेहतर के लिए आशा में, भले ही बेहतर विचार हो। मैं समझता हूं कि यादृच्छिक मूल्यों/संख्याओं के बारे में मुद्दों पर कई बार चर्चा की गई है, लेकिन मुझे ऐसा कोई सवाल नहीं मिला है जो लुआ से प्रासंगिक हो सकता है - कृपया इसे ध्यान में रखें!

Answer 1

अपने प्रश्न के पहले भाग पर कुछ विचार:

तो मेरे सवाल, कैसे यादृच्छिक इन नंबरों realrandom वास्तव द्वारा दिया जाता है?

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

भी एक बड़ा मुद्दा है। हालांकि किसी प्रक्रिया में बनाई गई एनएचटी तालिका का पता आपके प्लेटफ़ॉर्म पर यादृच्छिक प्रतीत हो सकता है, टीटी यादृच्छिक नहीं हो सकता है। या यह केवल कुछ बिट्स में भिन्न हो सकता है। उदाहरण के लिए, मेरी Win7 बॉक्स पर केवल कुछ ही बिट्स भिन्नता है, और बहुत बेतरतीब ढंग से नहीं:

 
C:...>for /L %i in (1,1,20) do @ lua -e "print{}" 
table: 0042E5D8 
table: 0061E5D8 
table: 0024E5D8 
table: 0049E5D8 
table: 0042E5D8 
table: 0042E5D8 
table: 0042E5D8 
table: 0064E5D8 
table: 0042E5D8 
table: 002FE5D8 
table: 0042E5D8 
table: 0049E5D8 
table: 0042E5D8 
table: 0042E5D8 
table: 0042E5D8 
table: 0024E5D8 
table: 0042E5D8 
table: 0042E5D8 
table: 0061E5D8 
table: 0042E5D8 

अन्य प्लेटफार्मों जाहिर है, अलग अलग होंगे। मैं उम्मीद करता हूं कि वहां प्लेटफॉर्म हों जहां पहली आवंटित तालिका का पता पूरी तरह से निर्धारिती है, और इसलिए कार्यक्रम के हर भाग पर समान है।

संक्षेप में, आपकी प्रक्रिया छवि में मनमानी वस्तु का पता यादृच्छिकता का एक बहुत अच्छा स्रोत नहीं है।

संपादित करें: पूर्णता के लिए, मैं रात में दिमाग में आने वाले कुछ अन्य विचारों को जोड़ना चाहता हूं।

स्टॉक tostring() फ़ंक्शन बेस लाइब्रेरी द्वारा प्रदान किया जाता है और फ़ंक्शन luaB_tostring() द्वारा कार्यान्वित किया जाता है।

switch (lua_type(L, 1)) { 
    ... 
    default: 
    lua_pushfstring(L, "%s: %p", luaL_typename(L, 1), lua_topointer(L, 1)); 
    break; 

तुम सच में इस कार्यप्रणाली को कॉल कर रहे हैं, तो स्ट्रिंग के अंत एक पते, मानक सी sprintf() प्रारूप %p, दृढ़ता से विशिष्ट तालिका से संबंधित का प्रतिनिधित्व करती हो जाएगा: प्रासंगिक बिट इस टुकड़ा है। एक अवलोकन यह है कि मैंने %p के लिए कई अलग-अलग कार्यान्वयन देखा है। विंडोज एमएसवीसीआर 80. डीएलएल (विंडोज़ के लिए लुआ की वर्तमान रिलीज द्वारा उपयोग की जाने वाली सी लाइब्रेरी का संस्करण) इसे %08X के बराबर बनाता है। मेरा उबंटू कर्मिक कोआला बॉक्स इसे %#x के बराबर बनाने के लिए प्रतीत होता है जो विशेष रूप से प्रमुख शून्यों को छोड़ देता है। यदि आप स्ट्रिंग के उस हिस्से को पार्स करने जा रहे हैं, तो आपको इसे ऐसे तरीके से करना चाहिए जो %p के अर्थ के भिन्नता के मुकाबले अधिक लचीला है।

नोट, यह भी कि लाइब्रेरी कोड में ऐसा कुछ भी करने से आपको कुछ आश्चर्यों का सामना करना पड़ सकता है।

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

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

तीसरा, आपको स्टॉक लुआ दुभाषिया में लोड नहीं किया जा सकता है, और बड़ा आवेदन (लाइटरूम, वाह, वायरशर्क, ...) बेस लाइब्रेरी फ़ंक्शंस को अपने कार्यान्वयन के साथ प्रतिस्थापित करने का विकल्प चुन सकता है। यह tostring() के लिए बहुत कम संभावित समस्या है, लेकिन ध्यान दें कि बेस लाइब्रेरी का print() वैकल्पिक कार्यान्वयन में प्रतिस्थापन या हटाने के लिए एक लगातार लक्ष्य है और मॉड्यूल (Lua Lanes, एक के लिए) हैं जो टूटते हैं यदि print आधार लाइब्रेरी में कार्यान्वयन नहीं है ।

Answer 2

कुछ खास बातें दिमाग में आते हैं:

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

यदि आपको विकिपीडिया पर PRNG आलेख पर अधिक जानकारी की आवश्यकता है और आवश्यकतानुसार संदर्भ/लिंक का उपयोग करें।

Answer 3

1. आप बीज हर बार जब आप यादृच्छिक फोन नहीं बुलाना चाहिए, आप केवल एक बार इसे कहते हैं कार्यक्रम प्रारंभ पर (जब तक आप कहीं से बीज मिलता है, उदाहरण के लिए, पिछले कुछ "यादृच्छिक दोहराने के लिए चाहिए " व्यवहार)।

2. मानक लुआ यादृच्छिक जनरेटर सांख्यिकीय अर्थ में खराब गुणवत्ता का है (वास्तव में, मानक सी यादृच्छिक जनरेटर), यदि आप इसकी परवाह करते हैं तो इसका उपयोग न करें। उदाहरण के लिए, lrandom मॉड्यूल (LuaRocks में उपलब्ध) का उपयोग करें।

3. यदि आपको अधिक सुरक्षित यादृच्छिक की आवश्यकता है, तो लिनक्स पर /dev/random से पढ़ें। (मुझे लगता है कि विंडोज़ के पास एक ही पंक्ति के साथ कुछ होना चाहिए - लेकिन आपको इसका उपयोग करने के लिए सी में कुछ कोड करने की आवश्यकता हो सकती है।)

4. तालिका सूचक मूल्यों पर निर्भर करना एक बुरा विचार है। जावा में वैकल्पिक लुआ कार्यान्वयन के बारे में सोचें, उदाहरण के लिए - कोई बात नहीं है कि वे क्या लौटेंगे। (साथ ही, सूचक मान अनुमानित हो सकते हैं, और हो सकता है कि कुछ परिस्थितियों में कार्यक्रम हर बार लागू हो।)

5. यदि आप बीज के लिए बेहतर परिशुद्धता चाहते हैं (और आप इसे केवल तभी चाहते हैं 'प्रोग्राम प्रति सेकंड एक बार से अधिक बार लॉन्च करने), आपको बेहतर रिज़ॉल्यूशन वाला टाइमर का उपयोग करना चाहिए। उदाहरण के लिए, LuaSocket से socket.gettime()। इसे कुछ मान से गुणा करें, क्योंकि math.randomseed केवल पूर्णांक भाग के साथ काम कर रहा है, और socket.gettime() रिटर्न टाइम (फ़्लोटिंग पॉइंट) सेकंड में समय देता है।

   require 'socket' 
   
   math.randomseed(socket.gettime() * 1e6) 
   
   for i = 1, 1e3 do 
       print(math.random()) 
   end 
   

Answer 4

इस विधि हालांकि एक प्रमुख कमजोरी है; लौटाया गया नंबर हमेशा समय के रूप में यादृच्छिक है, और प्रत्येक यादृच्छिक संख्या के लिए अंतराल एक सेकंड है, जो कि लंबा है, यदि किसी को बहुत ही कम समय में कई यादृच्छिक मानों की आवश्यकता होती है।

इसमें केवल कमजोरियां हैं यदि आप इसे गलत तरीके से कार्यान्वित करते हैं।

math.randomseed को कम से कम कहा जाना चाहिए - आम तौर पर केवल आपके कार्यक्रम की शुरुआत में, और आमतौर पर os.time का उपयोग करके बीज। बीज सेट होने के बाद, आप कई बार math.random का उपयोग कर सकते हैं, और यह यादृच्छिक मान उत्पन्न करेगा।

> math.randomseed(1) 
> return math.random(), math.random(), math.random() 
0.84018771715471 0.39438292681909 0.78309922375861 
> math.randomseed(2) 
> return math.random(), math.random(), math.random() 
0.70097636929759 0.80967634907443 0.088795455214007 
> math.randomseed(1) 
> return math.random(), math.random(), math.random() 
0.84018771715471 0.39438292681909 0.78309922375861 

जब मैं 1 से 2 करने के लिए बीज बदलने के लिए, मैं अलग यादृच्छिक परिणाम प्राप्त:

इस नमूने पर क्या होता है देखें। लेकिन जब मैं 1 पर वापस जाता हूं, तो "यादृच्छिक अनुक्रम" रीसेट हो जाता है। मैं पहले के समान मूल्य प्राप्त करता हूं।

os.time() एक बढ़ती संख्या देता है। बीज के रूप में इसका उपयोग उचित है; तो आप हर बार math.random का आह्वान कर सकते हैं और जब भी आप इसे आमंत्रित करते हैं तो अलग-अलग यादृच्छिक संख्याएं होती हैं।

गैर-यादृच्छिकता के बारे में थोड़ा चिंतित होने वाला एकमात्र परिदृश्य तब होता है जब आपका प्रोग्राम प्रति सेकंड एक से अधिक बार निष्पादित किया जाता है। उस स्थिति में, जैसा कि अन्य लोग कह रहे हैं, सबसे सरल समाधान उच्च परिभाषा वाले घड़ी का उपयोग कर रहा है।

दूसरे शब्दों में:

• आह्वान एक उचित बीज के साथ math.randomseed (os.time() ठीक है के मामलों की 99%) अपने कार्यक्रम
• आह्वान math.random हर बार की शुरुआत में आप एक यादृच्छिक संख्या की जरूरत है ।

सम्मान!