Index calculus algorithm
کمپیوٹیشنل نمبر تھیوری میں، انڈیکس کیلکولس الگورتھم مجرد لوگرتھم کی کمپیوٹنگ کے لیے ایک ممکنہ الگورتھم ہے۔ مجرد لوگرتھم کے لیے وقف جہاں ایک پرائم ہے، انڈیکس کیلکولس الگورتھم کے ایک خاندان کی طرف لے جاتا ہے جو محدود فیلڈز اور ایلیپٹک منحنی خطوط کے کچھ خاندانوں کے لیے موزوں ہے۔ الگورتھم چھوٹے پرائمز کے مجرد لوگرتھم کے درمیان تعلقات کو جمع کرتا ہے، ان کا حساب لکیری الجبرا کے طریقہ کار کے ذریعے کرتا ہے اور آخر میں چھوٹے پرائمز کے مجرد لوگرتھم کے حوالے سے مطلوبہ مجرد لوگرتھم کا اظہار کرتا ہے۔ تفصیل تقریبا بولتے ہوئے، مجرد لاگ کا مسئلہ ہمیں ایک x تلاش کرنے کے لیے کہتا ہے کہ جہاں g، h، اور ماڈیولس n دیے گئے ہیں۔ الگورتھم (ذیل میں تفصیل سے بیان کیا گیا ہے) اس گروپ پر لاگو ہوتا ہے جہاں q پرائم ہے۔ اسے ان پٹ کے طور پر فیکٹر بیس کی ضرورت ہوتی ہے۔ اس فیکٹر بیس کو عام طور پر نمبر −1 کے طور پر منتخب کیا جاتا ہے اور پہلا r پرائم 2 سے شروع ہوتا ہے۔ کارکردگی کے نقطہ نظر سے، ہم چاہتے ہیں کہ یہ عنصر کی بنیاد چھوٹی ہو، لیکن ایک بڑے گروپ کے لیے مجرد لاگ کو حل کرنے کے لیے ہمیں عنصر کی بنیاد (نسبتا) بڑی ہونی چاہیے۔ الگورتھم کے عملی نفاذ میں، ان متضاد مقاصد سے کسی نہ کسی طرح سمجھوتہ کیا جاتا ہے۔ الگورتھم تین مراحل میں انجام دیا جاتا ہے۔ پہلے دو مراحل صرف جنریٹر g اور پرائم ماڈیولس q پر منحصر ہوتے ہیں، اور r چھوٹے پرائمز کے فیکٹر بیس کے مجرد لوگرتھم تلاش کرتے ہیں۔ تیسرا مرحلہ عنصر بیس کے مجرد لاگ کے لحاظ سے مطلوبہ نمبر h کا مجرد لاگ تلاش کرتا ہے۔ پہلا مرحلہ جنریٹر g کے فیکٹر بیس اور پاور کے درمیان r لکیری طور پر آزاد تعلقات کے ایک سیٹ کی تلاش پر مشتمل ہوتا ہے۔ ہر رشتہ r نامعلوم میں لکیری مساوات کے نظام میں ایک مساوات کا حصہ بنتا ہے، یعنی فیکٹر بیس میں r پرائمز کے مجرد لوگرتھم۔ یہ مرحلہ شرمناک طور پر متوازی ہے اور بہت سے کمپیوٹرز کے درمیان تقسیم کرنا آسان ہے۔ دوسرا مرحلہ عنصر کی بنیاد کے مجرد لاگ کا حساب لگانے کے لیے لکیری مساوات کے نظام کو حل کرتا ہے۔ سیکڑوں ہزاروں یا لاکھوں مساوات کا نظام ایک اہم حساب ہے جس میں بڑی مقدار میں میموری کی ضرورت ہوتی ہے، اور یہ شرمناک طور پر متوازی نہیں ہے، اس لیے عام طور پر ایک سپر کمپیوٹر استعمال کیا جاتا ہے۔ چھوٹے مجرد لاگ کمپیوٹیشن کے لیے دوسروں کے مقابلے میں یہ ایک معمولی قدم سمجھا جاتا تھا۔ تاہم، بڑے مجرد لوگرتھم ریکارڈ صرف کام کو لکیری الجبرا سے دور اور چھلنی پر منتقل کرنے سے ممکن ہوئے (یعنی، متغیرات کی تعداد کو کم کرتے ہوئے مساوات کی تعداد میں اضافہ)۔ تیسرا مرحلہ جنریٹر g کے پاور s کی تلاش کرتا ہے، جسے جب دلیل h سے ضرب دی جاتی ہے، تو اسے فیکٹر بیس gsh = (−1) f0 2f1 3f2··prfr کے لحاظ سے فیکٹر کیا جا سکتا ہے۔ آخر میں، کسی ایسے آپریشن میں جسے واقعی چوتھا مرحلہ نہیں کہا جا سکتا، دوسرے اور تیسرے مراحل کے نتائج کو سادہ الجبرائی ہیرا پھیری کے ذریعے دوبارہ ترتیب دیا جا سکتا ہے تاکہ مطلوبہ مجرد لوگرتھم x = f0log (−1) + f1log2 + f2log3 + ·· + frlogpr − s کو طے کیا جا سکے۔ پہلے اور تیسرے مراحل دونوں شرمناک طور پر متوازی ہیں، اور حقیقت میں تیسرا مرحلہ پہلے دو مراحل کے نتائج پر منحصر نہیں ہے، لہذا یہ ان کے متوازی کیا جا سکتا ہے۔ عنصر بیس سائز r کا انتخاب اہم ہے، اور تفصیلات یہاں بیان کرنے کے لیے بہت پیچیدہ ہیں۔ فیکٹر بیس جتنا بڑا ہوگا، مرحلہ 1 میں تعلقات تلاش کرنا اتنا ہی آسان ہوگا، اور مرحلہ 3 کو مکمل کرنا اتنا ہی آسان ہوگا، لیکن مرحلہ 2 پر آگے بڑھنے سے پہلے آپ کو جتنے زیادہ تعلقات کی ضرورت ہوگی، اور مرحلہ 2 اتنا ہی مشکل ہوگا۔ مراحل 1 اور 2 کے لیے درکار مختلف قسم کے حساب کے لیے موزوں کمپیوٹرز کی نسبتا دستیابی بھی اہم ہے۔ دوسرے گروپوں میں ایپلی کیشنز الپٹک منحنی خطوط پر پوائنٹس کے گروپ میں پرائم عناصر کے تصور کی کمی انڈیکس کیلکولس طریقہ کار کو چلانے کے لیے ایک موثر فیکٹر بیس تلاش کرنا ناممکن بنا دیتی ہے جیسا کہ ان گروپوں میں یہاں پیش کیا گیا ہے۔ لہذا یہ الگورتھم الپٹک وکر گروپوں میں مجرد لوگرتھم کو مؤثر طریقے سے حل کرنے کے قابل نہیں ہے۔ تاہم: خاص قسم کے منحنی خطوط کے لیے (جسے سپر سنگولر ایلیپٹک منحنی خطوط کہا جاتا ہے) عام طریقوں کے مقابلے میں مسئلے کو تیزی سے حل کرنے کے لیے خصوصی الگورتھم موجود ہیں۔ اگرچہ ان خاص منحنی خطوط کے استعمال سے آسانی سے بچا جا سکتا ہے، لیکن 2009 میں یہ ثابت ہوا ہے کہ بعض شعبوں کے لیے ان شعبوں پر عام الپٹک منحنی خطوط پر پوائنٹس کے گروپ میں مجرد لوگرتھم کا مسئلہ عام طریقوں کے مقابلے میں تیزی سے حل کیا جا سکتا ہے۔ الگورتھم درحقیقت انڈیکس کیلکولس طریقہ کار کی موافقت ہیں۔ الگورتھم ان پٹ: ڈسکریٹ لوگرتھم جنریٹر، ماڈیولس اور دلیل۔ عنصر کی بنیاد، لمبائی کی۔ آؤٹ پٹ: اس طرح۔ تعلقات کے لیے خالی فہرست ہموار اعداد کے لیے بہتر کردہ انٹیجر فیکٹرائزیشن الگورتھم کا استعمال کرتے ہوئے، فیکٹر بیس کا استعمال کرتے ہوئے فیکٹر (یوکلڈین ریسیڈیو) کرنے کی کوشش کریں، یعنی۔ تلاش کریں کہ ہر بار ایک فیکٹرائزیشن مل جائے: اسٹور کریں اور کمپیوٹڈ کو ویکٹر کے طور پر (یہ ایک رشتہ کہا جاتا ہے) اگر یہ تعلق دوسرے تعلقات سے لکیری طور پر آزاد ہے: اسے تعلقات کی فہرست میں شامل کریں اگر کم از کم تعلقات ہیں، تو ایک میٹرکس بنائیں جس کی قطاریں تعلقات ہیں۔ میٹرکس کی کم شدہ ایکلون شکل حاصل کریں۔ آخری کالم میں پہلا عنصر مجرد لاگ آف ہے اور دوسرا عنصر مجرد لاگ آف ہے اور اسی طرح عنصر کی بنیاد پر فیکٹر کرنے کی کوشش کریں جب ایک فیکٹرائزیشن مل جاتی ہے: آؤٹ پٹ پیچیدگی عنصر کی بنیاد کا زیادہ سے زیادہ انتخاب فرض کرتے ہوئے، انڈیکس کیلکولس الگورتھم کا متوقع رننگ ٹائم (ایل نوٹیشن کا استعمال کرتے ہوئے) بیان کیا جا سکتا ہے۔ الگورتھم کا بنیادی خیال ویسٹرن اینڈ ملر (1968) کی وجہ سے ہے، جو بالآخر کریچک (1922) کے خیالات پر منحصر ہے۔ پہلا عملی نفاذ 1976 میں ڈفی-ہیلمین کرپٹو سسٹم کے تعارف کے بعد ہوا جو مجرد لوگرتھم پر انحصار کرتا ہے۔ مرکلے کے اسٹینفورڈ یونیورسٹی کے مقالے (1979) کا سہرا پوہلگ (1977) اور ہیلمین اینڈ رینیری (1983) کو جاتا ہے، جنہوں نے عمل درآمد میں بھی بہتری لائی۔ ایڈلمین نے الگورتھم کو بہتر بنایا اور اسے موجودہ شکل میں پیش کیا۔ انڈیکس کیلکولس فیملی انڈیکس کیلکولس نے الگورتھم کے ایک بڑے خاندان کو متاثر کیا۔ کچھ پرائم کے ساتھ محدود فیلڈز میں، جدید ترین الگورتھم نمبر فیلڈ چھلنی ہے جو ڈسکریٹ لوگرتھمز کے لیے ہے، جب اس کے مقابلے میں بڑا ہوتا ہے، فنکشن فیلڈ چھلنی، اور جوکس، جب اس کے مقابلے میں چھوٹا ہوتا ہے اور نمبر فیلڈ چھلنی ہائی ڈگری میں، جب درمیانی رخا ہوتا ہے۔ الپٹک منحنی خطوط کے کچھ خاندانوں میں مجرد لوگارتھم کو وقت کے ساتھ حل کیا جا سکتا ہے، لیکن عمومی معاملہ متغیر رہتا ہے۔ بیرونی روابط محدود شعبوں میں ڈسکریٹ لوگرتھم اور ان کی کرپٹوگرافک اہمیت، اینڈریو اوڈلیزکو ڈسکریٹ لوگرتھم پروبلم کے ذریعہ، کرس اسٹڈولم کے ذریعہ، بشمول 21 جون 2002 کا مقالہ "دی ڈسکریٹ لاگ پروبلم"۔ نوٹس گروپ تھیوری