पूर्णांक गुणनखंडन

"Prime decomposition" redirects here. For the prime decomposition theorem for 3-manifolds, see Prime decomposition (3-manifold).

Unsolved problem in computer science:

Can integer factorization be solved in polynomial time on a classical computer?

(more unsolved problems in computer science)

संख्या सिद्धांत में, पूर्णांक गुणनखंड एक समग्र संख्या का छोटे पूर्णांकों के उत्पाद (गणित) में अपघटन है। यदि ये विभाजक आगे अभाज्य संख्याओं तक सीमित हैं, तो प्रक्रिया को अभाज्य गुणनखंडन कहा जाता है।

जब संख्याएँ पर्याप्त रूप से बड़ी होती हैं, तो कोई कुशल एक कंप्यूटर जितना | गैर-क्वांटम पूर्णांक गुणनखंड एल्गोरिथ्म ज्ञात नहीं होता है। हालाँकि, यह सिद्ध नहीं हुआ है कि ऐसा कलन विधि मौजूद नहीं है। आरएसए (क्रिप्टोसिस्टम) | आरएसए पब्लिक-की एन्क्रिप्शन और डिजिटल हस्ताक्षर एल्गोरिथम जैसे क्रिप्टोग्राफी में उपयोग किए जाने वाले एल्गोरिदम के लिए इस समस्या की अनुमानित कम्प्यूटेशनल कठोरता धारणा महत्वपूर्ण है। गणित और कंप्यूटर विज्ञान के कई क्षेत्रों को समस्या पर ध्यान देने के लिए लाया गया है, जिसमें अण्डाकार वक्र, बीजगणितीय संख्या सिद्धांत और क्वांटम कंप्यूटर शामिल हैं।

2019 में, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé और Paul Zimmermann ने लगभग 900 कोर-वर्ष की कंप्यूटिंग शक्ति का उपयोग करते हुए 240-अंक (795-बिट) संख्या (RSA-240) बनाई। शोधकर्ताओं ने अनुमान लगाया कि 1024-बिट आरएसए मापांक लगभग 500 गुना अधिक समय लेगा। दी गई लंबाई की सभी संख्याएँ समान रूप से गुणनखंड करने में कठिन नहीं होती हैं। इन समस्याओं के सबसे कठिन उदाहरण (वर्तमान में ज्ञात तकनीकों के लिए) semiprime हैं, जो दो अभाज्य संख्याओं का गुणनफल है। जब वे दोनों बड़े होते हैं, उदाहरण के लिए दो हजार अंश से अधिक लंबे, बेतरतीब ढंग से चुने गए, और लगभग एक ही आकार के (लेकिन बहुत करीब नहीं, उदाहरण के लिए, फ़र्मेट के गुणनखंडन विधि द्वारा कुशल गुणन से बचने के लिए), यहां तक ​​​​कि सबसे तेज़ प्राइम फ़ैक्टराइज़ेशन एल्गोरिदम सबसे तेज कंप्यूटर खोज को अव्यावहारिक बनाने के लिए पर्याप्त समय ले सकते हैं; अर्थात्, जैसे-जैसे पूर्णांक के अंकों की संख्या बढ़ती जाती है, वैसे-वैसे किसी भी कंप्यूटर पर गुणनखंड करने के लिए आवश्यक संचालन की संख्या में भारी वृद्धि होती है।

कई क्रिप्टोग्राफ़िक प्रोटोकॉल बड़े समग्र पूर्णांकों या संबंधित समस्या के फैक्टरिंग की कठिनाई पर आधारित होते हैं - उदाहरण के लिए, RSA समस्या। एक एल्गोरिद्म जो किसी मनमाने पूर्णांक को प्रभावी ढंग से कारक बनाता है, वह RSA (एल्गोरिदम) आधारित सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी को असुरक्षित बना देगा।

प्रधान अपघटन

n का अभाज्य अपघटन = 864 as 2⁵ × 3³

अंकगणित के मूलभूत प्रमेय के अनुसार, प्रत्येक धनात्मक पूर्णांक का एक अद्वितीय अभाज्य गुणनखण्ड होता है। (परंपरा के अनुसार, 1 खाली गुणनफल है।) प्रधानता परीक्षण क्या पूर्णांक प्राइम है, बहुपद समय में किया जा सकता है, उदाहरण के लिए, एकेएस प्रारंभिक परीक्षण द्वारा। यदि समग्र, हालांकि, बहुपद समय परीक्षण कारक प्राप्त करने के तरीके में कोई अंतर्दृष्टि नहीं देते हैं।

पूर्णांक फ़ैक्टराइज़ेशन के लिए एक सामान्य एल्गोरिथ्म को देखते हुए, किसी भी पूर्णांक को इस एल्गोरिथम के बार-बार उपयोग से उसके घटक प्रमुख कारकों में फ़ैक्टर किया जा सकता है। स्थिति विशेष-उद्देश्य गुणनखंड एल्गोरिदम के साथ अधिक जटिल है, जिनके लाभों को अपघटन के दौरान उत्पन्न कारकों के साथ भी या बिल्कुल भी महसूस नहीं किया जा सकता है। उदाहरण के लिए, अगर n = 171 × p × q कहाँ p < q बहुत बड़ी अभाज्य संख्याएँ हैं, परीक्षण प्रभाग शीघ्रता से गुणनखंड 3 और 19 उत्पन्न करेगा लेकिन अगला गुणनखंड ज्ञात करने के लिए p विभाजन लेगा। एक विपरीत उदाहरण के रूप में, यदि n 13729, 1372933, और 18848997161 अभाज्य संख्याओं का गुणनफल है, जहां 13729 × 1372933 = 18848997157, Fermat की गुणनखंडन विधि से शुरू होगी $\left\lceil {\sqrt {n}}\right\rceil =18848997159$ जो तुरंत फल देता है ${\textstyle b={\sqrt {a^{2}-n}}={\sqrt {4}}=2b}$ और इसलिए कारक a − b = 18848997157 और a + b = 18848997161. जबकि इन्हें आसानी से क्रमशः मिश्रित और अभाज्य के रूप में पहचाना जाता है, फ़र्मेट की विधि समग्र संख्या को कारक बनाने में अधिक समय लेगी क्योंकि प्रारंभिक मान ${\textstyle \left\lceil {\sqrt {18848997157}}\,\right\rceil =137292}$ for a 1372933 के आसपास कहीं नहीं है।

कला की वर्तमान स्थिति

See also: Integer factorization records

बी-बिट नंबरों में, मौजूदा एल्गोरिदम का उपयोग करने के अभ्यास में कारक के लिए सबसे कठिन वे हैं जो समान आकार के दो प्राइम के उत्पाद हैं। इस कारण से, ये क्रिप्टोग्राफ़िक अनुप्रयोगों में उपयोग किए जाने वाले पूर्णांक हैं। फरवरी 2020 में इस तरह का सबसे बड़ा सेमीप्राइम आरएसए संख्या #RSA-250|RSA-250, 250 दशमलव अंकों के साथ एक 829-बिट संख्या थी। इंटेल स्काईलेक (माइक्रोआर्किटेक्चर) का उपयोग करके कुल गणना समय लगभग 2700 कोर-वर्ष कंप्यूटिंग था। #Xeon Gold (क्वाड प्रोसेसर) 6130 2.1 GHz पर। हाल के सभी गुणनखंडन रिकॉर्डों की तरह, यह गुणनखंडन सैकड़ों मशीनों पर चलने वाली सामान्य संख्या फ़ील्ड छलनी के अत्यधिक अनुकूलित कार्यान्वयन के साथ पूरा हुआ।

कठिनाई और जटिलता

कोई एल्गोरिदम प्रकाशित नहीं किया गया है जो सभी पूर्णांकों को बहुपद समय में गुणनखंडित कर सकता है, अर्थात, जो समय में बिग ओ अंकन में बी-बिट संख्या n को कारक बना सकता है (बी^k) कुछ स्थिर k के लिए। इस तरह के एल्गोरिदम का न तो अस्तित्व है और न ही गैर-अस्तित्व साबित हुआ है, लेकिन आम तौर पर यह संदेह है कि वे मौजूद नहीं हैं और इसलिए यह समस्या कक्षा पी में नहीं है। समस्या स्पष्ट रूप से कक्षा एनपी में है, लेकिन आम तौर पर यह संदेह है कि यह एनपी-पूर्ण नहीं है, हालांकि यह सिद्ध नहीं हुआ है। ऐसे प्रकाशित एल्गोरिदम हैं जो O((1 + ε) से तेज़ हैं^b) सभी सकारात्मक ε के लिए, यानी समय जटिलता#उप-घातीय समय|उप-घातीय। As of 2022सबसे अच्छा सैद्धांतिक असिम्प्टोटिक रनिंग टाइम वाला एल्गोरिदम सामान्य संख्या क्षेत्र छलनी (जीएनएफएस) है, जिसे पहली बार 1993 में प्रकाशित किया गया था। समय में बी-बिट नंबर एन पर चल रहा है:

$\exp \left(\left({\sqrt[{3}]{\frac {64}{9}}}+o(1)\right)(\ln n)^{\frac {1}{3}}(\ln \ln n)^{\frac {2}{3}}\right).$

वर्तमान कंप्यूटरों के लिए, GNFS बड़े n (लगभग 400 बिट्स से अधिक) के लिए सबसे अच्छा प्रकाशित एल्गोरिथम है। हालाँकि, क्वांटम कम्प्यूटिंग के लिए, पीटर शोर ने 1994 में एक एल्गोरिथ्म की खोज की जो इसे बहुपद समय में हल करता है। यदि क्वांटम संगणना स्केलेबल हो जाती है तो क्रिप्टोग्राफी के लिए इसका महत्वपूर्ण प्रभाव पड़ेगा। शोर का एल्गोरिदम केवल ओ लेता है (बी³) बी-बिट संख्या इनपुट पर समय और O(b) स्थान। 2001 में, शोर के एल्गोरिदम को पहली बार 7 क्विबिट प्रदान करने वाले अणुओं पर परमाणु चुंबकीय अनुनाद तकनीकों का उपयोग करके लागू किया गया था। यह ज्ञात नहीं है कि किस जटिलता वर्ग में पूर्णांक गुणनखंडन समस्या की निर्णय समस्या होती है (अर्थात: करता है n से छोटा कारक है k?)। यह एनपी (जटिलता) और सह-एनपी दोनों में जाना जाता है, जिसका अर्थ है कि बहुपद समय में हां और ना दोनों उत्तरों को सत्यापित किया जा सकता है। हाँ के उत्तर को गुणनखंड प्रदर्शित करके प्रमाणित किया जा सकता है n = d(n/d) साथ d ≤ k. नहीं के उत्तर को अलग-अलग अभाज्य संख्याओं में n के गुणनखंडन को प्रदर्शित करके प्रमाणित किया जा सकता है, सभी k से बड़े; कोई एकेएस प्रारंभिक परीक्षण का उपयोग करके उनकी प्रारंभिकता को सत्यापित कर सकता है, और फिर उन्हें n प्राप्त करने के लिए गुणा कर सकता है। अंकगणित का मौलिक प्रमेय यह गारंटी देता है कि बढ़ती हुई प्राइम्स की केवल एक ही संभावित स्ट्रिंग है जिसे स्वीकार किया जाएगा, जो दर्शाता है कि समस्या यूपी (जटिलता) और सह-यूपी दोनों में है। शोर के एल्गोरिदम के कारण यह बीक्यूपी में जाना जाता है।

समस्या जटिलता वर्गों पी, एनपी-पूर्ण, और सह-एनपी-पूर्ण तीनों के बाहर होने का संदेह है। इसलिए यह एनपी-मध्यवर्ती जटिलता वर्ग के लिए एक उम्मीदवार है। अगर यह एनपी-पूर्ण या सह-एनपी-पूर्ण साबित हो सकता है, तो यह एनपी = सह-एनपी, एक बहुत ही आश्चर्यजनक परिणाम होगा, और इसलिए इन दोनों वर्गों के बाहर होने के लिए पूर्णांक कारक व्यापक रूप से संदेह है।

इसके विपरीत, निर्णय समस्या क्या n एक समग्र संख्या है? (या समतुल्य: क्या n एक अभाज्य संख्या है? ) n के गुणनखंडों को निर्दिष्ट करने की समस्या से कहीं अधिक आसान प्रतीत होती है। एकेएस प्राइमलिटी टेस्ट के साथ बहुपद समय (एन के अंकों की संख्या बी में) में समग्र / मुख्य समस्या को हल किया जा सकता है। इसके अलावा, कई यादृच्छिक एल्गोरिदम हैं जो अभ्यास में बहुत जल्दी परीक्षण कर सकते हैं यदि कोई त्रुटि की एक छोटी सी संभावना को स्वीकार करने के लिए तैयार है। प्रारंभिक परीक्षण में आसानी आरएसए (एल्गोरिदम) एल्गोरिथम का एक महत्वपूर्ण हिस्सा है, क्योंकि इसके साथ शुरू करने के लिए बड़ी अभाज्य संख्याओं को खोजना आवश्यक है।

फैक्टरिंग एल्गोरिदम

विशेष-उद्देश्य

एक विशेष-उद्देश्य फैक्टरिंग एल्गोरिदम का रनिंग टाइम फैक्टरिंग की जाने वाली संख्या के गुणों पर या उसके अज्ञात कारकों में से किसी एक पर निर्भर करता है: आकार, विशेष रूप, आदि। चलने का समय निर्धारित करने वाले पैरामीटर एल्गोरिदम के बीच भिन्न होते हैं।

विशेष-उद्देश्य फैक्टरिंग एल्गोरिदम का एक महत्वपूर्ण उपवर्ग श्रेणी 1 या प्रथम श्रेणी एल्गोरिदम है, जिसका चलने का समय सबसे छोटे प्रमुख कारक के आकार पर निर्भर करता है। अज्ञात रूप के एक पूर्णांक को देखते हुए, इन विधियों को आम तौर पर छोटे कारकों को हटाने के लिए सामान्य प्रयोजन के तरीकों से पहले लागू किया जाता है। उदाहरण के लिए, भोली ट्रायल डिवीजन एक श्रेणी 1 एल्गोरिथम है।

• ट्रायल डिवीजन
• व्हील फैक्टराइजेशन
• पोलार्ड का आरओ एल्गोरिद्म, जिसमें चक्र का पता लगाना के दो सामान्य फ्लेवर हैं: एक फ़्लॉइड द्वारा और दूसरा ब्रेंट द्वारा।
• बीजगणितीय-समूह गुणनखंड एल्गोरिद्म|बीजगणितीय-समूह गुणनखंड एल्गोरिथम, जिनमें पोलार्ड का p - 1 एल्गोरिद्म है| पोलार्ड का p − 1 एल्गोरिथम, विलियम्स का p + 1 एल्गोरिद्म|विलियम्स का p + 1 एल्गोरिद्म, और लेनस्ट्रा अण्डाकार वक्र गुणनखंड
• फर्मेट की कारककरण विधि
• यूलर की कारककरण विधि
• विशेष संख्या क्षेत्र छलनी

सामान्य-उद्देश्य

एक सामान्य-उद्देश्य फैक्टरिंग एल्गोरिथम, जिसे श्रेणी 2, द्वितीय श्रेणी, या मौरिस क्रैचिक परिवार एल्गोरिथम के रूप में भी जाना जाता है,चलने का समय होता है जो पूरी तरह से पूर्णांक के आकार पर निर्भर करता है। यह एक प्रकार का एल्गोरिथम है जिसका उपयोग RSA संख्याओं को गुणनखंड करने के लिए किया जाता है। अधिकांश सामान्य-उद्देश्य वाले फैक्टरिंग एल्गोरिदम वर्ग विधि की सर्वांगसमता पर आधारित होते हैं।

• डिक्सन का एल्गोरिदम
• निरंतर अंश गुणनखंडन (CFRAC)
• द्विघात चलनी
• तर्कसंगत छलनी
• सामान्य संख्या क्षेत्र छलनी
• शैंक्स का वर्ग गुणनखंड बनाता है (SQUFOF)

अन्य उल्लेखनीय एल्गोरिदम

• शोर का एल्गोरिदम, क्वांटम कंप्यूटर के लिए

ह्यूरिस्टिक रनिंग टाइम

संख्या सिद्धांत में, कई पूर्णांक फैक्टरिंग एल्गोरिदम हैं जो कि अनुमानित रूप से समय की जटिलता की अपेक्षा करते हैं

$L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}$

बिग ओ नोटेशन में|लिटिल-ओ और एएल अंकन। उन एल्गोरिदम के कुछ उदाहरण दीर्घवृत्तीय वक्र विधि और द्विघात छलनी हैं। ऐसा ही एक अन्य एल्गोरिथम Schnorr द्वारा प्रस्तावित वर्ग समूह संबंध विधि है, सेसेन, और लेनस्ट्रा, जिसे उन्होंने केवल अप्रमाणित सामान्यीकृत रीमैन परिकल्पना | सामान्यीकृत रीमैन परिकल्पना (जीआरएच) मानते हुए सिद्ध किया।

कठोर चलने का समय

Schnorr-Seysen-Lenstra संभाव्य एल्गोरिथम को Lenstra और Pomerance द्वारा कठोरता से सिद्ध किया गया हैचलने के समय की उम्मीद है $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$ मल्टीप्लायरों के उपयोग के साथ जीआरएच धारणा को बदलकर। एल्गोरिथम द्विघात रूप के विविक्तकर के धनात्मक द्विआधारी द्विघात रूपों के आदर्श वर्ग समूह का उपयोग करता है Δ जिसे G द्वारा निरूपित किया जाता है_Δ. जी_Δ पूर्णांकों (a, b, c) के त्रिगुणों का समुच्चय है जिसमें वे पूर्णांक सापेक्ष प्रधान होते हैं।

स्चनोर-सेसेन-लेनस्ट्रा एल्गोरिथम

एक पूर्णांक n दिया गया है जिसका गुणनखंड किया जाएगा, जहाँ n एक निश्चित स्थिरांक से बड़ा एक विषम धनात्मक पूर्णांक है। इस फैक्टरिंग एल्गोरिथम में विवेचक Δ को n के गुणक के रूप में चुना जाता है, Δ = −dn, जहाँ d कोई धनात्मक गुणक है। एल्गोरिदम उम्मीद करता है कि एक डी के लिए जी में पर्याप्त चिकनी संख्या रूप मौजूद हैं_Δ. लेनस्ट्रा और पोमेरेन्स दिखाते हैं कि चिकनी परिणाम की गारंटी के लिए डी की पसंद को एक छोटे से सेट तक सीमित किया जा सकता है।

पी द्वारा निरूपित करें_Δ क्रोनकर प्रतीक के साथ सभी प्राइम क्यू का सेट $\left({\tfrac {\Delta }{q}}\right)=1$. G के एक समूह के जनरेटिंग सेट का निर्माण करके_Δ और अभाज्य रूप च_q जी का_Δ पी में क्यू के साथ_Δ जनरेटर और f के सेट के बीच संबंधों का एक क्रम_q उत्पादित है। क्यू के आकार से घिरा जा सकता है $c_{0}(\log |\Delta |)^{2}$ कुछ स्थिर के लिए $c_{0}$.

जिस संबंध का उपयोग किया जाएगा वह शक्तियों के गुणनफल के बीच का संबंध है जो G के समूह (गणित) के बराबर है_Δ. इन संबंधों का उपयोग जी के तथाकथित अस्पष्ट रूप के निर्माण के लिए किया जाएगा_Δ, जो जी का एक तत्व है_Δ Δ के संबंधित गुणनखंड की गणना करके और एक महानतम सामान्य विभाजक लेकर, यह अस्पष्ट रूप n का पूर्ण अभाज्य गुणनखंड प्रदान करता है। इस एल्गोरिथ्म में ये मुख्य चरण हैं:

मान लें कि गुणनखंड की जाने वाली संख्या n है।

1. चलो Δ के साथ एक नकारात्मक पूर्णांक हो Δ = −dn, जहाँ d एक गुणक है और Δ किसी द्विघात रूप का ऋणात्मक विविक्तकर है।
2. पहले अभाज्य संख्याओं को लें $p_{1}=2,p_{2}=3,p_{3}=5,\ldots ,p_{t}$, कुछ के लिए $t\in {\mathbb {N} }$.
3. होने देना $f_{q}$ G का एक यादृच्छिक अभाज्य रूप हो_Δ साथ ${\textstyle \left({\frac {\Delta }{q}}\right)=1}$.
4. G का जनरेटिंग सेट X खोजें_Δ
5. सेट X और के बीच संबंधों का एक क्रम लीजिए {f_q : q ∈ P_Δ} संतुष्टि देने वाला: ${\textstyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$
6. एक अस्पष्ट रूप का निर्माण करें $(a,b,c)$ वह एक तत्व f ∈ G है_Δ Δ के सबसे बड़े विषम भाजक का सहअभाज्य गुणनखंड प्राप्त करने के लिए 2 को विभाजित करने के क्रम में $\Delta =-4ac{\text{ or }}a(a-4c){\text{ or }}(b-2a)(b+2a)$
7. यदि अस्पष्ट रूप n का गुणनखंड प्रदान करता है तो रुकें, अन्यथा n का गुणनखंड मिलने तक एक और अस्पष्ट रूप खोजें। बेकार अस्पष्ट रूपों को उत्पन्न होने से रोकने के लिए, साइलो प्रमेयों का निर्माण करें|2-साइलो समूह Sll₂(Δ) जी (Δ) का।

किसी भी सकारात्मक पूर्णांक को फैक्टर करने के लिए एक एल्गोरिथ्म प्राप्त करने के लिए, इस एल्गोरिथम में कुछ चरणों को जोड़ना आवश्यक है जैसे कि ट्रायल डिवीजन और एडलमैन-पोमेरेंस-रूमली प्राइमलिटी टेस्ट।

अपेक्षित चलने का समय

जैसा कि कहा गया है कि एल्गोरिथ्म एक संभाव्य एल्गोरिथम है क्योंकि यह यादृच्छिक विकल्प बनाता है। इसका अपेक्षित चलने का समय अधिकतम है $L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]$.

यह भी देखें

• ऑरिफ्यूइलियन कारककरण
• उनके गुणनखंडों के साथ यादृच्छिक संख्या उत्पन्न करने के लिए बाख का एल्गोरिथ्म
• एक सकारात्मक पूर्णांक का विहित प्रतिनिधित्व
• गुणनखंडन
• गुणक विभाजन
• पी-एडिक वैल्यूएशन|$p$-एडिक वैल्यूएशन
• विभाजन (संख्या सिद्धांत) - सकारात्मक पूर्णांकों के योग के रूप में संख्या लिखने का एक तरीका।

संदर्भ

• Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective. Springer. ISBN 0-387-94777-9. Chapter 5: Exponential Factoring Algorithms, pp. 191–226. Chapter 6: Subexponential Factoring Algorithms, pp. 227–284. Section 7.4: Elliptic curve method, pp. 301–313.
• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.4: Factoring into Primes, pp. 379–417.
• Samuel S. Wagstaff Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3..
• Warren, Henry S. Jr. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.

बाहरी संबंध

• msieve - SIQS and NFS - has helped complete some of the largest public factorizations known
• Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", Computing and Combinatorics", 2000, pp. 3–22. download
• Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160(2): 781-793 (2004). August 2005 version PDF
• Eric W. Weisstein, “RSA-640 Factored” MathWorld Headline News, November 8, 2005
• Dario Alpern's Integer factorization calculator - A web app for factoring large integers