Shor का एल्गोरिदम

Shor का एल्गोरिदम, जिसे Peter Shor ने 1994 में विकसित किया, क्वांटम कंप्यूटरों का उपयोग करके एक पूर्णांक N को बहुपद समय O((log N)³) में गुणनखंडित कर सकता है। सर्वोत्तम ज्ञात शास्त्रीय एल्गोरिदम (सामान्य संख्या क्षेत्र छलनी) उप-घातांकीय समय में चलता है। यह महत्वपूर्ण है क्योंकि RSA एन्क्रिप्शन बड़ी संख्याओं को गुणनखंडित करने की कठिनाई पर निर्भर करता है। Shor का एल्गोरिदम एक मॉड्यूलर घातांकीय फ़ंक्शन की अवधि खोजने के लिए Quantum Fourier Transform का उपयोग करता है। जबकि एल्गोरिदम सैद्धांतिक रूप से शक्तिशाली है, RSA-2048 को तोड़ने के लिए इसे वास्तविक हार्डवेयर पर चलाने के लिए लाखों त्रुटि-सुधारित क्यूबिट की आवश्यकता होगी — वर्तमान NISQ क्षमताओं (जिनमें अधिकतम ~1000 शोरयुक्त क्यूबिट होते हैं) से कहीं आगे। Shor का एल्गोरिदम क्वांटम-पश्चात क्रिप्टोग्राफी अनुसंधान और NIST के क्वांटम-पश्चात क्रिप्टोग्राफी मानकीकरण प्रयास की प्राथमिक प्रेरणा है।