Inversive congruential generator
الٹا ہم آہنگ جنریٹر ایک قسم کے غیر لکیری ہم آہنگ سڈورینڈم نمبر جنریٹر ہوتے ہیں، جو ترتیب میں اگلا نمبر پیدا کرنے کے لیے ماڈیولر ضرب الٹا (اگر موجود ہو) کا استعمال کرتے ہیں۔ ایک الٹا ہم آہنگ جنریٹر کے لیے معیاری فارمولا، ماڈیولو کچھ پرائم q ہے: اس طرح کے جنریٹر کو علامتی طور پر ظاہر کیا جاتا ہے اور کہا جاتا ہے کہ یہ ایک آئی سی جی ہے جس کے پیرامیٹرز q، a، c اور بیج کے بیج ہوتے ہیں۔ مدت ترتیب میں محدود طور پر بہت سے مراحل ہونے چاہئیں، اور چونکہ اگلا عنصر صرف اپنے براہ راست پیشرو پر منحصر ہے، وغیرہ۔ ماڈیولس q کے لیے زیادہ سے زیادہ ممکنہ مدت خود q ہے، یعنی۔ ترتیب میں دہرانے سے پہلے 0 سے q−1 تک کی ہر قدر شامل ہوتی ہے۔ ترتیب کے لیے زیادہ سے زیادہ ممکنہ مدت حاصل کرنے کے لیے ایک کافی شرط یہ ہے کہ a اور c کا انتخاب اس طرح کیا جائے کہ کثیر الجہتی (کثیر الجہتی رنگ اوور) ابتدائی ہو۔ یہ ایک ضروری شرط نہیں ہے ؛ 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 ≤ جے ≤ آر، ہم غور کرتے ہیں، کہ درج ذیل ترتیب کی مدت کی لمبائی کہاں ہے۔ مرکب سڈورینڈم نمبروں کی ترتیب کو مجموعہ کے طور پر بیان کیا گیا ہے۔ مرکب نقطہ نظر الٹا ہم آہنگ جنریٹرز کو یکجا کرنے کی اجازت دیتا ہے، بشرطیکہ ان کے پاس متوازی نسل کے نظام میں مکمل مدت ہو۔ سی آئی جی کے فوائد سی آئی جی کو کئی وجوہات کی بنا پر عملی مقاصد کے لیے قبول کیا جاتا ہے۔ سب سے پہلے، اس طرح سے تیار کردہ بائنری ترتیبات ناپسندیدہ شماریاتی انحراف سے پاک ہیں۔ مختلف قسم کے شماریاتی ٹیسٹوں کے ساتھ بڑے پیمانے پر جانچ کی جانے والی الٹا ترتیب پیرامیٹر کی تغیر کے تحت مستحکم رہتی ہے۔ دوسرا، چو الگورتھم پر مبنی پیرامیٹر کے انتخاب کا ایک مستحکم اور آسان طریقہ موجود ہے جو زیادہ سے زیادہ مدت کی لمبائی کی ضمانت دیتا ہے۔ تیسرا، مرکب نقطہ نظر میں وہی خصوصیات ہیں جو واحد الٹا جنریٹر کی ہوتی ہیں، لیکن یہ مدت کی لمبائی بھی فراہم کرتا ہے جو ایک واحد الٹا ہم آہنگ جنریٹر کے ذریعہ حاصل کردہ مدت سے نمایاں طور پر زیادہ ہوتی ہے۔ ایسا لگتا ہے کہ وہ ملٹی پروسیسر متوازی ہارڈ ویئر پلیٹ فارم کے ساتھ ایپلی کیشن کے لیے ڈیزائن کیے گئے ہیں۔ ایک الگورتھم موجود ہے جو کمپاؤنڈ جنریٹرز کو پیش گوئی کی مدت کی لمبائی، پیش گوئی کے قابل لکیری پیچیدگی کی سطح کے ساتھ، تیار شدہ بٹ اسٹریمز کی بہترین شماریاتی خصوصیات کے ساتھ ڈیزائن کرنے کی اجازت دیتا ہے۔ اس پیچیدہ ڈھانچے کو ڈیزائن کرنے کا طریقہ کار p عناصر کے محدود میدان کی وضاحت کے ساتھ شروع ہوتا ہے اور مرکب جنریٹر کا جزو ہونے کے ناطے ہر الٹا ہم آہنگ جنریٹر کے لیے a اور c پیرامیٹرز کے انتخاب کے ساتھ ختم ہوتا ہے۔ اس کا مطلب یہ ہے کہ ہر جنریٹر ایک مقررہ آئی ایم پی کثیر الجہتی سے وابستہ ہے۔ اس طرح کی حالت ہر الٹا ہم آہنگ جنریٹر کی زیادہ سے زیادہ مدت کے لیے اور آخر میں مرکب جنریٹر کی زیادہ سے زیادہ مدت کے لیے کافی ہے۔ آئی ایم پی کثیر الجہتی کی تعمیر زیادہ سے زیادہ مدت کی لمبائی کے ساتھ الٹا ہم آہنگ جنریٹر کے لیے پیرامیٹرز تلاش کرنے کا سب سے موثر طریقہ ہے۔ تفرقہ اور اس کی حدود پیدا شدہ ترتیبات کی مساوی تقسیم اور شماریاتی آزادی کی خصوصیات، جو سٹوچسٹک تخروپن میں ان کے استعمال کے لیے بہت اہم ہیں، کا تجزیہ بالترتیب اور اس کے ساتھ مسلسل سڈورینڈم نمبروں کے ایس-ٹپل کی تضاد کی بنیاد پر کیا جا سکتا ہے۔ تضاد ایک یکساں جنریٹر سے جنریٹر کے فاصلے کا حساب لگاتا ہے۔ کم تضاد کا مطلب یہ ہے کہ پیدا شدہ ترتیب کو کرپٹوگرافک مقاصد کے لیے استعمال کیا جا سکتا ہے، اور الٹا ہم آہنگ جنریٹر کا پہلا مقصد سڈورینڈم نمبر فراہم کرنا ہے۔ تعریف صوابدیدی نکات کے لیے تضاد کی تعریف اس طرح کی جاتی ہے، جہاں کے تمام ذیلی وقفوں پر بالادستی کو بڑھایا جاتا ہے، اس میں گرنے والے پوائنٹس کی تعداد کا گنا ہوتا ہے اور کے-جہتی حجم کی نشاندہی کرتا ہے۔ اب تک، ہمارے پاس 0 سے لے کر انٹیجرز کے سلسلے تھے، تاکہ انٹیجرز کے سلسلے کو اس کی مدت سے تقسیم کیا جا سکے۔ اس تعریف سے، ہم یہ کہہ سکتے ہیں کہ اگر ترتیب بالکل بے ترتیب ہے تو یہ وقفے پر اچھی طرح سے تقسیم ہوتا ہے اور تمام پوائنٹس اسی طرح ہوتے ہیں لیکن اس کے بجائے اگر ترتیب ایک نقطہ کے قریب مرکوز ہے تو ذیلی وقفہ بہت چھوٹا ہوتا ہے اور اس طرح پھر ہمارے پاس بہتر اور بدترین صورت حال ہے: نوٹیشن کچھ مزید نوٹیشن ضروری ہے۔ انٹیجرز کے لیے اور اس کے ساتھ نان زیرو لیٹس پوائنٹس کا سیٹ ہونے دیں۔ وضاحت کریں اور کے لیے۔ حقیقی کے لیے مخفف استعمال کیا جاتا ہے، اور اس کا مطلب معیاری اندرونی پروڈکٹ ہے۔ اعلی پابند ہونے دیں اور انٹیجر بنیں۔ کے ساتھ رہنے دیں۔ پھر پوائنٹس کی تضاد ≤ + زیریں باؤنڈ کو مطمئن کرتی ہے صوابدیدی پوائنٹس کی تضاد کسی بھی غیر صفر جالی پوائنٹ کے لیے مطمئن کرتی ہے، جہاں کے غیر صفر نقاط کی تعداد کو ظاہر کرتا ہے۔ ان دونوں نظریات سے پتہ چلتا ہے کہ سی آئی جی کامل نہیں ہے کیونکہ تضاد مثبت قدر سے سختی سے زیادہ ہے لیکن یہ بھی کہ سی آئی جی بدترین جنریٹر نہیں ہے کیونکہ تضاد 1 سے کم قدر سے کم ہے۔ ایسے نظریات بھی موجود ہیں جو مرکب الٹا جنریٹرز کے لیے تضاد کی اوسط قیمت کو پابند کرتے ہیں اور وہ بھی جو اقدار کو اس طرح لیتے ہیں کہ تضاد پیرامیٹرز کے لحاظ سے کچھ قدر سے پابند ہوتا ہے۔ مزید تفصیلات کے لیے اصل کاغذ دیکھیں۔ سیوڈورانڈم نمبر جنریٹر بھی دیکھیں بے ترتیب نمبر جنریٹرز کی فہرست لکیری کونگروینشیل جنریٹر جنرلائزڈ انورسیو کونگروینشیل سیوڈورانڈم نمبر ناور-رنگولڈ سیوڈورانڈم فنکشن حوالہ جات بیرونی روابط یونیورسٹی آف سالزبرگ میں انورسیو جنریٹرز۔ سیوڈورانڈم نمبر جنریٹر