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

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

$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))

    b2 ← a*a - N
    तब तक दोहराएँ जब तक b2 एक वर्ग न हो जाए:
        ए ← ए + 1
        b2 ← a*a - N
     // समकक्ष:
     // बी2 ← बी2 + 2*ए + 1
     // ए ← ए + 1
    एक वापसी - sqrt(b2) //या एक + 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, लेकिन बी और की भी गणना करें 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 से। इस उदाहरण में, एन 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 2 या 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

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

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

FermatSieve(N, प्रारंभ करें, और, रोकें, मापांक) a ← प्रारंभ करें मापांक समय: b2 ← a*a - N यदि b2 एक वर्ग है, मापांक मापांक: FermatSieve(N, ए, एएंड, एस्टेप * मॉड्यूलस, नेक्स्ट मॉड्यूलस)

        अगर अंत
        ए ← ए + एस्टेप
    एंडडो

लेकिन रिकर्सन (कंप्यूटर विज्ञान) को तब रोक दिया जाता है जब कुछ ए-मान शेष रह जाते हैं; तभी (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 तुम्हें विभाजित न करे या d, v को विभाजित न करे।)

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

अन्य सुधार

फ़र्मेट की गुणनखंडन विधि के मौलिक विचार द्विघात छलनी और सामान्य संख्या क्षेत्र चलनी के आधार हैं, जो बड़े सेमीप्राइम्स के गुणनखंडन के लिए सबसे प्रसिद्ध एल्गोरिदम हैं, जो सबसे खराब स्थिति वाले हैं। फ़र्मेट की गुणनखंडन विधि की तुलना में द्विघात छलनी द्वारा किया जाने वाला प्राथमिक सुधार यह है कि अनुक्रम में केवल एक वर्ग खोजने के बजाय $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