الگوریتم شور

الگوریتم شور  یک الگوریتم کوانتومی، برای تجزیه عددها به عوامل اول در زمان چندجمله‌ای (Polynomial time) است. نام این الگوریتم که به افتخار پیتر شر نام‌گذاری شده است، در سال ۱۹۹۴ فرمول‌بندی شد. تجزیه یک عدد به عوامل اول ممکن است در نگاه اول مسئله سختی به نظر نرسد مثلا همه می دانیم که عوامل اول عدد صحیح ۹۱ هفت و سیزده هستند ولی  برای اعداد واقعا بزرگ یافتن عوامل اول بسیار دشوار و زمانبر است.

این الگوریتم عوامل اول یک عدد صحیح بزرگ را شناسایی می کند و از دو بخش کلاسیک و کوانتومی تشکیل شده است. در بخش کلاسیک این الگوریتم از ویژگی ها و قضایای مختلف ریاضی برای مثال قضیه اویلر از نظریه اعداد استفاده می کند و در بخش کوانتومی از تبدیل فوریه کوانتومی استفاده می کند.

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

مسئله تجزیه عددها به عوامل اول به عنوان یک مسئله ان‌پی کامل شناخته نمی شود و حل آن به این معنا نیست که همه مسائل ریاضی (از جمله مسائل  ان‌پی کامل) را می توان با الگوریتم های کوانتومی حل کرد. این الگوریتم از ساختار و خواص ویژه مسئله تجزیه عددها به عوامل اول استفاده می کند و این خواص لزوما قابل تعمیم به سایر مسائل نیستند. در واقع مسئله تجزیه عددها به عوامل اول به کلاس پیچیدگی کوانتومی BQP  تعلق دارد که به این معناست که اگر این الگوریتم پیاده سازی شود می تواند عوامل اول عددهای بزرگ را شناسایی کند و زمانی که مدار کوانتومی ساخته شود رمزنگاری آراس‌ای دیگر امن نخواهد بود.

 جستارهای وابسته 
 الگوریتم کوانتومی
 اطلاعات کوانتومی
 تبدیل فوریه کوانتومی
 رمزنگاری پساکوانتوم
 نظریه پیچیدگی کوانتومی
 الگوریتم گرور

 منابع 


رده:الگوریتم‌های تجزیه به عامل‌های عدد صحیح
رده:الگوریتم‌های کوانتومی
رده:رمزنگاری پساکوآنتوم
رده:علوم اطلاعات کوانتومی