फ़र्मेट की गुणनखंडन विधि

फ़र्मेट की गुणनखंडन विधि, जिसका नाम पियरे डी फ़र्मेट के नाम पर रखा गया है, दो वर्गों के अंतर के रूप में एक सम और विषम संख्या पूर्णांक के प्रतिनिधित्व पर आधारित होती है:

$N=a^{2}-b^{2}.$

वह अंतर बीजगणितीय रूप से गुणनखंडनीय $(a+b)(a-b)$ होता है; यदि कोई भी कारक एक के समान्तर नहीं होता है, तो यह N का उचित गुणनखंड होता है।

प्रत्येक विषम संख्या का एक ऐसा प्रतिनिधित्व होता है। वास्तव में, यदि $N=cd$ होता है तो, यह N का एक गुणनखंड होता है

$N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{2}$

चूँकि N विषम होता है, तो c और d भी विषम होता हैं, इसलिए वे आधे पूर्णांक होते हैं। (चार का गुणज भी वर्गों का अंतर होता है: मान लीजिए कि c और d सम हैं।)

अपने सरलतम रूप में, फ़र्मेट की विधि परीक्षण प्रभाग (सबसे अनुपयुक्त स्थिति) से भी धीमी हो सकती है। यघपि, परीक्षण प्रभाग और फ़र्मेट का संयोजन किसी की तुलना में अधिक प्रभावी होते है।

मूल विधि

कोई व्यक्ति a के विभिन्न मूल्यों की जांच करता है यह आशा करते हुए $a^{2}-N=b^{2}$ होता है, एक वर्ग। फॉर्म फ़ैक्टर(AND): // N विषम a ← होना चाहिए ceiling(sqrt(N))

    फॉर्म फ़ैक्टर(N): // N विषम होना चाहिए

    a ← सीलिंग(sqrt(N))
    b2 ← a*a - N
   तब तक दोहराएँ जब तक b2 एक वर्ग न हो जाए:
        a ← a + 1
        b2 ← a*a - N 
     // समान रूप से: 
     // b2 ← b2 + 2*a + 1 
     // a ← a + 1
    रीटर्न a - sqrt(b2) // or a + sqrt(b2)

उदाहरण के लिए, कारक के लिए $N=5959$, a के लिए पहला प्रयास 5959 का वर्गमूल है जिसे अगले पूर्णांक तक पूर्णांकित किया जाता है, जिसका मान 78 होता है। तब, $b^{2}=78^{2}-5959=125$ होता है। चूँकि 125 एक वर्ग नहीं होता है, इसलिए a का मान 1 बढ़ाकर दूसरा प्रयास किया जाता है। दूसरा प्रयास भी विफल हो जाता है, क्योंकि 282 फिर से एक वर्ग नहीं होता है।

Try:	1	2	3
a	78	79	80
b2	125	282	441
b	11.18	16.79	21

तीसरे प्रयास से 441 का पूर्ण वर्ग बनता है। तो, $a=80$, $b=21$होता है, और 5959 के कारक $a-b=59$ और $a+b=101$ होते है।

मान लीजिए N के दो से अधिक अभाज्य गुणनखंड होते हैं। वह प्रक्रिया सबसे पहले a और b के न्यूनतम मानों के साथ गुणनखंड प्राप्त करती है। जो, $a+b$ सबसे छोटा कारक ≥ N का वर्गमूल होता है, इत्यादि $a-b=N/(a+b)$ सबसे बड़ा कारक ≤ रूट-मूल होता है। यदि प्रक्रिया प्राप्त हो जाती है तो $N=1\cdot N$ होता है इससे पता चलता है कि N अभाज्य होता है।

$N=cd$ के लिए, मान लीजिए कि c सबसे बड़ा उपमूल कारक होता है। $a=(c+d)/2$, इसलिए चरणों की संख्या न्यूनाधिक निम्न प्रकार है $(c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c$.

यदि N अभाज्य होता है (तो वह $c=1$ होती है), हमें $O(N)$ उपाय की आवश्कता होती है। यह आदिमता सिद्ध करने का एक अनुपयुक्त विधि है। परन्तु यदि N का कोई गुणनखंड इसके वर्गमूल के समीप होता है, तो विधि शीघ्रता से कार्य करती है। अधिक स्पष्ट रूप से, यदि c का अंतर ${\left(4N\right)}^{1/4}$ से कम होता है तब ${\sqrt {N}}$, विधि को मात्र एक चरण की आवश्यकता होती है; यह N के आकार से स्वतंत्र होता है।

फर्मेट और परीक्षण प्रभाग

अभाज्य संख्या N = 2345678917 का गुणनखंड करने का प्रयास करने पर विचार करें , परन्तु b औरa − b की भी गणना करें। इस प्रकार से यह ${\sqrt {N}}$ से ऊपर जाते है, हम इसे निम्न प्रकार सारणीबद्ध कर सकते हैं:

a	48,433	48,434	48,435	48,436
b2	76,572	173,439	270,308	367,179
b	276.7	416.5	519.9	605.9
a − b	48,156.3	48,017.5	47,915.1	47,830.1

व्यवहार में, कोई उस अंतिम पंक्ति से तब तक उत्तेजित नहीं होता है जब तक कि b एक पूर्णांक न हो जाएँ। परन्तु ध्यान दें कि यदि N के पास उपरोक्त उपमूल कारक $a-b=47830.1$ होता है तो इसका अर्थ यह होता है की फ़र्मेट की विधि ने इसे प्रारम्भ में ही प्राप्त कर लिया होता है।

परीक्षण प्रभाग सामान्यतः 48,432 तक प्रयास करता है; परन्तु मात्र चार फ़र्मेट चरणों के बाद, हमें एक कारक अन्वेषण या प्रारंभिकता सिद्ध करने के लिए मात्र 47830 तक विभाजित करने की आवश्यकता होती है।

यह सब एक संयुक्त फैक्टरिंग विधि का सुझाव देता है। कुछ बाध्य $c>{\sqrt {N}}$ का चयन किया जाता ; ${\sqrt {N}}$ और $c$ के मध्य के कारकों के लिए फ़र्मेट विधि का उपयोग किया जाता है। यह ट्रायल डिवीजन के लिए एक बाध्यता देता है जो कि $c-{\sqrt {c^{2}-N}}$ होता है। उपरोक्त उदाहरण में, $c=48436$ के साथ परीक्षण प्रभाग की सीमा 47830 होती है। एक उचित विकल्प $c=55000$ हो सकता है जिसको सीमा 28937 होती है।

इस संबंध में, फ़र्मेट की विधि कम प्रतिफल देती है। इस बिंदु तक पहुचने से पहले कोई निश्चित रूप से रुक जाता है:

a	60,001	60,002
b2	1,254,441,084	1,254,561,087
b	35,418.1	35,419.8
a − b	24,582.9	24,582.2

सीईव में सुधार

$N=2345678917$ के लिए तालिका पर विचार करते समय, कोई तुरंत बता सकता है कि इनमें से कोई भी मान $b^{2}$ वर्ग नहीं होता हैं:

a	48,433	48,434	48,435	48,436
b2	76,572	173,439	270,308	367,179
b	276.7	416.5	519.9	605.9

$a^{2}-N$ के सभी वर्गमूलों की गणना करना आवश्यक नहीं होता है, और न ही a के लिए सभी मानों की जाँच करने आवश्कता होती है । वर्ग सदैव 0, 1, 4, 5, 9, 16 मॉड्यूलर अंकगणित 20 के अनुरूप होते हैं। प्रत्येक वृद्धि के साथ a 10 से मान दोहराए जाते हैं । इस उदाहरण में, N 17 मॉड 20 होता है, इसलिए 17 मॉड 20को घटाया (या 3 जोड़ें) जाता है, $a^{2}-N$ इन मानों के लिए 3, 4, 7, 8, 12, और 19 मॉड्यूल 20 उत्पन्न करता है। यह स्पष्ट है कि इस सूची में से मात्र 4 ही एक वर्ग हो सकते हैं। इस प्रकार, $a^{2}$ 1 मॉड 20 होना चाहिए, जिसका अर्थ a 1, 9, 11 या 19 मॉड 20 होता है; यह एक $b^{2}$ का उत्पादन करेगा जो 4 मॉड 20 में समाप्त होता है और, यदि यह वर्गाकार होता है, तो b² या 8 मॉड 10 में समाप्त हो जाता है।

इसे किसी भी मापांक के साथ निष्पादित किया जा सकता है। $N=2345678917$ का उपयोग किया जाता हैं ,

modulo 16:	Squares are	0, 1, 4, or 9
	N mod 16 is	5
	so $a^{2}$ can only be	9
	and a must be	3 or 5 or 11 or 13 modulo 16
modulo 9:	Squares are	0, 1, 4, or 7
	N mod 9 is	7
	so $a^{2}$ can only be	7
	and a must be	4 or 5 modulo 9

कोई सामान्यतः प्रत्येक मापांक के लिए एक अलग अभाज्य की शक्ति का चयन करता है।

a-मानों (प्रारंभ, अंत और चरण) और एक मापांक के अनुक्रम को देखते हुए, कोई इस प्रकार आगे बढ़ सकता है:

        फ़र्मेटसीव(N, astart, aend, astep, modulus)

    a ← astart
    do modulus times:
        b2 ← a*a - N
        if b2 is a square, modulo modulus:
            फ़र्मेटसीव(N, a, aend, astep * modulus, NextModulus)
        endif
        a ← a + astep
    enddo

रिकर्सन (कंप्यूटर विज्ञान) को तब रोक दिया जाता है जब कुछ a-मान शेष रह जाते हैं; तभी (aend-astart)/astep छोटा होता है। इसके अतिरिक्त, क्योंकि a का चरण-आकार स्थिर होता है, कोई भी जोड़ के साथ क्रमिक b2 की गणना कर सकता है।

गुणक सुधार

फ़र्मेट की विधि तब सबसे अच्छा काम करती है जब कोई कारक N के वर्गमूल के निकट होता है।

यदि दो कारकों का अनुमानित अनुपात ($d/c$) ज्ञात होता है, तो एक परिमेय संख्या $v/u$ उस मूल्य के निकट चुना जा सकता है। $Nuv=cv\cdot du$, और नुव पर लागू फ़र्मेट की विधि, कारकों $cv$ और $du$ शीग्रता से पता लगाती है। तब $\gcd(N,cv)=c$ और $\gcd(N,du)=d$ ओता है। (जब तक कि c u को विभाजित न करे या d, v को विभाजित न करे।)

सामान्यतः, यदि अनुपात ज्ञात नहीं है, तो विभिन्न $u/v$ मूल्यों के लिए प्रयास की जा सकता है, और प्रत्येक परिणामी एनयूवी को कारक बनाने का प्रयास करें। आर. लेहमैन ने ऐसा करने के लिए एक व्यवस्थित तरीका तैयार किया, ताकि फ़र्मेट का प्लस ट्रायल डिवीजन एन को कारक बना सके $O(N^{1/3})$ समय।

आम तौर पर, यदि अनुपात ज्ञात नहीं है, तो विभिन्न यू/वी मानों की कोशिश की जा सकती है, और प्रत्येक परिणामी एनयूवी को कारक बनाने का प्रयास किया जा सकता है। आर. लेहमैन ने ऐसा करने के लिए एक व्यवस्थित तरीका तैयार किया, ताकि फ़र्मेट का प्लस ट्रायल डिवीजन 3)O(N^1⁄3) समय में N का कारक बन सके।[1]

अन्य सुधार

फ़र्मेट की गुणनखंडन विधि के मौलिक विचार द्विघात छलनी और सामान्य संख्या क्षेत्र चलनी के आधार हैं, जो बड़े सेमीप्राइम्स के गुणनखंडन के लिए सबसे प्रसिद्ध एल्गोरिदम हैं, जो सबसे खराब स्थिति वाले हैं। फ़र्मेट की गुणनखंडन विधि की तुलना में द्विघात छलनी द्वारा किया जाने वाला प्राथमिक सुधार यह है कि अनुक्रम में मात्र एक वर्ग खोजने के बजाय $a^{2}-n$, यह इस अनुक्रम के तत्वों का एक उपसमूह ढूंढता है जिसका उत्पाद एक वर्ग है, और यह इसे अत्यधिक कुशल तरीके से करता है। अंतिम परिणाम वही है: वर्ग मॉड n का अंतर, जो कि यदि गैर-तुच्छ है, तो कारक n के लिए उपयोग किया जा सकता है।

यह भी देखें

• वर्ग पूरा करना
• बहुपदों का गुणनखंडन
• कारक प्रमेय
• फ़ॉइल नियम
• मोनोइड गुणनखंडन
• पास्कल का त्रिकोण
• मुख्य कारक है
• कारकीकरण
• यूलर की गुणनखंडन विधि
• पूर्णांक गुणनखंडन
• प्रोग्राम संश्लेषण
• गाऊसी पूर्णांक गुणनखंडों की तालिका
• अद्वितीय गुणनखंडन डोमेन

संदर्भ

• Fermat (1894), Oeuvres de Fermat, vol. 2, p. 256
• McKee, J (1999). "Speeding Fermat's factoring method". Mathematics of Computation. 68 (228): 1729–1737. doi:10.1090/S0025-5718-99-01133-3.

बाहरी संबंध

• Fermat's factorization running time, at blogspot.in
• Fermat's Factorization Online Calculator, at windowspros.ru