मैं सिर्फ कंप्यूटर विज्ञान का एक शुरुआत कर रहा हूं। मैंने समय चलने के बारे में कुछ सीखा लेकिन मुझे यकीन नहीं है कि जो मैंने समझा वह सही है। तो कृपया मेरी मदद करो।पूर्णांक कारक एक गैर-बहुपद समय क्यों है?
तो पूर्णांक कारककरण वर्तमान में बहुपद समय की समस्या नहीं है लेकिन प्रारंभिक परीक्षण है। मान लें कि चेक करने की संख्या एन है। यदि हम यह तय करने के लिए एक प्रोग्राम चलाते हैं कि 1 से sqrt (n) से प्रत्येक नंबर एन को विभाजित कर सकता है, और यदि उत्तर हाँ है, तो संख्या को स्टोर करें। मुझे लगता है कि यह कार्यक्रम बहुपद समय है, है ना?
एक संभावित तरीका है कि मैं गलत हूं, एक कारक कार्यक्रम को पहले प्राइम की खोज के बजाय सभी प्राइम ढूंढना चाहिए। तो शायद यही कारण है।
हालांकि, सार्वजनिक कुंजी क्रिप्टोग्राफी में, क्रिप्टोग्राफी पर हमला करने के लिए बड़ी संख्या का एक प्रमुख कारक खोजना आवश्यक है। चूंकि आम तौर पर एक बड़ी संख्या (सार्वजनिक कुंजी) केवल दो प्राइम का उत्पाद है, एक प्राइम ढूंढना मतलब दूसरे को ढूंढना है। यह बहुपद समय होना चाहिए। तो हमला करना मुश्किल या असंभव क्यों है?
आपने जो कहा था वह जांच रहा है कि संख्या प्रमुख है या नहीं। – Emil
क्योंकि संख्याएं बड़ी हैं! – nullpotent
यदि आपको लगता है कि एल्गोरिदम एक्स में बहुपद जटिलता है, तो बहुपद लिखने का प्रयास करें जो इसकी जटिलता व्यक्त करता है। यदि आप सफल होते हैं तो एक्स में बहुपद जटिलता होती है, यदि आप असफल होते हैं तो आप इस विचार के साथ स्वयं को सांत्वना देना चाहेंगे कि एक्स में बहुपद जटिलता नहीं है, जो इस विचार से अधिक आरामदायक होगा कि आप (या एक) बहुपद को खोजने में विफल रहे हैं। लेकिन, अधिक गंभीरता से, पूर्णांक में अंकों की संख्या के संदर्भ में पूर्णांक कारककरण की जटिलता के लिए समीकरण लिखने का प्रयास करें और इसके रूप का अध्ययन करें। –