الگوریتم شور

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

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

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

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

جستارهای وابسته

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Shor's algorithm». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۷ شهریور ۱۳۹۴.

↑ Clegg, Brian (2021). Quantum computing : the transformative technology of the qubit revolution. London. p. 81-84. ISBN 978-1-78578-707-2. OCLC 1247151042.
↑ Shor, Peter W. (2003). "Why haven't more quantum algorithms been found?". Journal of the ACM. Association for Computing Machinery (ACM). 50 (1): 87–90. doi:10.1145/602382.602408. ISSN 0004-5411.
↑ Aaronson, Scott (2008). "THE LIMITS OF Quantum". Scientific American. Scientific American, a division of Nature America, Inc. 298 (3): 62–69. JSTOR 26000518. Retrieved 2023-01-12.
↑ Bernhardt, C. (2019). Quantum Computing for Everyone. The MIT Press. MIT Press. p. 7. ISBN 978-0-262-03925-3. Retrieved 2023-01-12.

این یک مقالهٔ خرد ریاضیات است. می‌توانید با گسترش آن به ویکی‌پدیا کمک کنید.

[Clegg_2021_p.-1] Clegg, Brian (2021). Quantum computing : the transformative technology of the qubit revolution. London. p. 81-84. ISBN 978-1-78578-707-2. OCLC 1247151042.

[Shor_2003_pp._87–90-2] Shor, Peter W. (2003). "Why haven't more quantum algorithms been found?". Journal of the ACM. Association for Computing Machinery (ACM). 50 (1): 87–90. doi:10.1145/602382.602408. ISSN 0004-5411.

[Aaronson_2008_pp._62–69-3] Aaronson, Scott (2008). "THE LIMITS OF Quantum". Scientific American. Scientific American, a division of Nature America, Inc. 298 (3): 62–69. JSTOR 26000518. Retrieved 2023-01-12.

[Bernhardt_2019_p._174-4] Bernhardt, C. (2019). Quantum Computing for Everyone. The MIT Press. MIT Press. p. 7. ISBN 978-0-262-03925-3. Retrieved 2023-01-12.

[۱]

[۲]

[۳]

[۴]