ایک بڑا پرائم نمبر کیسے بنایا جائے | کوانٹا میگزین

پرائم نمبرز مشکل چیزیں ہیں۔ ہم اسکول میں سیکھتے ہیں کہ وہ اعداد ہیں جن میں 1 اور خود کے علاوہ کوئی فیکٹر نہیں ہے، اور یہ کہ ریاضی دانوں کو ہزاروں سالوں سے معلوم ہے کہ ان کی لامحدود تعداد موجود ہے۔ کمانڈ پر ایک تیار کرنا ایسا نہیں لگتا ہے جیسے یہ مشکل ہو۔

لیکن یہ ہے. من مانی طور پر بڑے پرائم نمبرز کو بنانا کافی پیچیدہ ہے۔ آپ کے پاس بنیادی طور پر دو کمپیوٹیشنل آپشنز ہیں، دونوں ہی خرابیوں کے ساتھ۔ آپ بے ترتیب پن کا استعمال کر سکتے ہیں اور اندازہ لگا کر ایک تلاش کر سکتے ہیں، لیکن طریقہ متضاد ہے — آپ ہر بار ایک مختلف پرائم بنانے کا خطرہ چلاتے ہیں۔ یا آپ ایک زیادہ قابل اعتماد، تعییناتی الگورتھم استعمال کر سکتے ہیں، لیکن بھاری کمپیوٹیشنل قیمت پر۔

مئی میں، کمپیوٹر سائنسدانوں کی ایک ٹیم سے ظاہر ہوا کہ ایک قسم کا ہائبرڈ اپروچ بھی کام کر سکتا ہے۔ انہوں نے ایک الگورتھم شائع کیا جو مؤثر طریقے سے ایک مخصوص لمبائی کے پرائم نمبر کو آؤٹ پٹ کرنے کے لیے بے ترتیب اور تعییناتی نقطہ نظر کو یکجا کرتا ہے، جس میں ایک ہی کی فراہمی کے زیادہ امکانات ہوتے ہیں چاہے الگورتھم کئی بار چلایا جائے۔ الگورتھم بے ترتیب پن اور پیچیدگی کو دلچسپ طریقوں سے جوڑتا ہے، اور یہ خفیہ نگاری کے لیے بھی کارآمد ہو سکتا ہے، جہاں کچھ انکوڈنگ اسکیمیں بڑے پرائمز کی تعمیر پر انحصار کرتی ہیں۔

"انہوں نے کوششوں کا ایک سلسلہ ترتیب دیا، ان میں سے ہر ایک مختلف لمبائی کا پرائم نمبر بنانے کی کوشش کر رہا تھا، اور ظاہر کیا کہ ایک کوشش کام کرتی ہے،" کہا۔ روئی بتاؤانسٹی ٹیوٹ فار ایڈوانسڈ اسٹڈی کے ایک نظریاتی کمپیوٹر سائنسدان جو اس کام میں شامل نہیں تھے۔ "یہ ایک ایسی تعمیر ہے جو طے شدہ طور پر منتخب کردہ پرائم کو آؤٹ پٹ کرتی ہے، لیکن آپ کو سککوں کو ٹاس کرنے اور عمل میں بے ترتیب انتخاب کرنے کی اجازت دیتی ہے۔"

پرائمز کے لیے ایک موثر نسخہ بنانے کے چیلنج کی جڑیں گہری ہیں۔ "ہم واقعی اس بارے میں زیادہ نہیں جانتے کہ پرائمز کیسے تقسیم کیے جاتے ہیں، یا پرائمز میں فرق کے بارے میں،" اوفر گراسمین نے کہا، جو سیوڈورنڈم الگورتھم کا مطالعہ کرتے ہیں۔ اور اگر ہم نہیں جانتے کہ انہیں کہاں تلاش کرنا ہے، تو شروع سے پرائم نمبر بنانے کا کوئی آسان طریقہ نہیں ہے۔

وقت گزرنے کے ساتھ، محققین نے مذکورہ بالا طریقوں کو تیار کیا۔ سب سے آسان طریقہ صرف اندازہ لگانا ہے۔ اگر آپ 1,000 ہندسوں کے ساتھ پرائم چاہتے ہیں، مثال کے طور پر، آپ بے ترتیب طور پر 1,000 ہندسوں کا نمبر چن سکتے ہیں اور پھر اسے چیک کر سکتے ہیں۔ "اگر یہ اہم نہیں ہے تو، آپ صرف ایک اور کوشش کریں، اور دوسرا، اور اسی طرح جب تک کہ آپ کو کوئی نہ ملے،" کہا راہل سنتھانم، آکسفورڈ یونیورسٹی میں کمپیوٹر سائنس دان اور نئے مقالے کے شریک مصنف۔ "چونکہ بہت سے پرائمز ہیں، یہ الگورتھم نسبتاً کم تعداد میں تکرار کے بعد، آپ کو کچھ نمبر دے گا جو زیادہ امکان کے ساتھ پرائم ہے۔" لیکن بے ترتیب ہونے کا مطلب ہے کہ آپ کو ہر بار مختلف نمبر ملیں گے۔ اگر آپ کو مستقل مزاجی کی ضرورت ہو تو یہ ایک مسئلہ ہو سکتا ہے — اگر، کہیں، آپ سیکیورٹی کا ایک خفیہ طریقہ کار استعمال کر رہے ہیں جو بڑے پرائمز کی دستیابی پر منحصر ہے۔

دوسرا نقطہ نظر ایک تعییناتی الگورتھم کے ساتھ جانا ہے۔ آپ ابتدائی طور پر ایک نقطہ آغاز منتخب کر سکتے ہیں اور نمبروں کی جانچ شروع کر سکتے ہیں۔ آخر کار آپ کو ایک تلاش کرنا مقصود ہے، اور آپ کا الگورتھم مستقل طور پر آپ کو ملنے والی پہلی کو آؤٹ پٹ کرے گا۔ لیکن اس میں کچھ وقت لگ سکتا ہے: اگر آپ 1,000 ہندسوں کے ساتھ پرائم نمبر تلاش کر رہے ہیں، یہاں تک کہ 2 کے ساتھ حساب⁵⁰⁰ قدم - جو کائنات کی عمر سے کہیں زیادہ وقت لگیں گے - کامیابی کی ضمانت دینے کے لیے کافی نہیں ہیں۔

2009 میں، ریاضی دان اور فیلڈز میڈلسٹ ٹیرنس تاؤ بہتر کرنا چاہتے تھے۔ اس نے ریاضی دانوں کو چیلنج کیا کہ وہ کمپیوٹیشنل وقت کی حد کے اندر ایک مقررہ سائز کا پرائم تلاش کرنے کے لیے ایک متعین الگورتھم کے ساتھ آئیں۔

اس وقت کی حد کو polynomial time کہا جاتا ہے۔ ایک الگورتھم ایک مسئلہ کو کثیر الوقت میں حل کرتا ہے اگر اس کے اٹھائے جانے والے اقدامات کی تعداد ایک کثیر الثانی فعل سے زیادہ نہ ہو۔ n، ان پٹ کا سائز۔ (ایک کثیر الثانی فعل میں ایسی اصطلاحات شامل ہوتی ہیں جن میں متغیرات کو مثبت عددی قوتوں تک بڑھایا جاتا ہے، جیسے n² یا 4n³.) پرائم نمبر کی تعمیر کے تناظر میں، n پرائم میں ہندسوں کی تعداد سے مراد ہے جو آپ چاہتے ہیں۔ کمپیوٹیشنل طور پر، اس کی قیمت زیادہ نہیں ہے: کمپیوٹر سائنس دان ایسے مسائل کی وضاحت کرتے ہیں جنہیں الگورتھم کے ذریعے کثیر الثانی وقت میں حل کیا جا سکتا ہے۔ ایک مشکل مسئلہ، اس کے برعکس، ایکسپونینشل وقت لیتا ہے، جس کا مطلب ہے کہ اس کے لیے ایک کفایتی فنکشن (جس میں 2 جیسی اصطلاحات شامل ہیں) سے لگ بھگ کئی مراحل کی ضرورت ہوتی ہے۔ⁿ).

کئی دہائیوں سے، محققین نے بے ترتیب پن اور سختی کے درمیان تعلق کی تحقیقات کی ہیں۔ پرائم نمبر کی تعمیر کا مسئلہ آسان سمجھا جاتا تھا اگر آپ بے ترتیب ہونے کی اجازت دیتے — اور ہر بار مختلف نمبر حاصل کرنے سے مطمئن ہوتے — اور اگر آپ عزم پر اصرار کرتے تو مشکل۔

ابھی تک کوئی بھی تاؤ کے چیلنج کو پورا کرنے میں کامیاب نہیں ہوا ہے، لیکن نیا کام قریب آتا ہے۔ یہ میساچوسٹس انسٹی ٹیوٹ آف ٹیکنالوجی کے کمپیوٹر سائنس دان شفیع گولڈ واسر اور ایرن گیٹ کے 2011 میں متعارف کرائے گئے نقطہ نظر پر بہت زیادہ توجہ مرکوز کرتا ہے۔ انہوں نے "pseudodeterministic" الگورتھم بیان کیے — تلاش کے مسائل کے لیے ریاضی کی ترکیبیں، جیسے بڑے پرائمز تلاش کرنا، جو بے ترتیب پن کے فوائد کو بروئے کار لا سکتے ہیں اور، زیادہ امکان کے ساتھ، اب بھی ہر بار ایک ہی جواب پیدا کرتے ہیں۔ وہ ترکیب میں بے ترتیب بٹس کی کارکردگی کا استعمال کریں گے، جو نتیجہ میں بے ترتیب ہو جائے گی، جو کہ تعییناتی نظر آئیں گی۔

محققین تب سے سیوڈوڈیٹرمینسٹک الگورتھم کو تلاش کر رہے ہیں۔ 2017 میں، یونیورسٹی آف واروک کے سنتھانم اور ایگور اولیویرا (جنہوں نے نئے کام میں بھی تعاون کیا) بیان کیا پرائمز کی تعمیر کے لیے ایک pseudodeterministic اپروچ جس میں بے ترتیب پن کا استعمال کیا گیا تھا اور یہ یقین سے تعینی نظر آتا تھا، لیکن اس نے "subexponential" وقت میں کام کیا — exponential سے تیز، لیکن polynomial time سے سست۔ پھر 2021 میں، بتائیں اور لیجی چنیونیورسٹی آف کیلیفورنیا، برکلے میں کمپیوٹر سائنس دان، دریافت سیوڈو رینڈم نمبر جنریٹر بنانے کے لیے ایک مشکل مسئلہ کا استعمال کیسے کریں (ایک الگورتھم جو بے ترتیب آؤٹ پٹ سے الگ الگ نمبروں کی ایک تار تیار کرتا ہے)۔ چن نے کہا کہ "[ہمیں] سختی اور چھدمی کے درمیان ایک نیا تعلق ملا۔

یہ ٹکڑے آخر کار 2023 کے موسم بہار میں ایک ساتھ آئے کمپیوٹیشنل پیچیدگی پر ایک بوٹ کیمپ برکلے کے سائمن انسٹی ٹیوٹ فار دی تھیوری آف کمپیوٹنگ میں، جب محققین نے ماضی کے نتائج کو ایک ساتھ بناتے ہوئے اس مسئلے پر مل کر کام کرنا شروع کیا۔ نئے کام کے لیے، چن نے کہا، ہانلن رین — آکسفورڈ میں کمپیوٹر سائنس دان اور ایک شریک مصنف — کے پاس چن-ٹیل کے نتیجے کو سنتھانم-اولیویرا کے نقطہ نظر کے ساتھ جوڑنے کے ابتدائی خیالات تھے۔ پھر پوری ٹیم نے نئے کاغذ کو تیار کرنے کے لیے آئیڈیاز کو مکمل طور پر تیار کیا۔

سنتھانم نے کہا کہ نتیجہ خیز سیڈوڈیٹرمینسٹک الگورتھم نے متعدد وقت میں پرائم نمبرز بنانے کے لیے ماضی کے کام کو دیکھنے کے نئے طریقے استعمال کیے ہیں۔ اس نے ثابت طور پر ایک مخصوص لمبائی کے ایک اہم نمبر کو آؤٹ پٹ کرنے کے لیے بے ترتیب پن کا استعمال کیا، اور یہ ٹول بے ترتیب اندازے سے زیادہ درست اور تعییناتی کرنچنگ سے زیادہ کمپیوٹیشنل طور پر موثر ہے۔

سنتھانم نے کہا کہ نیا الگورتھم بھی قابل ذکر حد تک آسان ہے، اور اسے تلاش کے مسائل کی ایک وسیع رینج پر لاگو کیا جا سکتا ہے — واقعی، نمبروں کے کسی بھی گھنے ذیلی سیٹ پر، جیسے پرائمز، جس کے لیے رکنیت کا تعین کثیر وقت میں کیا جا سکتا ہے۔ لیکن یہ کامل نہیں ہے۔ الگورتھم لامحدود طور پر بہت سی ان پٹ لمبائیوں کے لیے کام کرتا ہے، لیکن یہ ہندسوں کی تمام لمبائیوں کا احاطہ نہیں کرتا ہے۔ کی کچھ قدریں اب بھی ہو سکتی ہیں۔ n وہاں سے باہر جس کے لیے الگورتھم مقررہ طور پر کوئی پرائم تیار نہیں کرتا ہے۔

گراسمین نے کہا کہ "اس چھوٹے سے انتباہ سے چھٹکارا حاصل کرنا اچھا ہوگا۔

سنتھانم نے کہا، حتمی مقصد ایک الگورتھم تلاش کرنا ہے جس کے لیے بے ترتیب ہونے کی بالکل بھی ضرورت نہیں ہے۔ لیکن یہ تلاش کھلی رہتی ہے۔ "ڈیٹرمنزم وہی ہے جسے ہم استعمال کرنا چاہتے ہیں،" انہوں نے کہا۔

لیکن انہوں نے یہ بھی نشاندہی کی کہ سیوڈورنڈم پروسیسز طاقتور ٹولز ہیں، اور پرائمز کی تعمیر جیسے منصوبے ریاضی، کمپیوٹر سائنس، انفارمیشن تھیوری اور دیگر شعبوں سے آئیڈیاز کو جوڑنے کے لیے ان کا استعمال کرنے کا صرف ایک طریقہ ہے۔

ٹیل نے کہا، "یہ کوشش کرنا اور سوچنا بہت دلچسپ ہے کہ یہ شاندار مشاہدات اور کہاں لے جائیں گے۔"