একটি ছদ্ম-এলোমেলো সংখ্যা হল একটি বিশেষ সংখ্যা যা একটি বিশেষ জেনারেটর দ্বারা তৈরি করা হয়। ডিটারমিনিস্টিক র্যান্ডম বিট জেনারেটর (পিআরএনজি), যা ডিটারমিনিস্টিক র্যান্ডম বিট জেনারেটর (ডিআরবিজি) নামেও পরিচিত, হল একটি অ্যালগরিদম যা সংখ্যাগুলির একটি ক্রম তৈরি করার জন্য যার বৈশিষ্ট্যগুলি র্যান্ডম সংখ্যা ক্রমগুলির বৈশিষ্ট্যগুলিকে আনুমানিক করে। উৎপন্ন PRNG ক্রমটি সত্যিই এলোমেলো নয়, কারণ এটি সম্পূর্ণরূপে PRNG বীজ নামক একটি বীজের মান দ্বারা নির্ধারিত হয়, যার মধ্যে সত্যিকারের এলোমেলো মান থাকতে পারে। যদিও হার্ডওয়্যার র্যান্ডম নম্বর জেনারেটর ব্যবহার করে র্যান্ডম-এর কাছাকাছি সিকোয়েন্স তৈরি করা যেতে পারে, তবে ছদ্ম-র্যান্ডম নম্বর জেনারেটরগুলি সংখ্যা তৈরির গতি এবং তাদের পুনরুত্পাদনযোগ্যতার জন্য অনুশীলনে গুরুত্বপূর্ণ৷
আবেদন
PRNGs হল সিমুলেশন (যেমন মন্টে কার্লোর জন্য), ইলেকট্রনিক গেমস (যেমন পদ্ধতিগত প্রজন্মের জন্য), এবং ক্রিপ্টোগ্রাফির মতো অ্যাপ্লিকেশনের কেন্দ্রবিন্দু। ক্রিপ্টোগ্রাফিক অ্যাপ্লিকেশনের জন্য আউটপুট প্রয়োজনতথ্য পূর্ববর্তী তথ্য থেকে অনুমানযোগ্য ছিল না. আরও জটিল অ্যালগরিদম প্রয়োজন যা সাধারণ PRNG-এর রৈখিকতার উত্তরাধিকারী হয় না।
নিয়ম ও শর্তাবলী
পিআরএনজি পাওয়ার জন্য ভালো পরিসংখ্যানগত বৈশিষ্ট্য একটি কেন্দ্রীয় প্রয়োজন। সাধারনত, RNG এমন সংখ্যা তৈরি করে যেগুলি উদ্দেশ্যপ্রণোদিত ব্যবহারের জন্য উপযুক্ত হওয়ার জন্য র্যান্ডম থেকে যথেষ্ট কাছাকাছি রয়েছে তা নিশ্চিত করার জন্য সতর্ক গাণিতিক বিশ্লেষণের প্রয়োজন৷
জন ভন নিউম্যান PRNG কে সত্যিকারের র্যান্ডম জেনারেটর হিসাবে ভুল ব্যাখ্যা করার বিরুদ্ধে সতর্ক করেছিলেন এবং রসিকতা করেছিলেন যে "যে কেউ এলোমেলো সংখ্যা তৈরির জন্য গাণিতিক পদ্ধতি বিবেচনা করে সে অবশ্যই পাপের অবস্থায় রয়েছে।"
ব্যবহার করুন
PRNG একটি নির্বিচারে প্রাথমিক অবস্থা থেকে চালু করা যেতে পারে। এই অবস্থার সাথে আরম্ভ করার সময় এটি সর্বদা একই ক্রম তৈরি করবে। পিআরএনজি সময়কাল নিম্নরূপ সংজ্ঞায়িত করা হয়েছে: অ-পুনরাবৃত্ত ক্রম উপসর্গের দৈর্ঘ্যের সমস্ত প্রাথমিক অবস্থায় সর্বাধিক। সময়কাল রাজ্যের সংখ্যা দ্বারা সীমিত, সাধারণত বিটে পরিমাপ করা হয়। যেহেতু প্রতিটি "স্টেট" বিট যোগ করার সাথে সময়কালের দৈর্ঘ্য সম্ভাব্য দ্বিগুণ হয়ে যায়, তাই অনেকগুলি ব্যবহারিক অ্যাপ্লিকেশনের জন্য যথেষ্ট বড় পিরিয়ড সহ PRNG তৈরি করা সহজ৷
যদি PRNG-এর অভ্যন্তরীণ অবস্থায় n বিট থাকে, তাহলে এর সময়কাল 2n ফলাফলের বেশি হতে পারে না, এটি অনেক কম। কিছু PRNG-এর জন্য, পুরো সময়কাল বাইপাস না করেই সময়কাল গণনা করা যেতে পারে। লিনিয়ার ফিডব্যাক শিফট রেজিস্টার (LFSRs) সাধারণত হয়পিরিয়ড 2n − 1 এর সমান হওয়ার জন্য বেছে নেওয়া হয়েছে।
লিনিয়ার কনগ্রুয়েনশিয়াল জেনারেটরের সময়কাল থাকে যা ফ্যাক্টরিং ব্যবহার করে গণনা করা যায়। যদিও পিপিপি পিরিয়ড শেষ হওয়ার পরে তার ফলাফলের পুনরাবৃত্তি করবে, বারবার ফলাফলের অর্থ এই নয় যে পিরিয়ডের শেষ হয়ে গেছে, যেহেতু এর অভ্যন্তরীণ অবস্থা আউটপুটের চেয়ে বেশি হতে পারে; এটি বিশেষ করে একক বিট আউটপুট সহ PRNG গুলির জন্য স্পষ্ট৷
সম্ভাব্য ত্রুটি
ত্রুটিপূর্ণ PRNGs দ্বারা পাওয়া ত্রুটিগুলি সূক্ষ্ম (এবং অজানা) থেকে সুস্পষ্ট পর্যন্ত। একটি উদাহরণ হল RANDU র্যান্ডম নম্বর অ্যালগরিদম, যা কয়েক দশক ধরে মেইনফ্রেমে ব্যবহৃত হচ্ছে। এটি একটি গুরুতর ত্রুটি ছিল, কিন্তু এটির অপ্রতুলতা দীর্ঘ সময়ের জন্য অলক্ষিত ছিল৷
অনেক ক্ষেত্রে, গবেষণা অধ্যয়ন যেগুলি এলোমেলো নির্বাচন, মন্টে কার্লো সিমুলেশন, বা RNG ভিত্তিক অন্যান্য পদ্ধতি ব্যবহার করেছে তা নিম্নমানের GNPG এর ফলাফলের তুলনায় অনেক কম নির্ভরযোগ্য। এমনকি আজও, কখনও কখনও সতর্কতা প্রয়োজন, যেমনটি আন্তর্জাতিক এনসাইক্লোপিডিয়া অফ স্ট্যাটিস্টিক্যাল সায়েন্স (2010) এর সতর্কতা দ্বারা প্রমাণিত।
সফল কেস স্টাডি
একটি উদাহরণ হিসাবে, বহুল ব্যবহৃত জাভা প্রোগ্রামিং ভাষা বিবেচনা করুন। 2017 সালের হিসাবে, জাভা এখনও তার PRNG এর জন্য লিনিয়ার কনগ্রুয়েনশিয়াল জেনারেটরের (LCG) উপর নির্ভর করে৷
ইতিহাস
প্রথম PRNG গুরুতর সমস্যা এড়াতে এবং এখনও বেশ দ্রুত চালানো,মার্সেন টুইস্টার ছিল (নীচে আলোচনা করা হয়েছে), যা 1998 সালে প্রকাশিত হয়েছিল। তারপর থেকে, অন্যান্য উচ্চ মানের PRNG তৈরি করা হয়েছে।
কিন্তু ছদ্ম-এলোমেলো সংখ্যার ইতিহাস সেখানে শেষ হয় না। 20 শতকের দ্বিতীয়ার্ধে, PRNG-এর জন্য ব্যবহৃত অ্যালগরিদমের মানক শ্রেণির মধ্যে লিনিয়ার কনগ্রুয়েনশিয়াল জেনারেটর অন্তর্ভুক্ত ছিল। LCG এর মান অপর্যাপ্ত বলে পরিচিত ছিল, কিন্তু এর চেয়ে ভালো পদ্ধতি পাওয়া যায়নি। প্রেস এট আল (2007) ফলাফলটিকে নিম্নরূপ বর্ণনা করেছে: "যদি সমস্ত বৈজ্ঞানিক কাগজপত্র যার ফলাফলগুলি [LCGs এবং সম্পর্কিত] কারণে সন্দেহের মধ্যে রয়েছে সেগুলি লাইব্রেরির তাক থেকে অদৃশ্য হয়ে গেলে, প্রতিটি শেলফে আপনার মুষ্টির আকারের একটি ফাঁক থাকবে।"
ছদ্ম-এলোমেলো জেনারেটর তৈরির প্রধান কৃতিত্ব ছিল একটি দ্বি-উপাদান ক্ষেত্রে রৈখিক পুনরাবৃত্তির উপর ভিত্তি করে পদ্ধতির প্রবর্তন; এই ধরনের অসিলেটর লিনিয়ার ফিডব্যাক শিফ্ট রেজিস্টারের সাথে মিলিত হয়। তারা ছদ্ম-এলোমেলো নম্বর সেন্সর আবিষ্কারের ভিত্তি হিসাবে কাজ করেছিল৷
বিশেষ করে, মারসেন টুইস্টারের 1997 সালের আবিষ্কারটি আগের জেনারেটরের অনেক সমস্যা এড়িয়ে গিয়েছিল। মারসেন টুইস্টারের 219937−1 পুনরাবৃত্তির সময়কাল রয়েছে (≈4.3 × 106001)। এটি 623 মাত্রায় (32-বিট মানের জন্য) সমানভাবে বিতরণ করা প্রমাণিত হয়েছে এবং এটি প্রবর্তনের সময় অন্যান্য পরিসংখ্যানগত শব্দ জেনারেটরের তুলনায় দ্রুততর ছিল যা ছদ্ম-এলোমেলো সংখ্যার ক্রম তৈরি করে।
2003 সালে, জর্জ মার্সাগ্লিয়া রৈখিক পুনরাবৃত্তির উপর ভিত্তি করে জরশিফ্ট জেনারেটরের একটি পরিবার চালু করেছিলেন। এই জেনারেটর অত্যন্তদ্রুত এবং - একটি নন-লিনিয়ার অপারেশনের সাথে মিলিত - তারা কঠোর পরিসংখ্যানগত পরীক্ষায় উত্তীর্ণ হয়৷
2006 সালে, ওয়েল জেনারেটর পরিবার তৈরি করা হয়েছিল। ওয়েল জেনারেটরগুলি এক অর্থে টুইস্টার মারসেনের গুণমানকে উন্নত করে, যার একটি অত্যধিক বড় স্টেট স্পেস রয়েছে এবং সেগুলি থেকে খুব ধীরগতিতে পুনরুদ্ধার হয়, প্রচুর শূন্য সহ ছদ্ম-এলোমেলো সংখ্যা তৈরি করে৷
ক্রিপ্টোগ্রাফি
ক্রিপ্টোগ্রাফিক অ্যাপ্লিকেশনের জন্য উপযুক্ত
PRNG কে ক্রিপ্টোগ্রাফিকভাবে সুরক্ষিত PRNG (CSPRNG) বলা হয়। একটি CSPRNG-এর প্রয়োজনীয়তা হল যে আক্রমণকারী যে বীজটি জানে না তার জেনারেটরের আউটপুট সিকোয়েন্সকে র্যান্ডম সিকোয়েন্স থেকে আলাদা করার ক্ষেত্রে শুধুমাত্র একটি প্রান্তিক সুবিধা রয়েছে। অন্য কথায়, যখন একটি PRNG শুধুমাত্র নির্দিষ্ট পরিসংখ্যান পরীক্ষায় উত্তীর্ণ হওয়ার প্রয়োজন হয়, তখন একটি CSPRNG-কে অবশ্যই সমস্ত পরিসংখ্যানগত পরীক্ষায় উত্তীর্ণ হতে হবে যা বীজের আকারে বহুপদী সময়ের মধ্যে সীমাবদ্ধ।
যদিও এই সম্পত্তির প্রমাণ গণনাগত জটিলতা তত্ত্বের বর্তমান স্তরের বাইরে, তবে CSPRNG-কে এমন একটি সমস্যা কমিয়ে দিয়ে শক্তিশালী প্রমাণ সরবরাহ করা যেতে পারে যা পূর্ণসংখ্যার ফ্যাক্টরাইজেশনের মতো কঠিন বলে মনে করা হয়। সাধারণভাবে, একটি অ্যালগরিদমকে CSPRNG হিসাবে প্রত্যয়িত করার আগে বছরের পর বছর পর্যালোচনার প্রয়োজন হতে পারে।
এটা দেখানো হয়েছে যে সম্ভবত NSA NIST-প্রত্যয়িত Dual_EC_DRBG সিউডো-র্যান্ডম নম্বর জেনারেটরের মধ্যে একটি অসমমিতিক পিছনের দরজা ঢুকিয়েছে।
ছদ্ম-এলোমেলো অ্যালগরিদমসংখ্যা
অধিকাংশ PRNG অ্যালগরিদমগুলি এমন ক্রম তৈরি করে যা বিভিন্ন পরীক্ষার যেকোনো একটি দ্বারা সমানভাবে বিতরণ করা হয়। এটি একটি খোলা প্রশ্ন। এটি ক্রিপ্টোগ্রাফির তত্ত্ব এবং অনুশীলনের একটি কেন্দ্রীয় বিষয়: একটি সত্যিকারের র্যান্ডম সিকোয়েন্স থেকে একটি উচ্চ-মানের PRNG-এর আউটপুটকে আলাদা করার কোনো উপায় আছে কি? এই সেটিংয়ে, সমাধানকারী জানেন যে হয় একটি পরিচিত PRNG অ্যালগরিদম ব্যবহার করা হয়েছিল (কিন্তু যে অবস্থায় এটি শুরু করা হয়েছিল তা নয়), অথবা একটি সত্যিকারের র্যান্ডম অ্যালগরিদম ব্যবহার করা হয়েছিল৷ তাকে অবশ্যই তাদের মধ্যে পার্থক্য করতে হবে।
পিআরএনজি ব্যবহার করে এমন বেশিরভাগ ক্রিপ্টোগ্রাফিক অ্যালগরিদম এবং প্রোটোকলের নিরাপত্তা এই অনুমানের উপর ভিত্তি করে যে উপযুক্ত পিআরএনজি ব্যবহার এবং সত্যিকারের র্যান্ডম সিকোয়েন্স ব্যবহারের মধ্যে পার্থক্য করা অসম্ভব। এই নির্ভরতার সবচেয়ে সহজ উদাহরণ হল স্ট্রিম সাইফার, যা প্রায়শই PRNG আউটপুট সহ প্লেইনটেক্সট বার্তা বাদ দিয়ে বা পাঠানোর মাধ্যমে কাজ করে, সাইফারটেক্সট তৈরি করে। ক্রিপ্টোগ্রাফিকভাবে পর্যাপ্ত PRNGs ডিজাইন করা অত্যন্ত কঠিন কারণ তাদের অবশ্যই অতিরিক্ত মানদণ্ড পূরণ করতে হবে। পিআরএনজির ক্রিপ্টোগ্রাফিক উপযুক্ততার ক্ষেত্রে এর সময়কালের আকার একটি গুরুত্বপূর্ণ কারণ, তবে একমাত্র নয়।
1946 সালে জন ভন নিউম্যান দ্বারা প্রস্তাবিত একটি প্রাথমিক কম্পিউটার পিআরএনজি গড় স্কোয়ার পদ্ধতি হিসাবে পরিচিত। অ্যালগরিদমটি নিম্নরূপ: যেকোনো সংখ্যা নিন, এটিকে বর্গ করুন, একটি "র্যান্ডম সংখ্যা" হিসাবে ফলাফলের সংখ্যার মাঝের সংখ্যাগুলি সরিয়ে দিন, তারপর পরবর্তী পুনরাবৃত্তির জন্য এই সংখ্যাটিকে প্রারম্ভিক সংখ্যা হিসাবে ব্যবহার করুন৷ উদাহরণস্বরূপ, 1111 নম্বরের বর্গ করলে পাওয়া যায়1234321, যা 01234321 হিসাবে লেখা যেতে পারে, একটি 8-সংখ্যার সংখ্যা হল একটি 4-অঙ্কের সংখ্যার বর্গ। এটি একটি "এলোমেলো" সংখ্যা হিসাবে 2343 দেয়। এই পদ্ধতির পুনরাবৃত্তির ফলাফল হল 4896, এবং তাই। ভন নিউম্যান 10 সংখ্যার সংখ্যা ব্যবহার করেছিলেন, কিন্তু প্রক্রিয়াটি একই ছিল৷
"মিডল স্কোয়ার" এর অসুবিধা
"মান বর্গ" পদ্ধতির সমস্যা হল যে সমস্ত ক্রমগুলি শেষ পর্যন্ত পুনরাবৃত্তি হয়, কিছু খুব দ্রুত, উদাহরণস্বরূপ: 0000। ভন নিউম্যান এই সম্পর্কে জানতেন, কিন্তু তিনি তার উদ্দেশ্যগুলির জন্য যথেষ্ট একটি পদ্ধতি খুঁজে পেয়েছিলেন এবং চিন্তিত ছিলেন যে গণিত "সংশোধন" শুধুমাত্র ভুলগুলিকে সরিয়ে দেওয়ার পরিবর্তে লুকিয়ে রাখবে৷
ভন নিউম্যান হার্ডওয়্যার র্যান্ডম এবং ছদ্ম-র্যান্ডম নম্বর জেনারেটরগুলিকে অনুপযুক্ত খুঁজে পেয়েছেন: যদি তারা জেনারেট আউটপুট রেকর্ড না করে, তবে সেগুলি পরে ত্রুটির জন্য পরীক্ষা করা যাবে না। যদি তারা তাদের ফলাফলগুলি লিখে রাখে, তাহলে তারা কম্পিউটারের সীমিত উপলব্ধ মেমরি এবং এইভাবে কম্পিউটারের সংখ্যা পড়তে এবং লেখার ক্ষমতা শেষ করে দেবে। সংখ্যাগুলো যদি কার্ডে লেখা হতো, তাহলে সেগুলো লিখতে ও পড়তে অনেক বেশি সময় লাগতো। ENIAC কম্পিউটারে তিনি "মিডল স্কোয়ার" পদ্ধতি ব্যবহার করেছিলেন এবং ছদ্ম-এলোমেলো সংখ্যাগুলি পাঞ্চ করা কার্ডগুলি থেকে সংখ্যা পড়ার চেয়ে কয়েকশ গুণ দ্রুত প্রাপ্ত করার প্রক্রিয়া চালিয়েছিলেন৷
মান বর্গক্ষেত্র তখন থেকে আরও জটিল জেনারেটর দ্বারা স্থানান্তরিত হয়েছে।
উদ্ভাবনী পদ্ধতি
একটি সাম্প্রতিক উদ্ভাবন হল ওয়েইল সিকোয়েন্সের সাথে গড় বর্গক্ষেত্রকে একত্রিত করা। এই পদ্ধতির মধ্যে উচ্চ মানের পণ্য নিশ্চিত করেদীর্ঘ সময়ের. এটি সেরা ছদ্ম-এলোমেলো নম্বর সূত্র পেতে সাহায্য করে৷