چگونه یک عدد اول بزرگ بسازیم | مجله کوانتا

اعداد اول چیزهای پیچیده ای هستند. ما در مدرسه می آموزیم که آنها اعدادی هستند که هیچ عاملی جز 1 و خودشان ندارند و ریاضیدانان هزاران سال است که می دانند تعداد نامحدودی از آنها وجود دارد. به نظر نمی رسد که تولید یکی از آنها کار سختی باشد.

اما آن است. ساختن اعداد اول دلخواه بزرگ بسیار پیچیده است. شما اساساً دو گزینه محاسباتی دارید که هر دو دارای اشکالاتی هستند. می‌توانید از تصادفی استفاده کنید و با حدس زدن یکی را پیدا کنید، اما این روش ناسازگار است - هر بار خطر ایجاد یک عدد اول متفاوت را دارید. یا می توانید از یک الگوریتم مطمئن تر و قطعی تر، اما با هزینه محاسباتی سنگین استفاده کنید.

در ماه مه، تیمی از دانشمندان کامپیوتر نشان داد که نوعی رویکرد ترکیبی نیز می تواند کارساز باشد. آنها الگوریتمی را منتشر کردند که به طور موثر رویکردهای تصادفی و قطعی را برای خروجی یک عدد اول با طول خاص با احتمال زیاد ارائه همان عدد حتی اگر الگوریتم چندین بار اجرا شود، ترکیب می‌کند. این الگوریتم تصادفی و پیچیدگی را به روش‌های جالبی به هم متصل می‌کند، و همچنین ممکن است برای رمزنگاری مفید باشد، جایی که برخی از طرح‌های رمزگذاری بر ساخت اعداد اول بزرگ متکی هستند.

گفت: «آنها دنباله ای از تلاش ها را انجام دادند، هر یک از آنها سعی کردند عدد اول با طول متفاوت بسازند، و نشان دادند که یکی از تلاش ها جواب می دهد. روئی تل، یک دانشمند نظری کامپیوتر در موسسه مطالعات پیشرفته که با این کار درگیر نبود. "این ساختاری است که یک عدد اول انتخابی قطعی را تولید می کند، اما به شما امکان می دهد سکه ها را پرتاب کنید و در این فرآیند انتخاب های تصادفی داشته باشید."

چالش ایجاد یک دستور العمل کارآمد برای اعداد اول ریشه عمیقی دارد. اوفر گروسمن که الگوریتم‌های شبه تصادفی را مطالعه می‌کند، می‌گوید: «ما واقعاً چیز زیادی در مورد نحوه توزیع اعداد اول یا شکاف‌های اعداد اول نمی‌دانیم. و اگر ندانیم کجا آنها را پیدا کنیم، هیچ راه آسانی برای تولید یک عدد اول از ابتدا وجود ندارد.

با گذشت زمان، محققان رویکردهای فوق را توسعه دادند. ساده ترین راه فقط حدس زدن است. برای مثال اگر یک عدد اول با 1,000 رقم می خواهید، می توانید یک عدد 1,000 رقمی را به طور تصادفی انتخاب کنید و سپس آن را بررسی کنید. گفت: "اگر بهترین نیست، فقط یکی دیگر را امتحان کنید، و دیگری را امتحان کنید، و همینطور ادامه دهید تا زمانی که یکی را پیدا کنید." راهول سانتانام، دانشمند کامپیوتر در دانشگاه آکسفورد و یکی از نویسندگان مقاله جدید. از آنجایی که اعداد اول زیادی وجود دارد، این الگوریتم پس از تعداد نسبتاً کمی تکرار، تعدادی عدد اول را با احتمال زیاد به شما می‌دهد. او گفت، اما استفاده از تصادفی بودن به این معنی است که احتمالاً هر بار یک عدد متفاوت دریافت خواهید کرد. اگر به یکپارچگی نیاز دارید، این می تواند مشکل ساز باشد - مثلاً اگر از یک روش رمزنگاری امنیتی استفاده می کنید که به در دسترس بودن اعداد اول بزرگ بستگی دارد.

روش دیگر این است که با یک الگوریتم قطعی پیش بروید. می توانید یک نقطه شروع را انتخاب کنید و شروع به آزمایش اعداد، به صورت متوالی، برای اولیه بودن کنید. در نهایت قرار است یکی را پیدا کنید و الگوریتم شما به طور پیوسته اولین موردی را که پیدا می کنید خروجی می دهد. اما ممکن است کمی طول بکشد: اگر به دنبال یک عدد اول با 1,000 رقم هستید، حتی یک محاسبه با 2⁵⁰⁰ قدم‌هایی که بسیار طولانی‌تر از سن جهان طول می‌کشد، برای تضمین موفقیت کافی نیست.

در سال 2009، ترنس تائو، ریاضیدان و برنده مدال فیلدز، می خواست بهتر عمل کند. او ریاضیدانان را به چالش کشید تا یک الگوریتم قطعی برای یافتن عدد اول با اندازه معین در یک محدودیت زمانی محاسباتی ارائه کنند.

این محدودیت زمانی به عنوان زمان چند جمله ای شناخته می شود. یک الگوریتم اگر تعداد مراحلی که طی می کند بیش از یک تابع چند جمله ای نباشد، یک مسئله را در زمان چند جمله ای حل می کند. n، اندازه ورودی. (یک تابع چند جمله ای شامل عباراتی است که دارای متغیرهایی هستند که به توان های عدد صحیح مثبت افزایش یافته اند، مانند n² یا 4n³.) در زمینه ساخت اعداد اول، n به تعداد ارقام اول مورد نظر شما اشاره دارد. از نظر محاسباتی، این هزینه زیادی ندارد: دانشمندان کامپیوتر مسائلی را که می‌توان با الگوریتم‌ها در زمان چند جمله‌ای حل کرد، به آسانی توصیف می‌کنند. در مقابل، یک مشکل سخت زمان نمایی می‌برد، به این معنی که به تعدادی گام نیاز دارد که توسط یک تابع نمایی تقریبی شده است (که شامل عباراتی مانند 2 است.ⁿ).

برای دهه ها، محققان ارتباط بین تصادفی و سختی را بررسی کرده اند. اگر تصادفی بودن را مجاز می‌شمارید - و هر بار به دریافت عدد متفاوتی رضایت می‌دادید - مشکل ساخت اعداد اول آسان تلقی می‌شد و اگر بر جبرگرایی پافشاری می‌کردید سخت در نظر گرفته می‌شد.

هنوز کسی نتوانسته با چالش تائو روبرو شود، اما کار جدید نزدیک است. این به شدت از رویکردی است که در سال 2011 توسط Shafi Goldwasser و Eran Gat، دانشمندان کامپیوتر در موسسه فناوری ماساچوست معرفی شد. آنها الگوریتم‌های «شبه‌جبرانه» را توصیف کردند - دستور العمل‌های ریاضی برای مسائل جستجو، مانند یافتن اعداد اول بزرگ، که می‌توانند از مزایای تصادفی بودن استفاده کنند و با احتمال زیاد، همچنان هر بار پاسخ یکسانی را تولید کنند. آن‌ها از کارایی بیت‌های تصادفی در دستور غذا استفاده می‌کنند، که در نتیجه از حالت تصادفی خارج می‌شود و قطعی به نظر می‌رسد.

محققان از آن زمان تاکنون در حال بررسی الگوریتم‌های شبه قطعی بوده‌اند. در سال 2017، سانتانام و ایگور اولیویرا از دانشگاه وارویک (که همچنین در کار جدید مشارکت داشت) شرح داده شده یک رویکرد شبه قطعی برای ساختن اعداد اول که از تصادفی استفاده می‌کرد و به طور قانع‌کننده‌ای قطعی به نظر می‌رسید، اما در زمان «زیر نمایی» - سریع‌تر از زمان نمایی، اما کندتر از زمان چند جمله‌ای، کار می‌کرد. سپس در سال 2021، Tell and لیجی چن، دانشمند کامپیوتر در دانشگاه کالیفرنیا، برکلی، کاوش چگونه از یک مسئله سخت برای ساختن یک مولد اعداد شبه تصادفی (الگوریتمی که رشته ای از اعداد غیرقابل تشخیص از یک خروجی تصادفی تولید می کند) استفاده کنیم. چن گفت: «[ما] ارتباط جدیدی بین سختی و شبه تصادفی پیدا کردیم.

این قطعات سرانجام در بهار 2023، در طول یک بوت کمپ در مورد پیچیدگی محاسباتی در مؤسسه تئوری محاسبات سیمونز در برکلی، زمانی که محققان شروع به کار با هم روی این مشکل کردند و نتایج گذشته را با هم ترکیب کردند. چن گفت، برای کار جدید، هانلین رن - دانشمند کامپیوتر در آکسفورد و یکی از نویسندگانش - ایده های اولیه را داشت تا نتیجه چن-تل را با رویکرد سانتانام-اولیویرا به روشی بدیع ترکیب کند. سپس کل تیم ایده ها را به طور کامل تری برای تولید مقاله جدید توسعه دادند.

سانتانام گفت که الگوریتم شبه قطعی حاصل از روش‌های جدیدی برای نگاه کردن به کارهای گذشته برای تولید اعداد اول در زمان چند جمله‌ای استفاده کرد. به طور ثابت از تصادفی برای خروجی یک عدد اول با طول خاص استفاده می کرد، و این ابزار دقیق تر از حدس زدن تصادفی و از نظر محاسباتی کارآمدتر از کرانچ قطعی است.

سانتانام گفت، الگوریتم جدید نیز به‌طور قابل‌توجهی ساده است و می‌توان آن را برای طیف گسترده‌ای از مسائل جستجو به کار برد - در واقع، برای هر زیرمجموعه متراکمی از اعداد، مانند اعداد اول، که عضویت آن را می‌توان در زمان چند جمله‌ای تعیین کرد. اما کامل نیست. این الگوریتم برای بی نهایت طول ورودی کار می کند، اما تمام طول ارقام را پوشش نمی دهد. ممکن است هنوز مقادیری وجود داشته باشد n در جایی که الگوریتم به طور قطعی یک عدد اول تولید نمی کند.

گروسمن گفت: «خیلی خوب است که از شر آن اخطار کوچک خلاص شویم.

Santhanam گفت که هدف نهایی یافتن الگوریتمی است که به هیچ وجه به تصادفی بودن نیاز نداشته باشد. اما این تلاش همچنان باز است. او گفت: «جبرگرایی چیزی است که ما می خواهیم از آن استفاده کنیم.

اما او همچنین خاطرنشان کرد که فرآیندهای شبه تصادفی ابزار قدرتمندی هستند و پروژه‌هایی مانند ساخت اعداد اول تنها یکی از راه‌های استفاده از آن‌ها برای اتصال ایده‌هایی از ریاضیات، علوم کامپیوتر، تئوری اطلاعات و سایر زمینه‌ها هستند.

تل گفت: "این هیجان انگیز است که تلاش کنید و فکر کنید که این مشاهدات درخشان به کجا منجر می شود."