Discrete logarithm records
مجرد لوگرتھم ریکارڈ مجرد لوگرتھم کے مسئلے کو حل کرنے میں آج تک حاصل کیے گئے بہترین نتائج ہیں، جو کہ ایک محدود چکور گروپ G کے عناصر g اور h کی مساوات کے حل x تلاش کرنے کا مسئلہ ہے۔ اس مسئلے کی مشکل کئی کرپٹوگرافک نظاموں کی حفاظت کی بنیاد ہے، بشمول ڈفی ہیلمین کلیدی معاہدہ، ایل گیمل خفیہ کاری، ایل گیمل دستخطی اسکیم، ڈیجیٹل سگنیچر الگورتھم، اور ان کے ایلیپٹک کرپٹوگرافی اینالاگس۔ ان الگورتھم میں استعمال ہونے والے G کے لیے عام انتخاب میں انٹیجرز ماڈیولو p کا ضرب گروپ، ایک محدود فیلڈ کا ضرب گروپ، اور ایک محدود فیلڈ پر ایلیپٹک وکر پر پوائنٹس کا گروپ شامل ہیں۔ انٹیجرز ماڈیولو پرائم نمبروں کا موجودہ ریکارڈ، جو دسمبر 2019 میں ترتیب دیا گیا ہے، ایک مجرد لوگارتھم کمپیوٹیشن ماڈیولو ہے جو 240 ہندسوں کے ساتھ ایک پرائم ہے۔ خصوصیت 2 کے لیے، محدود فیلڈز کا موجودہ ریکارڈ، جو جولائی 2019 میں مقرر کیا گیا ہے، ایک مجرد لوگرتھم ہے۔ جب پرائم ایکسپوینٹس تک محدود ہو تو، موجودہ ریکارڈ، جو اکتوبر 2014 میں قائم کیا گیا تھا، ختم ہو گیا ہے۔ خصوصیت 3 کے لیے، موجودہ ریکارڈ، جو جولائی 2016 میں قائم کیا گیا تھا، ختم ہو گیا ہے۔ "اعتدال پسند" خصوصیت کے شعبوں کے لیے، موجودہ ریکارڈ، جو جنوری 2013 میں قائم کیا گیا تھا، ختم ہو گیا ہے۔ انٹیجرز ماڈیولو پی 2 دسمبر 2019 کو، فیبریس بوڈوٹ، پیئرک گاؤڈری، اورور گیلیویک، نادیہ ہیننگر، ایمانوئل تھام، اور پال زیمرمین نے 240 ہندسوں (795 بٹ) پرائم آر ایس اے-240 + 49204 (آر ایس اے-240 کے اوپر پہلا محفوظ پرائم) ایک مجرد لوگارتھم ماڈیولو کے حساب کا اعلان کیا۔ یہ حساب نمبر فیلڈ سیو الگورتھم اور اوپن سورس سی اے ڈی او-این ایف ایس سافٹ ویئر کا استعمال کرتے ہوئے آر ایس اے-240 کی فیکٹرائزیشن کے ساتھ بیک وقت انجام دیا گیا تھا۔ کمپیوٹیشن کے مجرد لوگرتھم حصے میں تقریبا 3100 بنیادی سال لگے، جس میں انٹیل زیون گولڈ 6130 سی پی یو کو بطور حوالہ (2.1 گیگا ہرٹز) استعمال کیا گیا۔ محققین کا اندازہ ہے کہ الگورتھم اور سافٹ ویئر میں بہتری نے ہارڈ ویئر میں بہتری کا حساب لگانے کے بعد اس حساب کو پچھلے ریکارڈوں سے توقع سے تین گنا زیادہ تیز کردیا۔ انٹیجرز ماڈیولو پی کے پچھلے ریکارڈوں میں شامل ہیں: 16 جون 2016 کو، تھورسٹن کلینجنگ، کلاز ڈائم، آرجن کے لینسٹرا، کرسٹین پریپلاٹا، اور کولن اسٹہلکے نے نمبر فیلڈ چھلنی کا استعمال کرتے ہوئے ایک مجرد لوگرتھم ماڈیولو کے 232 ہندسوں (768 بٹ) کے محفوظ پرائم کی گنتی کا اعلان کیا۔ یہ حساب فروری 2015 میں شروع کیا گیا تھا اور 2.2 گیگا ہرٹز پر انٹیل زیون ای 5-2660 تک پہنچنے میں تقریبا 6600 بنیادی سال لگے۔ 18 جون 2005 کو، انٹون جوکس اور رینالڈ لرسیر نے 1.15 گیگا ہرٹز 16-پروسیسر ایچ پی الفا سرور جی ایس 1280 کمپیوٹر اور نمبر فیلڈ سیو الگورتھم کا استعمال کرتے ہوئے تین ہفتوں میں 130 ہندسوں (431 بٹ) کے مضبوط پرائم کے ایک مجرد لوگرتھم ماڈیولو کی گنتی کا اعلان کیا۔ 5 فروری 2007 کو تھورسٹن کلینجنگ کی طرف سے 160 ہندسوں (530 بٹ) کے محفوظ پرائم کے مجرد لوگرتھم ماڈیولو کی گنتی کے اعلان کے ذریعے اس کی جگہ لے لی گئی، جس میں دوبارہ نمبر فیلڈ چھلنی کا استعمال کیا گیا۔ زیادہ تر حساب مختلف پی سی پر اور متوازی کمپیوٹنگ کلسٹر پر بیکار وقت کا استعمال کرتے ہوئے کیا گیا تھا۔ 11 جون 2014 کو، سیرل بوویر، پیئرک گاؤڈری، لورنٹ امبرٹ، ہمزا جیلجیلی اور ایمانوئل تھام نے نمبر فیلڈ چھلنی الگورتھم کا استعمال کرتے ہوئے 180 ہندسوں (596 بٹ) کے محفوظ پرائم کے ایک مجرد لوگرتھم ماڈیولو کی گنتی کا اعلان کیا۔ اس کے علاوہ قابل ذکر بات یہ ہے کہ جولائی 2016 میں، جوشوا فریڈ، پیئرک گاؤڈری، نادیہ ہینگر، ایمانوئل تھوم نے 1024 بٹ پرائم پر اپنی مجرد لوگرتھم کمپیوٹیشن شائع کی۔ انہوں نے نسبتا چھوٹے ذیلی گروپ (160 بٹس) پر خصوصی الگورتھم کا استعمال کرتے ہوئے خصوصی نمبر فیلڈ چھلنی کے لیے حساس ایک پرائم تیار کیا۔ اگرچہ یہ ایک چھوٹا ذیلی گروپ ہے، لیکن یہ 1024 بٹ ڈیجیٹل سگنیچر الگورتھم (ڈی ایس اے) کے ساتھ استعمال ہونے والا معیاری ذیلی گروپ سائز تھا۔ محدود فیلڈز خصوصیت 2 کے محدود میدان میں موجودہ ریکارڈ () کا اعلان 10 جولائی 2019 کو رابرٹ گرینجر، تھورسٹن کلینجنگ، آرجن لینسٹرا، بینجمن ویسولووسکی، اور جینس زمبرگل نے کیا تھا۔ یہ ٹیم انٹیل زیون فن تعمیر پر مبنی کلسٹرز پر 25,481,219 بنیادی اوقات کا استعمال کرتے ہوئے GF (230750) میں مجرد لوگرتھم کا حساب لگانے میں کامیاب رہی۔ یہ کمپیوٹیشن نیم کثیر الجہتی الگورتھم کے خاتمے کے مرحلے کا استعمال کرتے ہوئے پہلی بڑے پیمانے کی مثال تھی۔ خصوصیت 2 کے محدود میدان میں پچھلے ریکارڈوں کا اعلان 31 جنوری 2014 کو رابرٹ گرینجر، تھورسٹن کلینجنگ، اور جینس زمبریگل نے کیا تھا۔ یہ ٹیم تقریبا 400,000 بنیادی گھنٹوں کا استعمال کرتے ہوئے جی ایف (29234) میں مجرد لوگرتھم کا حساب لگانے میں کامیاب رہی۔ اس حساب کی نئی خصوصیات میں ڈگری ٹو عناصر کے لوگرتھم کو حاصل کرنے کے لیے ایک ترمیم شدہ طریقہ اور ایک منظم طریقے سے بہتر نزول کی حکمت عملی شامل ہے۔ اینٹوین جوکس 21 مئی 2013 کو۔ ان کی ٹیم 550 سی پی یو گھنٹے سے کم کا استعمال کرتے ہوئے 26168 = (2257) 24 عناصر کے ساتھ میدان میں مجرد لوگرتھم کا حساب لگانے میں کامیاب رہی۔ یہ حساب اسی انڈیکس کیلکولس الگورتھم کا استعمال کرتے ہوئے کیا گیا تھا جیسا کہ 24080 عناصر کے ساتھ فیلڈ میں حالیہ حساب کتاب میں کیا گیا تھا۔ 11 اپریل 2013 کو رابرٹ گرینجر، فاروق گلوگلو، گیری میک گائر، اور جینس زمبریگل۔ نئے حساب کا تعلق 26120 عناصر کے ساتھ فیلڈ سے تھا اور اس میں 749.5 بنیادی گھنٹے لگے۔ 22 مارچ، 2013 کو انٹون جوکس۔ اس نے چھوٹے خصوصیت والے شعبوں کے لیے وہی الگورتھم استعمال کیا جو کہ 21778 عناصر کے ساتھ میدان میں پچھلی گنتی تھی۔ نئے حساب کا تعلق 24080 عناصر کے ساتھ فیلڈ سے تھا، جسے 216 عناصر کے ساتھ فیلڈ کی ڈگری 255 توسیع کے طور پر پیش کیا گیا۔ حساب کتاب میں 1400 بنیادی گھنٹے سے بھی کم وقت لگا۔ 19 فروری 2013 کو رابرٹ گرینجر، فاروق گلوگلو، گیری میک گائر، اور جینس زمبریگل۔ انہوں نے 21971 عناصر کے میدان میں ایک مجرد لوگرتھم کا حساب لگانے کے لیے بائنری فیلڈز کے لیے درمیانے درجے کے بیس فیلڈ فنکشن فیلڈ چھلنی کی ایک نئی قسم کا استعمال کیا۔ درمیانے درجے کے بیس فیلڈ کو استعمال کرنے کے لیے، انہوں نے فیلڈ کی نمائندگی 227 عناصر کے فیلڈ کی ڈگری 73 توسیع کے طور پر کی۔ کمپیوٹیشن میں انٹیل (ویسٹمیر) زیون ای 5650 ہیکس کور پروسیسرز کا استعمال کرتے ہوئے ایس جی آئی الٹیکس آئی سی ای 8200 ای ایکس کلسٹر پر 3132 بنیادی گھنٹے لگے۔ 11 فروری 2013 کو انٹون جوکس۔ اس نے چھوٹے خصوصیت والے شعبوں کے لیے ایک نیا الگورتھم استعمال کیا۔ حساب کا تعلق 21778 عناصر کے میدان سے تھا، جسے 214 عناصر کے ساتھ میدان کی ڈگری 127 توسیع کے طور پر پیش کیا گیا۔ حساب کتاب میں 220 بنیادی گھنٹے سے بھی کم وقت لگا۔ پرائم ڈگری کی خصوصیت 2 کے محدود میدان میں موجودہ ریکارڈ () کا اعلان تھورسٹن کلینجنگ نے 17 اکتوبر 2014 کو کیا تھا۔ حساب 21279 عناصر کے میدان میں کیا گیا تھا اور بنیادی طور پر لکیری الجبرا کے حساب اور نزول کے مرحلے میں دو اہم مستثنیات کے ساتھ اس راستے کی پیروی کی گئی تھی۔ کل رننگ ٹائم چار بنیادی سالوں سے بھی کم تھا۔ پرائم ڈگری کی خصوصیت 2 کے محدود میدان میں پچھلے ریکارڈ کا اعلان کیریمل گروپ نے 6 اپریل 2013 کو کیا تھا۔ انہوں نے 2809 عناصر کے میدان میں ایک مجرد لوگرتھم کا حساب لگانے کے لیے فنکشن فیلڈ چھلنی کا استعمال کیا۔ خصوصیت 3 کے میدان کے لیے موجودہ ریکارڈ () کا اعلان 18 جولائی 2016 کو گورا ایڈج، آئزک کینالس-مارٹنیز، نریلی کروز-کورٹس، الفریڈ مینزز، تھامس اولیویرا، فرانسسکو روڈریگز-ہنریکس، اور لوئس رویرا-زماریپا نے کیا۔ حساب 4841 بٹ کے محدود فیلڈ میں 36·509 عناصر کے ساتھ کیا گیا تھا اور اسے CINVESTAV اور واٹرلو یونیورسٹی کے کئی کمپیوٹرز پر انجام دیا گیا تھا۔ مجموعی طور پر، کمپیوٹنگ کے وقت کے تقریبا 200 بنیادی سال کمپیوٹیشن پر خرچ کیے گئے۔ خصوصیت 3 کے ایک محدود میدان میں پچھلے ریکارڈوں کا اعلان کیا گیا: جوکس اور پیئرٹ (دسمبر 2014) کے ایشیاکرپٹ 2014 کے مقالے کے مکمل ورژن میں۔ ڈی ایل پی کو فیلڈ جی ایف (35·479) میں حل کیا جاتا ہے، جو کہ 3796 بٹ فیلڈ ہے۔ اس کام میں میدان کے کسی بھی "خاص" پہلوؤں کا استحصال نہیں کیا گیا جیسے کہ کمر یا مڑے ہوئے کمر کی خصوصیات۔ کل حساب کتاب میں 8600 سی پی یو گھنٹے سے بھی کم وقت لگا۔ 26 فروری 2014 کو گورا ایڈج، الفریڈ مینزیس، تھامس اولیویرا، اور فرانسسکو روڈریگز-ہنریکس کے ذریعہ، 27 جنوری 2014 کو پچھلے اعلان کو اپ ڈیٹ کیا گیا۔ کمپیوٹیشن 1551 بٹ فیلڈ GF (36·163) میں DLP کو حل کرتا ہے، جس میں 1201 CPU گھنٹے لگتے ہیں۔ 2012 میں فوجیتسو، این آئی سی ٹی، اور کیوشو یونیورسٹی کی ایک مشترکہ ٹیم نے، جس نے 36·97 عناصر اور 923 بٹس کے سائز کے میدان میں ایک مجرد لوگرتھم کا حساب لگایا، فنکشن فیلڈ چھلنی پر تغیر کا استعمال کرتے ہوئے اور 36·71 عناصر اور 676 بٹس کے سائز کے میدان میں پچھلے ریکارڈ کو وسیع مارجن سے شکست دی۔ "اعتدال پسند" سائز کی خصوصیت کے شعبوں میں، 2005 تک قابل ذکر حسابات میں وہ 6553725 عناصر (401 بٹس) کا میدان شامل تھا جس کا اعلان 24 اکتوبر 2005 کو کیا گیا تھا، اور 37080130 عناصر (556 بٹس) کے میدان میں 9 نومبر 2005 کو اعلان کیا گیا تھا۔ "اعتدال پسند" خصوصیت کے ایک محدود میدان کے لیے موجودہ ریکارڈ (2013 تک) کا اعلان 6 جنوری 2013 کو کیا گیا تھا۔ ٹیم نے 3334135357 عناصر (ایک 1425 بٹ محدود فیلڈ) کے میدان میں ایک مجرد لوگارتھم کا حساب لگانے کے لیے میڈیم پرائم کیس کے لیے فنکشن فیلڈ چھلنی کی ایک نئی تبدیلی کا استعمال کیا۔ یہی تکنیک کچھ ہفتے پہلے 3355377147 عناصر (ایک 1175 بٹ محدود فیلڈ) کے میدان میں ایک مجرد لوگرتھم کا حساب لگانے کے لیے استعمال کی گئی تھی۔ 25 جون 2014 کو، رازوان باربولسکو، پییرک گاؤڈری، اورور گیلیویک، اور فرانسوا مورین نے ایک محدود فیلڈ میں ایک مجرد لوگرتھم کے نئے حساب کا اعلان کیا جس کی ترتیب میں 160 ہندسوں ہیں اور یہ ایک پرائم فیلڈ کی ڈگری 2 کی توسیع ہے۔ استعمال کیا جانے والا الگورتھم نمبر فیلڈ چھلنی (این ایف ایس) تھا، جس میں مختلف تبدیلیاں کی گئی تھیں۔ کمپیوٹنگ کا کل وقت سی پی یو (چھان بین) کے ایک کور پر 68 دن اور جی پی یو (لکیری الجبرا) پر 30 گھنٹے کے برابر تھا۔ ایلیپٹک منحنی خطوط سرٹی کام کارپوریشن نے ایلیپٹک وکر کرپٹوگرافی چیلنجز کا ایک سلسلہ جاری کیا ہے۔ لیول I میں 109 بٹ اور 131 بٹ سائز کے فیلڈز شامل ہیں۔ لیول II میں 163، 191، 239، 359 بٹ سائز شامل ہیں۔ فی الحال یہ خیال کیا جاتا ہے کہ سطح دوم کے تمام چیلنجز کمپیوٹیشنل طور پر ناقابل عمل ہیں۔ لیول I کے چیلنجز جن کا سامنا کیا گیا ہے وہ ہیں: ECC2K-108، جس میں 2108 عناصر کے میدان پر کوبلٹز وکر پر ایک مجرد لوگرتھم لینا شامل ہے۔ یہ انعام 4 اپریل 2000 کو تقریبا 1300 افراد کے ایک گروپ کو دیا گیا جس کی نمائندگی رابرٹ ہارلے نے کی تھی۔ انہوں نے اسپیڈ اپ کے ساتھ متوازی پولارڈ رو طریقہ استعمال کیا۔ ECC 2-109، جس میں 2109 عناصر کے میدان پر منحنی خطوط پر ایک مجرد لوگرتھم لینا شامل ہے۔ یہ انعام 8 اپریل 2004 کو تقریبا 2600 افراد کے ایک گروپ کو دیا گیا جس کی نمائندگی کرس مونیکو نے کی۔ انہوں نے پولارڈ رو کے متوازی طریقہ کار کا ایک ورژن بھی استعمال کیا، جس میں 17 ماہ کا کیلنڈر کا وقت لگا۔ ECCp-109، جس میں ایک منحنی ماڈیولو 109 بٹ پرائم پر ایک مجرد لوگارتھم لینا شامل ہے۔ یہ انعام 15 اپریل 2002 کو تقریبا 10308 افراد کے ایک گروپ کو دیا گیا جس کی نمائندگی کرس مونیکو نے کی۔ ایک بار پھر، انہوں نے متوازی پولارڈ رو طریقہ کار کا ایک ورژن استعمال کیا، جس میں کیلنڈر کا وقت 549 دن لگا۔ 131 بٹ (یا اس سے بڑے) چیلنجوں میں سے کوئی بھی پورا نہیں ہوا ہے۔ جولائی 2009 میں، جوپی ڈبلیو بوس، مارسیلو ای کائہرا، تھورسٹن کلینجنگ، آرجن کے لینسٹرا اور پیٹر ایل مونٹگمری نے اعلان کیا کہ انہوں نے ایک الپٹک وکر (جسے سی ای سی پی 112 آر 1 کے نام سے جانا جاتا ہے) ماڈیولو پر ایک مجرد لوگرتھم کا حساب لگایا ہے جو 112 بٹ پرائم ہے۔ حساب لگانا تقریبا 6 مہینوں میں 200 سے زیادہ پلے اسٹیشن 3 گیم کنسولز کے کلسٹر پر کیا گیا تھا۔ انہوں نے پولارڈ رو طریقہ کار کا عام متوازی ورژن استعمال کیا۔ اپریل 2014 میں، گراز یونیورسٹی آف ٹیکنالوجی کے ایرک وینجر اور پال وولفگر نے 18 کور ورٹیکس-6 ایف پی جی اے کلسٹر کا استعمال کرتے ہوئے 113 بٹ کوبلٹز وکر کے مجرد لوگرتھم کو 24 دنوں میں حل کیا۔ جنوری 2015 میں، انہی محققین نے 113 بٹ بائنری فیلڈ پر بیان کردہ ایلیپٹک وکر کے مجرد لوگرتھم کو حل کیا۔ 10-کور کنٹیکس-7 ایف پی جی اے کلسٹر کا استعمال کرتے ہوئے اوسط رن ٹائم تقریبا 82 دن ہے۔ 2 دسمبر 2016 کو، ڈینیئل جے برنسٹین، سوزین اینگلز، تانجا لینج، روبن نیڈر ہیگن، کرسٹوف پار، پیٹر شوابی، اور رالف زیمرمین نے پولارڈ کے رو الگورتھم کے متوازی ورژن کے بہتر ایف پی جی اے نفاذ کا استعمال کرتے ہوئے بائنری وکر پر ایک عام 117.35-bit ایلیپٹک وکر مجرد لوگرتھم کے مسئلے کے حل کا اعلان کیا۔ یہ حملہ متوازی طور پر 64 سے 576 ایف پی جی اے پر تقریبا چھ ماہ تک جاری رہا۔ 23 اگست 2017 کو، تاکویا کوساکا، شو جوئیچی، کین اکوٹا، ایم ڈی۔ الامین کھنڈیکر، یاسویوکی نوگامی، ستوشی اوہرا، نارییوشی یامائی، اور سلوین ڈوکسن نے اعلان کیا کہ انہوں نے پولارڈ کے رو طریقہ کار کی بے ترتیب چہل قدمی کو مؤثر طریقے سے انجام دینے کے لیے بی این وکر کی خصوصی سیکسٹک موڑ کی خاصیت کا استعمال کرتے ہوئے 114 بٹ "جوڑی کے موافق" بیریٹو نیہرگ (بی این) وکر پر ایک مجرد لوگرتھم کا مسئلہ حل کیا ہے۔ نفاذ میں 2000 سی پی یو کور استعمال کیے گئے اور اس مسئلے کو حل کرنے میں تقریبا 6 ماہ لگے۔ 16 جون 2020 کو، الیگزینڈر زینیویکس (زیلار) اور جین لوک پونس (جین لک پونس) نے بٹ کوائن پزل ٹرانزیکشنز چیلنج میں 114 بٹ پرائیویٹ کلید کو حل کرکے سی ای سی پی 256 کے 1 وکر پر 114 بٹ وقفہ ایلیپٹک وکر ڈسکریٹ لوگرتھم کے مسئلے کے حل کا اعلان کیا۔ ایک نیا ریکارڈ قائم کرنے کے لیے، انہوں نے 256x این ویڈیا ٹیسلا وی 100 جی پی یو پروسیسر پر پولارڈ کینگرو پر مبنی اپنا سافٹ ویئر استعمال کیا اور اس میں انہیں 13 دن لگے۔ دو ہفتے پہلے-انہوں نے 109 بٹ وقفہ ای سی ڈی ایل پی کو صرف 3 دنوں میں حل کرنے کے لیے یکساں تعداد میں گرافکس کارڈز کا استعمال کیا۔ نوٹ حوالہ جات بیرونی روابط تاریخ کے لحاظ سے ترتیب شدہ مجرد لوگرتھم کے حسابات غیر متناسب کلیدی الگورتھم ماڈیولر ریاضی لوگرتھم کمپیوٹیشنل سختی کے مفروضے عالمی ریکارڈ