الگوریتم شور به زبان ساده؛ رمزگشایی داده در کامپیوتر کوانتومی

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

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

اما این ادعا چقدر به واقعیت نزدیک است؟ یا چند سال با تبدیل شدن به واقعیت فاصله دارد؟ اصلا کامپیوتر کوانتومی چگونه قفل داده‌های رمزنگاری‌شده را می‌شکند؟ جواب «الگوریتم شور» (Shor's algorithm) است. اگر کنجکاوید بدانید این الگوریتم چطور کار می‌کند و چگونه می‌تواند در عرض چند دقیقه از داده‌ای رمزگشایی کند که در کامپیوتر معمولی میلیون‌ها سال زمان می‌برد، با این مقاله همراه باشید.

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

در مورد محاسبات ریاضی به کمک رایانش کوانتومی هم این حالت وجود دارد. در کامپیوتر کوانتومی، ذرات‌ (الکترون یا فوتون)، به کمک لیزرهایی با دقت بسیار بالا یا پرتوهای مایکروویو در حالت برهم‌نهی قرار گرفته و همیشه در حال نوسان هستند. حالت این ذرات تا زمانی ‌که مقادیرشان اندازه‌گیری نشده است، معلوم نیست. اما اگر تمام حالت‎‌هایی که این ذرات ممکن است به خود بگیرد شناخته شده باشد، آن وقت می‌توان گفت آن‌ها هم‌زمان در تمام آن حالت‌های ممکن وجود دارند. 

ازآنجاکه هر کیوبیت هر دو حالت صفر و یک بیت را در خود ذخیره می‌کند، به تعداد N کیوبیت می‌توان هم‌زمان دو برابر حالت‌های ممکن داده‌ی ذخیره‌شده در بیت را ذخیره کرد. این مقدار بسیار قابل توجهی است؛ در جهان ۱۰ به توان ۷۸ تا ۱۰ به توان ۸۲ اتم قابل مشاهده وجود دارد و ۲۶۵ کیوبیت می‌تواند هم‌زمان به اندازه‌ی تمام اتم‌های جهان در خود داده ذخیره کند. 

علاوه بر پدیده‌ی برهم‌نهی، کیوبیت‌ها ویژگی مهم دیگری نیز دارند که به آن درهم‌تنیدگی (entanglement) می‌گویند. در این حالت، تغییر رفتار یکی از دو کیوبیت درهم‌تنیده شده بلافاصله در رفتار کیوبیت دوم به‌صورت کاملا پیش‌بینی‌شده‌ای تغییر ایجاد می‌کند. در پدیده‌ی درهم‌تنیدگی اتفاق بسیار شگفت‌انگیزی رخ می‌دهد و آن تأثیر دو کیوبیت درهم‌تنیده بر یکدیگر در فواصل بسیار طولانی است.

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

پدیده‌ی درهم‌تنیدگی بسیار شبیه جادوگری به نظر می‌رسد و فیزیکدانان هم به‌طور کامل از سازوکار آن سر در نمی‌آورند (حتی اینشتین هم آن را «رفتار عجیب و اسرارآمیز در فاصله‌ی دور» نامید!)؛ اما در حوزه‌ی رایانش کوانتومی، این پدیده کمک می‌کند حتی در صورت عدم قطعیت، اطلاعات از جایی به‌جای دیگر منتقل شود. مثل این می‌ماند از سکه‌ی که هنوز در حال چرخش است، برای حل محاسبات پیچیده استفاده کرد. با اتصال چندین کیوبیت به یکدیگر می‌توان مسائلی را حل کرد که حتی سریع‌ترین کامپیوترهای غیر کوانتومی برای حل آن‌ها به میلیون‌ها سال زمان نیاز دارند. 

در مورد طرز کار کامپیوتر کوانتومی این تصور رایج وجود دارد که چندین کامپیوتر معمولی در کنار هم و هم‌زمان با هم روی مسئله‌ای واحد کار می‌کنند؛ این تصور تا حدودی هم درست و هم نادرست است. 

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

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

در ادامه و در بخش طرز کار الگوریتم شور خواهیم دید محققان چگونه به کمک الگوریتمی برای اعمال «برهم‌نهی ویرانگر»، تمام حالت‌های نادرست را خنثی می‌کنند و به کمک «برهم‌نهی سازنده»، پاسخ درست را تقویت می‌کنند تا انتخاب رایانش کوانتومی باشد.

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

شور هکری با نیتی شرورانه نبود، بلکه ریاضیدانی بود که در مرکز آزمایشی بل لبز مانند ریاضیدان‌های مثل خودش دنبال حل مسائل دشوار ریاضی می‌گشت. الگوریتم او که به الگوریتم شور (Shor’s Algorithm) معروف است، به نوعی فناوری نیاز داشت که در زمان انتشار مقاله در سال ۱۹۹۴ به زحمت در سطح نظریه مطرح شده بود و تا رسیدن به مرحله‌ی عملیاتی به سال‌ها زمان نیاز داشت.

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

امنیت رمزنگاری داده بر اساس «بیت‌های امنیت» سنجیده می‌شود. برای مثال، مهاجم سایبری برای رمزگشایی از داده‌ای که با کلید ۱۲۸ بیتی AES (استاندارد رمزنگاری پیشرفته)، یا با کلید ۲۵۶ بیتی منحنی بیضوی (Elliptic-curve cryptography) یا کلید ۳۰۷۲ بیتی RSA رمزنگاری‌شده است، به انجام ۲۱۲۸ مرحله‌ی محاسباتی نیاز دارد. به عبارت دیگر، هر کدام از این سه روش برای رمزنگاری داده، دارای ۱۲۸ بیت امنیت است. 

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

برای تصور بهتر این موضوع، خوب است بدانید کلید رمزنگاری ۲۵۶ بیتی شامل دو به توان ۲۵۶ ترکیب ممکن است. این یعنی:

۱۱۵,۷۹۲,۰۸۹,۲۳۷,۳۱۶,۱۹۵,۴۲۳,۵۷۰,۹۸۵,۰۰۸,۶۸۷,۹۰۷,۸۵۳,۲۶۹,۹۸۴,۶۶۵,۶۴۰,۵۶۴,۰۳۹,۴۵۷,۵۸۴,۰۰۷,۹۱۳,۱۲۹,۶۳۹,۹۳۶ ترکیب ممکن (عدد ۷۸ رقمی). حتی سریع‌ترین اَبَرکامپیوتر دنیا، یعنی Tianhe-2، برای رمزگشایی از این کلید به میلیون‌ها سال زمان نیاز دارد. 

اگر مهندسان موفق شوند کامپیوترهای کوانتومی با تعداد بسیار زیادی کیوبیت (هزاران کیوبیت) تولید کنند و دست مهاجمان سایبری به این کامپیوترها برسد، آن وقت امنیت الگوریتم RSA و روش‌های رمزنگاری مشابه به‌طور کامل نابود می‌شود. 

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

ویژگی دیگر رمزنگاری RSA استفاده از عملیات ضرب دو عدد اول است (N= a.b) که حاصل آن (N) همان داده‌ی رمزنگاری‌شده است. انجام عملیات ضرب بسیار آسان است و هر کامپیوتری از پس محاسبه‌ی آن به‌راحتی برمی‌آید. اما سختی کار جایی است که قرار است این عملیات به‌صورت معکوس انجام شود. یعنی اگر از شما بپرسند عدد ۷۰۱۱۱۱ از ضرب کدام دو عدد اول به دست آمده است، آیا می‌توانید جواب را پیدا کنید؟

پیدا کردن جواب این مسئله حتی با ماشین‌حساب یا کامپیوتر امکان‌پذیر نیست. درحالی‌که اگر سؤال این بود که حاصل ضرب ۹۰۷ در ۷۷۳ چقدر می‌شود، با همان ماشین‎‌حساب به‌راحتی می‌توانستید به جواب ۷۰۱۱۱۱ برسید. این دو عدد درواقع همان اعداد اولی هستند که در سؤال قبلی قرار بود آن‌ها را پیدا کنیم؛ اما هیچ راهی برای رسیدن به آن نداشتیم. 

ازآنجاکه محاسبه‌ی رابطه‌ی بین این اعداد از یک سو آسان و از سوی مخالف به‌شدت دشوار است، به آن تابع دریچه (trapdoor function) می‌گویند. در رمزنگاری RSA برای هرچه دشوارتر کردن حدس این دو مضرب، از اعداد بسیار بسیار بزرگ استفاده می‌شود. برای مثال، کلید ۲۰۴۸ بیتی RSA برای رمزنگاری داده از کلیدی استفاده می‌کند که از ۶۱۷ رقم تشکیل شده است. 

ممکن است برای برخی این سؤال پیش آمده باشد که چطور الگوریتمی مانند RSA که فقط با اعداد و ارقام سروکار دارد، می‌تواند پیامی مثل «برای من ساندویچ بخر» را رمزنگاری کند. جواب این است که تمام اطلاعاتی که در کامپیوتر پردازش می‌شود به‌صورت باینری (صفر و یک) ذخیره‌ شده‌اند و از استانداردهای کُدبندی نویسه مانند یونی‌کد (Unicode) یا اسکی (ASCII) برای نمایش دادن آن‌ها به‌صورت حروفی که برای انسان قابل‌فهم باشند، استفاده می‌شود.

این به این معنی است که پیامی مانند «برای من ساندویچ بخر» در کامپیوتر به‌صورت صفر و یک کدنویسی شده است و به‌راحتی می‌تواند به شکل زنجیره‌ای از اعداد در الگوریتم RSA رمزنگاری شود. 

با این اوصاف می‌توان گفت دشواری شکستن رمزنگاری RSA در دو لایه مطرح می‌شود: ۱- اعدادی که در این الگوریتم استفاده می‌شوند به‌ حدی بزرگ هستند که دستیابی به کلید خصوصی با آزمون و خطا ممکن نیست. ۲- کامپیوترهای کنونی برای پیدا کردن مضرب‌های اول این اعداد بسیار بزرگ به میلیون‌ها یا شاید میلیاردها سال محاسبه نیاز دارند.

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

همان‌طور که گفته شد در رمزنگاری RSA، از حاصل ضرب دو عدد اول، عدد بسیار بزرگ N حاصل می‌شود. فردی که بتواند این دو عدد اول را پیدا کند، در واقع توانسته از داده رمزگشایی کند. اما پیدا کردن این دو عدد اول تقریبا غیر ممکن است، مگر اینکه از الگوریتم شور در کامپیوتر کوانتومی استفاده شود.   

طبق این الگوریتم، هر حدس رندوم و بی‌اساس (g) از عددی که ممکن است مضربی از N باشد، اگر به توان p/2 برسد و یک واحد به آن اضافه یا کم شود، به جواب درست بسیار نزدیک‌تر است. به نظر ساده است، به شرطی که بتوانیم مقدار p را پیدا کنیم. مقدار p را هم می‌توان تقریبا بلافاصله و با انجام تنها یک محاسبه‌ی کوانتومی‌ موسوم به تبدیل فوریه (Fourier transform)، که البته کمی پیچیده است، به دست آورد.

پس در الگوریتم شور کار را با حدس عددی رندوم شروع می‌کنیم که ممکن است مضربی از عدد N باشد (اما به احتمال زیاد نیست) و بعد این الگوریتم این حدس رندوم را به حدس خیلی بهتری که احتمالا مضربی از N باشد، تبدیل می‌کند. 

در این فرایند هیچ فیزیک کوانتومی دخیل نیست و می‌توان آن را روی کامپیوترهای معمولی برای پیدا کردن مضرب‌های عددی بزرگ اجرا کرد. اما چالش اصلی مدت‌زمان بسیار زیادی است که لازم است کامپیوتر معمولی حدس رندوم و غیر محتمل ما را به حدس بهتری که احتمالا جواب درست باشد، تبدیل کند. مثلا پیدا کردن دو مضرب عددی که ۵۰ رقم دارد شاید روی کامپیوتر معمولی چند دقیقه طول بکشد؛ اما اگر این عدد ۲۳۲ رقم داشته باشد، سال‌ها زمان لازم است تا دو مضرب آن پیدا شود. در واقع در سال ۲۰۰۹، تیمی ۱۲ نفره از محققان برای پیدا کردن دو مضرب N با ۲۳۲ رقم، دو سال زمان صرف کردند. 

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

اما الگوریتم شور چگونه حدس رندوم و غیر محتمل ما را به حدس بهتری تبدیل می‌کند‌ (فرایند کاملا ریاضیاتی) و چرا کامپیوتر کوانتوم این فرایند را تسریع می‌کند (عملیات فیزیکی)؟

همه چیز با عدد بزرگ N شروع می‌شود که قرار است مضرب‌های آن را پیدا کرده تا به این ترتیب قفل اطلاعات رمزنگاری‌شده را بشکنیم. این دو مضرب برای ما نامعلوم است، برای همین عددی کوچکتر از N را به‌عنوان حدس اولیه خود انتخاب می‌کنیم. نکته‌ی قابل‌توجه این است که نیازی نیست عددی که حدس می‌زنیم حتما مضرب اصلی N باشد. این حدس می‌تواند عددی باشد که در مضربی با N مشترک است؛ مثلا ۴ مضربی از ۶ نیست؛ اما هر دو در مضرب ۲ با هم مشترک هستند. 

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

اما داستان به این سادگی‌ها هم نیست. برای اعداد بسیار بزرگی که در رمزنگاری به کار می‌روند، اینکه هر حدس در مضربی از N مشترک باشد تا حد نجومی غیر محتمل است. برای همین در این الگوریتم از ترفندی استفاده می‌شود تا حدس غیر متحمل به حدسی تبدیل شود که احتمال داشتن مضرب مشترکی با N در آن زیاد باشد. 

این ترفند بر اساس یک قاعده‌ی ساده‌ی ریاضی است: برای هر جفت عدد صحیحی که با یکدیگر مضرب مشترکی ندارند (مثلا N و g)، اگر یکی از آن‌ها را (g) به اندازه‌ی کافی در خودش ضرب کنید (p)، سرانجام به عدد صحیحی خواهید رسید که مضربی از عدد دوم (m.N) به‌علاوه‌ی یک است.

برای مثال فرض کنید N عدد ۱۵ و حدس اولیه‌ی ما به‌عنوان یکی از دو مضرب ۱۵، عدد ۷ است (چون ۱۵ عدد بسیار کوچکی است، واضح است ۷ مضربی از آن نیست؛ اما برای اعداد بزرگتر نمی‌توان در همان نگاه اول مشخص کرد حدس رندوم ما جواب درست است یا خیر). درحالی‌که عدد ۷ به توان ۲ مساوی مضربی از ۱۵ به اضافه‌ی یک نیست و ۷ به توان ۳ هم اینطور نیست؛ اما ۷ به توان ۴ دقیقا مساوی مضربی از ۱۵ به اضافه‌ی یک است؛ یعنی مقدار p در این معادله برابر ۴ است.

پس برای عدد بزرگ N و حدس غیر محتمل g، می‌توان مطمئن بود توانی از g مساوی مضربی از N به اضافه‌ی یک است. با جابجایی هوشمندانه‌ی این معادله، می‌شود آن را به این صورت بازنویسی کرد:

 به این ترتیب معادله‌ای داریم که شبیه این است: (چیزی) ضرب (چیز دیگری) مساوی N است و این دو دقیقا همان اعدادی است که دنبال آن هستیم: دو مضرب N. به این ترتیب الگوریتم شور حدس رندوم ما را به کمک این فرمول به اعدادی تبدیل می‌کند که مضربی از N است و به عبارت دیگر، خود این دو عدد احتمالا مضاربی از دو مضرب اصلی N باشند. برای رسیدن به خود N کافی است از الگوریتم اقلیدس کمک بگیریم.

مثلا: 

اما ۵۰ و ۴۸ هیچ‌کدام مضربی از ۱۵ نیست؛ اما به کمک ب.م.م می‌توان بین ۵۰ و ۱۵ عدد ۵ و بین ۴۸ و ۱۵ عدد ۳ را به دست آورد. ۵ و ۳ دو مضرب ۱۵ (N) هستند و به این ترتیب داده رمزگشایی می‌شود.

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

مسئله این است که رسیدن به این حدس‌های جدید و بهبودیافته ما را با سه مشکل روبه‌رو می‌کند: 

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

مشکل دوم این است که p عدد فرد باشد که در این صورت حاصل تقسیم p بر ۲، عدد صحیح نخواهد بود که این هم به کار ما نمی‌آید. 

اما برای هر حدس تصادفی، حداقل در سه‌هشتم موارد این احتمال وجود دارد که هیچ یک از این دو مشکل پیش نیاید و p حدس‌هایی ایجاد کند که مضاربی از N باشند و رمز را بشکنند. این احتمال ارزش تکرار دارد. برای هر حدس اولیه حداقل در ۳۷٫۵ درصد موارد این احتمال وجود دارد که g^p/2 ±1 به مضربی از N بیانجامد؛ این یعنی ۹۹ درصد این احتمال وجود دارد تا تنها با ۱۰ حدس، به مضارب N برسیم و داده‌ را رمزگشایی کنیم. 

اما مشکل سوم به این سادگی قابل حل نیست. برای تبدیل حدس غیر محتمل به حدس خوب لازم است آن را آن‌قدر در خودش ضرب کنیم تا به مضربی از N به اضافه‌ی یک برسیم. برای کامپیوتر معمولی پیدا کردن این توان (p) زمان و کار زیادی می‌برد. اینجا است که پای مکانیک کوانتوم به داستان باز می‌شود و کل این فرایند را به طرز جنون‌آمیزی سرعت می‎‌بخشد. 

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

کلید محاسبات سریع کوانتومی در رسیدن به نوعی برهم‌نهی کوانتوم است که تمام جواب‌های ممکن را هم‌زمان محاسبه کند و در عین حال به‌طور کاملا هوشمندانه‌ای تمام جواب‌های نادرست را در حالت برهم‌نهی ویرانگر (destructive interference) قرار بدهد تا یکدیگر را خنثی کنند. در این حالت وقتی جواب مسئله محاسبه می‌شود، خروجی دیگر رندوم نیست و به احتمال زیاد جواب درست است. 

ما در این معادله دنبال عدد p هستیم. عدد p در واقع به period (دوره) اشاره می‌کند و دارای خاصیت تناوبی است به این معنی که اگر یک توان رندوم (x) را در نظر بگیریم و اندازه‌ی p را به آن اضافه (یا از آن کم) کنیم، مقداری که به اضافه‌ی مضربی در N است (یعنی r)، همواره یکسان باقی خواهد ماند.

مثلا اگر:

آن‌وقت

و

به این ترتیب به هر تعداد مقادیر p به توان رندوم g اضافه کنیم، جواب معادله همیشه به اندازه‌ی یکسان (اینجا ۳) از مضربی از N بیشتر است. در این حالتِ برهم‌نهی، اعدادی در اختیار داریم که به‌طور تناوبی به اندازه‌ی دوره‌ی p تکرار می‌شوند یا به عبارت دیگر، به اندازه‌ی فرکانس یک بر p تکرار می‌شوند. اگر بتوانیم این فرکانس را پیدا کنیم، می‌توانیم مقدار p را پیدا کنیم و با داشتن مقدار p و قرار دادن آن در فرمول می‌توانیم دو مضرب N را پیدا و داده را رمزگشایی کنیم. 

بهترین ابزار برای پیدا کردن فرکانس، تبدیل فوریه (Fourier transform) است که سیگنال‌های صوتی را به موج را تبدیل می‌کند و آن را به‌صورت نموداری از توابع سینوس و کسینوس برای نمایش فرکانس‌های مختلف تشکیل‌دهنده‌ی موج نشان می‌دهد. 

نسخه‌ی کوانتومی تبدیل فوریه به محققان این امکان را می‌دهد تا با اعمال آن به برهم‌نهی کوانتومی که با فرکانس یک بر p تکرار می‌شود، تمام فرکانس‌های نادرست ممکن را در تداخل ویرانگر قرار داده تا همدیگر را از بین ببرند (موجی با دامنه‌ی صفر) و تنها یک حالت کوانتوم در آخر باقی بماند؛ یعنی همان عدد یک بر p. 

با معکوس کردن یک بر p، به p می‌رسیم و مادامی که p عدد زوج باشد (که از تقسیم آن بر ۲، عدد صحیح حاصل شود) می‌توانیم حدس اولیه‌ی خود را به توان این عدد تقسیم بر دو برسانیم و به اندازه‌ی یک واحد به آن اضافه و از آن کم کنیم. تا زمانی‌ که به مضرب دقیقی از N نرسیم، می‌توانیم مطمئن باشیم حدس ما حالا در مضربی از N شریک است. با استفاده از الگوریتم اقلیدس می‌توانیم این دو مضرب را به‌سرعت پیدا و به این ترتیب داده را رمزگشایی کنیم. 

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

به این ترتیب الگوریتم شور با حدس درست مضرب‌های N، عملا رمزنگاری‌های کنونی را که بر پایه‌ی ضرب دو عدد اول هستند، بی‌فایده می‌کند. 

برای درک بهتر از طرز کار الگوریتم شور می‌توانید ویدئوی زیر را تماشا کنید. در این ویدئو به کمک این الگوریتم دو مضرب عدد ۳۱۴۱۹۱ به دست می‌آید:

تماشا در یوتیوب

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

اما پیتر شور نشان داد کامپیوتر کوانتومی فرضی می‌تواند یک مسئله‌ی ریاضی حل‌نشدنی را بدون نیاز به انجام محاسبات جداگانه برای مقادیر مختلف، به‌راحتی حل کند؛ و بدین ‌ترتیب کنجکاوی و اشتیاق محققان سراسر جهان را برای ساخت کامپیوترهای کوانتومی برانگیخت. 

اگرچه بسیاری الگوریتم شور را پایانی برای امنیت رمزنگاری RSA و در نتیجه تهدیدی جدی برای بیت‌کوین و دیگر رمزارزها در نظر می‌گیرند، نگرانی برای این موضوع در حال ‌حاضر بسیار زود است.  

مسئله این است که تعامل کیوبیت‌ها با محیط اطراف خود به‌گونه‌ای است که رفتار کوانتومی آن‌ها بعد از مدتی طی فرایندی موسوم به ناهمدوسی کوانتومی (Quantum decoherence) از بین می‌رود. حالت کوانتومی این کیوبیت‌ها به‌شدت آسیب‌پذیر و ناپایدار است و کوچک‌ترین لرزش یا تغییر دما (اختلالاتی که در زبان کوانتوم به آن «نویز» می‌گویند) می‌تواند آن‌ها را قبل از انجام هرگونه محاسبه‌ای از حالت برهم‌نهی خارج کند. 

به همین خاطر است که محققان برای محافظت از کیوبیت‌ها در مقابل اختلالات محیط بیرونی، آن‌ها را در یخچال‌های فوق سرد یا محفظه‌های خلأ قرار می‌دهند. 

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

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

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

نظر شما کاربر زومیت درباره‌ی رایانش کوانتومی و تهدید آن برای امنیت داده‌های رمزنگاری‌شده و رمزارزها چیست؟ آیا توسعه‌ی کیوبیت‌ها سریع‌تر از توسعه‌ی الگوریتم‌‌‌های رمزنگاری پساکوانتومی اتفاق خواهد افتاد؟