سوال تصادفی از SQuAD:
چه زمانی کشف شد که اعداد اول می توانند برای ایجاد الگوریتم های رمزنگاری کلید عمومی اعمال شوند؟
پاسخ:
دهه 1970
جملات بازیابی شده:
- با این حال، این دیدگاه در 1970s شکسته شد، هنگامی که آن را به عموم اعلام شد که اعداد اول می تواند به عنوان پایه ای برای ایجاد الگوریتم های رمزنگاری کلید عمومی استفاده می شود.
- پرایم ها در چندین روال در فناوری اطلاعات استفاده می شوند، مانند رمزنگاری کلید عمومی، که از ویژگی هایی مانند دشواری فاکتورگیری اعداد بزرگ در فاکتورهای اول آنها استفاده می کند.
- الگوریتم‌هایی بسیار کارآمدتر از تقسیم آزمایشی برای آزمایش اولیه بودن اعداد بزرگ ابداع شده‌اند.
- چندین الگوریتم رمزنگاری کلید عمومی، مانند RSA و تبادل کلید دیفی-هلمن، بر اساس اعداد اول بزرگ هستند (به عنوان مثال، اعداد اول 512 بیتی اغلب برای RSA و اعداد اول 1024 بیتی برای دیفی-هلمن معمولی هستند.) .
- اعداد اول همچنین برای جداول هش و مولد اعداد شبه تصادفی استفاده می شوند.
- برخی از این اعداد اول با استفاده از محاسبات توزیع شده پیدا شده اند.
- برای مدت طولانی، نظریه اعداد به طور کلی، و مطالعه اعداد اول به طور خاص، به عنوان مثال متعارف ریاضیات محض تلقی می شد، بدون اینکه هیچ کاربردی خارج از منافع شخصی مطالعه موضوع به استثنای استفاده از اعداد اول وجود نداشت. دندانه های چرخ دنده برای توزیع یکنواخت سایش.
- الگوریتم‌های قطعی راهی را ارائه می‌دهند تا با اطمینان بگوییم که آیا یک عدد معین اول است یا خیر.
- عبارت "همه الگوریتم های ممکن" نه تنها شامل الگوریتم های شناخته شده امروزی، بلکه هر الگوریتمی است که ممکن است در آینده کشف شود.
- به عنوان مثال، تقسیم آزمایشی یک الگوریتم قطعی است زیرا اگر به درستی اجرا شود، همیشه یک عدد اول را به عنوان اول و یک عدد ترکیبی را به عنوان ترکیبی تشخیص می دهد.
- به عنوان یک مسئله تصمیم گیری بیان می شود، مشکل تصمیم گیری در مورد اینکه آیا ورودی دارای ضریب کمتر از k است یا خیر. هیچ الگوریتم فاکتورسازی اعداد صحیح کارآمد شناخته شده نیست، و این واقعیت اساس چندین سیستم رمزنگاری مدرن، مانند الگوریتم RSA را تشکیل می‌دهد.
- قبل از شروع تحقیقات واقعی که به صراحت به پیچیدگی مسائل الگوریتمی اختصاص داده شده بود، پایه های متعددی توسط محققان مختلف ایجاد شد.
- این اصل محلی-جهانی دوباره بر اهمیت اعداد اول تا نظریه اعداد تأکید می کند.
- الگوریتم‌های احتمالی معمولاً سریع‌تر هستند، اما به طور کامل ثابت نمی‌کنند که یک عدد اول است.
- با این حال، بهترین الگوریتم کوانتومی شناخته شده برای این مسئله، الگوریتم شور، در زمان چند جمله ای اجرا می شود.
- غربال اراتوستن که به اراتوستن نسبت داده می شود، روشی ساده برای محاسبه اعداد اول است، اگرچه اعداد اول بزرگی که امروزه در رایانه ها یافت می شوند به این روش تولید نمی شوند.
- یک مسئله در صورتی ذاتاً دشوار تلقی می شود که راه حل آن به منابع قابل توجهی نیاز داشته باشد، صرف نظر از الگوریتم مورد استفاده.
- الگوریتم هایی که از بیت های تصادفی استفاده می کنند، الگوریتم های تصادفی نامیده می شوند.
- اعتقاد بر این است که اگر یک مشکل را بتوان با یک الگوریتم حل کرد، یک ماشین تورینگ وجود دارد که مشکل را حل می کند.
- با این حال، اعداد کارمایکل به طور قابل توجهی نادرتر از اعداد اول هستند، بنابراین این آزمایش می تواند برای اهداف عملی مفید باشد.
- برای مثال، فهرست دریک نورمن لمر از اعداد اول تا 10006721 که در سال 1956 تجدید چاپ شد، با 1 به عنوان اول اول شروع شد.
- تز Cobham می گوید که اگر یک الگوریتم زمان چند جمله ای را بپذیرد، می توان یک مسئله را با مقدار قابل قبولی از منابع حل کرد.
- اقلیدس همچنین نشان داد که چگونه از عدد اول مرسن یک عدد کامل بسازیم.
- از ژانویه 2016 [به روز رسانی]، بزرگترین عدد اول شناخته شده دارای 22،338،618 رقم اعشاری است.
- چنین سؤالاتی باعث توسعه شاخه های مختلف نظریه اعداد، با تمرکز بر جنبه های تحلیلی یا جبری اعداد شد.