১৯৯৪ সালে গণিতবিদ পিটার শোর কম্পিউটার বিজ্ঞান ও বিশ্বের নিরাপত্তা সংস্থাসমূহের ভিত নাড়িয়ে দেন একটি তাত্ত্বিক আবিষ্কারের মাধ্যমে: তিনি প্রমাণ করেন যে একটি কোয়ান্টাম কম্পিউটার পলিনোমিয়াল বা বহুপদী সময়ে বৃহৎ যৌগিক সংখ্যার মৌলিক উৎপাদক বিশ্লেষণ (Prime Factorization) এবং ডিসক্রিট লগারিদম সমাধান করতে সক্ষম। আধুনিক পাবলিক-কী ক্রিপ্টোগ্রাফি—যা HTTPS, অনলাইন ব্যাংকিং, মিলিটারি যোগাযোগ এবং ব্লকচেইনের নিরাপত্তা নিশ্চিত করে—সম্পূর্ণভাবে এই সমস্যাগুলোর ক্ল্যাসিক্যাল সমাধান অসম্ভবতার ওপর প্রতিষ্ঠিত। শোরের অ্যালগরিদম প্রমাণ করেছে যে এই জটিলতা প্রকৃতির পরম নিয়ম নয়, বরং এটি কেবল ক্ল্যাসিক্যাল টুরিং মেশিনের অক্ষমতা।
১. ক্রিপ্টোগ্রাফির ভিত্তি: RSA কেন উৎপাদক বিশ্লেষণের ওপর নির্ভরশীল
জনপ্রিয় RSA ক্রিপ্টোসিস্টেম দুটি অতি বৃহৎ মৌলিক সংখ্যা $p$ এবং $q$-এর গুণফল $N = p cdot q$-এর ওপর ভিত্তি করে কাজ করে। এর এনক্রিপশন সূচক $e$ এবং ডিক্রিপশন সূচক $d$ ইউলারের টশেন্ট ফাংশন $phi(N) = (p-1)(q-1)$-এর সাথে সম্পর্কিত:
[
e cdot d equiv 1 pmod{phi(N)}
]
যদি আক্রমণকারী $N$-কে $p$ ও $q$-এ ভেঙে ফেলতে পারে, তবে কয়েক মাইক্রোসেকেন্ডেই প্রাইভেট কী $d$ উদ্ধার করা সম্ভব। ক্ল্যাসিক্যাল কম্পিউটারের সবচেয়ে শক্তিশালী উৎপাদক বিশ্লেষণ অ্যালগরিদম হলো জেনারেল নাম্বার ফিল্ড সিভ (GNFS), যার সময় জটিলতা সাব-এক্সপোনেনশিয়াল:
[
mathcal{O}left( expleft( c (ln N)^{1/3} (ln ln N)^{2/3} right) right)
]
একটি ২০৪৮-বিট RSA কী ক্ল্যাসিক্যাল সুপারকম্পিউটার ক্লাস্টারে ভাঙতে মহাবিশ্বের বয়সের চেয়েও বেশি সময় প্রয়োজন।
২. সংখ্যাতাত্ত্বিক রূপান্তর: ফ্যাক্টরিং থেকে পর্যায়কাল (Order Finding) নির্ণয়
শোরের মূল বুদ্ধিবৃত্তিক বিপ্লব ছিল এটি দেখানো যে, মৌলিক উৎপাদক বিশ্লেষণ আসলে মডুলার এক্সপোনেনশিয়াল ফাংশনের পর্যায়কাল (Period বা Order) নির্ণয়ের সমতুল্য।
ধরা যাক, আমরা $N$-এর চেয়ে ছোট একটি দৈব সংখ্যা $a$ বেছে নিলাম যেন $gcd(a, N) = 1$ হয়। এবার মডুলার ফাংশনটি বিবেচনা করি:
[
f(x) = a^x bmod N
]
ইউলারের উপপাদ্য অনুযায়ী, এমন একটি ক্ষুদ্রতম ধনাত্মক পূর্ণসংখ্যা $r$ বিদ্যমান থাকবে যার জন্য:
[
a^r equiv 1 pmod N implies a^r – 1 equiv 0 pmod N
]
যদি এই পর্যায়কাল $r$ একটি জোড় সংখ্যা হয়, তবে আমরা একে বর্গের অন্তর সূত্রে ভাঙতে পারি:
[
(a^{r/2} – 1)(a^{r/2} + 1) equiv 0 pmod N
]
এর অর্থ $N$ সংখ্যাটি এই গুণফলকে নিঃশেষে বিভাজ্য করে। যতক্ষণ পর্যন্ত $a^{r/2} notequiv -1 pmod N$ শর্তটি বজায় থাকে (যার সম্ভাবনা অন্তত ৫০%), ততক্ষণ ইউক্লিডীয় অ্যালগরিদম ব্যবহার করে গসাগু বা $gcd$ নির্ণয়ের মাধ্যমে আমরা $N$-এর মৌলিক উৎপাদক পেয়ে যাই:
[
p = gcd(a^{r/2} – 1, N), quad q = gcd(a^{r/2} + 1, N)
]
যেহেতু গসাগু ক্ল্যাসিক্যালি মাত্র $mathcal{O}((log N)^2)$ সময়ে বের করা যায়, তাই সম্পূর্ণ উৎপাদক বিশ্লেষণের কঠিন কাজটি কেবল একটি পর্যায়কাল $r$ খুঁজে পাওয়ার ওপর নির্ভরশীল হয়ে পড়ে।
৩. কোয়ান্টাম অর্ডার-ফাইন্ডিং সাবরুটিন
ক্ল্যাসিক্যালি $a^x bmod N$-এর পর্যায়কাল $r$ বের করতে এক্সপোনেনশিয়াল সংখ্যক মান পরীক্ষা করতে হয়। কিন্তু কোয়ান্টাম সুপারপজিশন এবং কোয়ান্টাম ফুরিয়ার রূপান্তরের মাধ্যমে শোরের অ্যালগরিদম পলিনোমিয়াল ধাপে এটি সমাধান করে।
অ্যালগরিদমের প্রধান ধাপসমূহ:
- রেজিস্টার প্রস্তুতি: দুটি কোয়ান্টাম রেজিস্টার তৈরি করা হয়—কাউন্টিং রেজিস্টার ১ ($t approx 2 log_2 N$ কিউবিট) এবং টার্গেট রেজিস্টার ২ ($log_2 N$ কিউবিট)।
- সুপারপজিশন ও মডুলার এক্সপোনেনশিয়েশন: রেজিস্টার ১-এ হ্যাডামার্ড গেট প্রয়োগ করে সকল সম্ভাব্য $x$-এর সুপারপজিশন তৈরি করা হয় এবং কোয়ান্টাম সার্কিট $U_a |xrangle |yrangle = |xrangle |y cdot a^x bmod Nrangle$ প্রয়োগ করা হয়:
[
|psirangle = frac{1}{sqrt{2^t}} sum_{x=0}^{2^t-1} |xrangle |a^x bmod Nrangle
] - টার্গেট রেজিস্টার মেজারমেন্ট: টার্গেট রেজিস্টার পরিমাপ করলে এটি একটি নির্দিষ্ট মান $y_0$ দেখায়, যার ফলে রেজিস্টার ১ ঠিক $r$ ব্যবধানে সাজানো স্টেটসমূহের সুপারপজিশনে কলাপ্স করে:
[
|psi_{text{collapsed}}rangle = frac{1}{sqrt{m}} sum_{j} |x_0 + j cdot rrangle
] - ইনভার্স কোয়ান্টাম ফুরিয়ার ট্রান্সফর্ম ($text{QFT}^dagger$): এই পর্যায়ক্রমিক স্টেটের ওপর $text{QFT}^dagger$ প্রয়োগ করলে পর্যায়কাল $r$-এর কারণে ইন্টারফারেন্স ঘটে এবং ফ্রিকোয়েন্সি স্পেসে সুনির্দিষ্ট চূড়া (peaks) তৈরি হয়:
[
|psi_{text{final}}rangle = frac{1}{sqrt{r}} sum_{s=0}^{r-1} left| frac{s cdot 2^t}{r} rightrangle
] - কন্টিনিউড ফ্র্যাকশন অ্যালগরিদম: রেজিস্টার ১ পরিমাপ করে প্রাপ্ত মান থেকে ক্ল্যাসিক্যাল কন্টিনিউড ফ্র্যাকশন বা আবৃত্ত ভগ্নাংশ অ্যালগরিদমের মাধ্যমে অতি দ্রুত সঠিক হর $r$ উদ্ধার করা হয়।
- ক্ল্যাসিক্যাল GNFS: $mathcal{O}left(e^{c (ln N)^{1/3} (ln ln N)^{2/3}}right)$ — ২০৪৮-বিট RSA ভাঙতে কোটি কোটি বছর।
- শোরের অ্যালগরিদম: $widetilde{mathcal{O}}((log N)^2)$ বা সর্বোচ্চ $mathcal{O}(n^3)$ — একটি ফল্ট-টলারেন্ট কোয়ান্টাম প্রসেসরে মাত্র কয়েক মিনিট থেকে ঘণ্টা!
৪. পোস্ট-কোয়ান্টাম ক্রিপ্টোগ্রাফির যুগ
যেহেতু শোরের অ্যালগরিদম উপবৃত্তাকার বক্ররেখা ক্রিপ্টোগ্রাফিকেও (ECC) ভেঙে ফেলে, তাই আধুনিক বিশ্বের সাইবার নিরাপত্তা বজায় রাখতে NIST-এর নেতৃত্বে পোস্ট-কোয়ান্টাম ক্রিপ্টোগ্রাফি (PQC) স্ট্যান্ডার্ড চালু করা হয়েছে। এতে ল্যাটিস-ভিত্তিক ক্রিপ্টোগ্রাফি (Kyber, Dilithium) ব্যবহৃত হচ্ছে যা কোয়ান্টাম আক্রমণ প্রতিরোধে সক্ষম।
