किसी दिए गए नंबर के लिए (हम जानते हैं कि एन = पी^ए * क्यू^बी, कुछ प्राइम नंबर पी, क्यू और कुछ पूर्णांक ए, बी) और एक दिया गया नंबर φ (एन) (http://en.wikipedia.org/wiki/Euler%27s_totient_function) पी, क्यू, ए और बी खोजें।फास्ट फैक्टरलाइजेशन
पकड़ यह है कि एन, और φ (एन) के बारे में 200 अंक हैं इसलिए एल्गोरिदम बहुत तेज होना चाहिए। यह बहुत कठिन समस्या प्रतीत होता है और मैं पूरी तरह से नहीं जानता कि φ (एन) का उपयोग कैसे करें।
इस तक कैसे पहुंचे?
n = p^a * q^b के लिए, कुल φ(n) = (p-1)*p^(a-1) * (q-1)*q^(b-1) है। सामान्यता के नुकसान के बिना, p < q।
तो gcd(n,φ(n)) = p^(a-1) * q^(b-1) अगर pq-1 और gcd(n,φ(n)) = p^a * q^(b-1) विभाजित नहीं होता है, तो p बिताते हैं q-1।
पहले मामले में, हम n/gcd(n,φ(n)) = p*q और φ(n)/gcd(n,φ(n)) = (p-1)*(q-1) = p*q + 1 - (p+q) है, इस प्रकार आप x = p*q = n/gcd(n,φ(n)) और y = p+q = n/gcd(n,φ(n)) + 1 - φ(n)/gcd(n,φ(n)) है। फिर p और q ढूंढना आसान है: y^2 - 4*x = (q-p)^2, इसलिए q = (y + sqrt(y^2 - 4*x))/2, और p = y-q। फिर एक्सपोनेंट्स a और b ढूंढना मामूली है।
दूसरे मामले में, n/gcd(n,φ(n)) = q। तब आप आसानी से एक्सपोनेंट b पा सकते हैं, q द्वारा विभाजित होने तक विभाजन शेष छोड़ देता है, और इस प्रकार p^a प्राप्त करता है। φ(n)(q-1)*q^(b-1) द्वारा विभाजित z = (p-1)*p^(a-1) देता है। फिर p^a - z = p^(a-1) और p = p^a/(p^a-z)। एक्सपोनेंट a ढूँढना फिर से छोटा है।
तो यह तय करना बाकी है कि आपके पास कौन सा मामला है। आपके पास केस 2 है यदि केवल n/gcd(n,φ(n)) एक प्रमुख है।
इसके लिए, आपको एक सभ्य प्राथमिकता परीक्षण की आवश्यकता है। या आप पहले मान सकते हैं कि आपके पास केस 1 है, और यदि यह काम नहीं करता है, तो निष्कर्ष निकालें कि आपके पास 2 मामला है।
क्या काम करने का प्रयास करें n/(n - φ (n)) है।
अप का पालन करें:
n/(एन - φ (एन)) = pq। आप सिर्फ पीके द्वारा विभाजित करते रहें।
यह सही नहीं है। 'φ (6) = 2',' 6 - φ (6) = 4' भी विभाजित नहीं करता है 6. –
मैं गणना करता हूं कि 'n/(n - φ (n)) = pq/(q + p-1) '। मुझे लगता है कि यह इतना बुनियादी नहीं है। –
@ ब्लूराजा-डैनीफ्लूघोफ्ट, ठीक है यह काम करता है। यह दिलचस्प है, कोई सुझाव यह क्यों काम करता है, इस सूत्र को कैसे कम किया जाए? – xan
+1 आपने यह कैसे किया है –
असल में, आपको कुल के लिए सूत्र जानने की आवश्यकता है, और आप 'पी * क्यू' और' पी + क्यू 'खोजना चाहते हैं। तब से, जब तक वांछित परिणाम निकलता है तब तक आप सामग्री को तब तक घुमाएं। –
इसके अलावा केस 3: 'gcd (n, φ (n)) = p^(a-1) * q^b' –