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

Revision as of 11:11, 24 July 2023

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

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 ← होना चाहिए

 फॉर्म फ़ैक्टर(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 फिर से एक वर्ग नहीं होता है।

प्रयास:	1	2	3
a	78	79	80
b²	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
b²	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
b²	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
b²	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$ का उपयोग किया जाता हैं ,

मॉड्यूलो 16:	वर्ग इस प्रकार है	0, 1, 4, or 9
	N मॉड 16 है	5
	इसलिए $a^{2}$ मात्र उल्लेखित संख्या हो सकता है	9
	और $a$ अवश्य निम्न प्रकार है	3 or 5 or 11 or 13 मॉड्यूलो 16
मॉड्यूलो 9:	वर्ग निम्न प्रकार है	0, 1, 4, or 7
	N मॉड 9 है	7
	इसलिए $a^{2}$ मात्र उल्लेखित संख्या हो सकता है	7
	और $a$ अवश्य निम्न प्रकार है	4 or 5 मॉड्यूलो 9

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

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

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

 a ← astart
 do modulus times:
  b2 ← a*a - N
  if b2 is a square, मॉड्यूलो 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})$ समय में 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

[1] Lehman, R. Sherman (1974). "बड़े पूर्णांकों का गुणनखंडन" (PDF). Mathematics of Computation. 28 (126): 637–646. doi:10.2307/2005940. JSTOR 2005940.

[1]

@@ Line 1: / Line 1: @@
-'''फ़र्मेट की गुणनखंडन विधि''', जिसका नाम [[पियरे डी फ़र्मेट]] के नाम पर रखा गया है, दो वर्गों के अंतर के रूप में एक सम और विषम संख्या [[पूर्णांक]] के प्रतिनिधित्व पर आधारित होती है:
+'''फ़र्मेट की गुणनखंडन विधि''', जिसका नाम [[पियरे डी फ़र्मेट]] के नाम पर रखा गया था, दो वर्गों के अंतर के रूप में एक सम और विषम संख्या [[पूर्णांक]] के प्रतिनिधित्व पर आधारित होती है:
 :<math>N = a^2 - b^2.</math>
 वह अंतर [[बीजगणित|बीजगणितीय]] रूप से गुणनखंडनीय <math>(a+b)(a-b)</math> होता है; यदि कोई भी कारक एक के समान्तर नहीं होता है, तो यह N का उचित गुणनखंड होता है।
@@ Line 5: / Line 5: @@
 प्रत्येक विषम संख्या का एक ऐसा प्रतिनिधित्व होता है। वास्तव में, यदि <math>N=cd</math> होता है तो, यह N का एक गुणनखंड होता है
 :<math>N = \left(\frac{c+d}{2}\right)^2 - \left(\frac{c-d}{2}\right)^2</math>
-चूँकि N विषम होता है, तो c और d भी विषम होता हैं, इसलिए वे आधे पूर्णांक होते हैं। (चार का गुणज भी वर्गों का अंतर होता है: मान लीजिए कि c और d सम हैं।)
+चूँकि N विषम होता है, तो c और d भी विषम होते हैं, इसलिए वे आधे पूर्णांक होते हैं। (चार का गुणज भी वर्गों का अंतर होता है: मान लीजिए कि c और d सम होते हैं।)
 अपने सरलतम रूप में, फ़र्मेट की विधि परीक्षण प्रभाग (सबसे अनुपयुक्त स्थिति) से भी धीमी हो सकती है। यघपि, परीक्षण प्रभाग और फ़र्मेट का संयोजन किसी की तुलना में अधिक प्रभावी होते है।
 ==मूल विधि==
-कोई व्यक्ति a के विभिन्न मूल्यों की जांच करता है यह आशा करते हुए <math>a^2-N = b^2</math> होता है, एक वर्ग। फॉर्म फ़ैक्टर(AND): // N विषम a ← होना चाहिए {{Not a typo|ceiling(sqrt(N))}}
+कोई व्यक्ति a के विभिन्न मूल्यों की जांच करता है यह आशा करते हुए <math>a^2-N = b^2</math> एक वर्ग होता है। फॉर्म फ़ैक्टर(AND): // N विषम a ← होना चाहिए
-     फॉर्म फ़ैक्टर(N): ''// N विषम होना चाहिए''
+  फॉर्म फ़ैक्टर(N): ''// N विषम होना चाहिए''
-     a ← सीलिंग(sqrt(N))
+  a ← सीलिंग(sqrt(N))
-     b2 ← a*a - N
+  b2 ← a*a - N
-    तब तक दोहराएँ जब तक b2 एक वर्ग न हो जाए:
+  तब तक दोहराएँ जब तक b2 एक वर्ग न हो जाए:
-         a ← a + 1
+   a ← a + 1
-         b2 ← a*a - N
+   b2 ← a*a - N
-      // समान रूप से:
+   // समान रूप से:
-      // b2 ← b2 + 2*a + 1
+   // b2 ← b2 + 2*a + 1
-      // a ← a + 1
+   // a ← a + 1
-     '''रीटर्न''' a - sqrt(b2) ''// or a + sqrt(b2)''
+  '''रीटर्न''' a - sqrt(b2) ''// or a + sqrt(b2)''
-उदाहरण के लिए, कारक के लिए <math>N = 5959</math>, a के लिए पहला प्रयास {{math|5959}} का वर्गमूल है  जिसे अगले पूर्णांक तक पूर्णांकित किया जाता है, जिसका मान  {{math|78}} होता है। तब, <math>b^2 = 78^2-5959 = 125</math> होता है। चूँकि 125 एक वर्ग नहीं होता है, इसलिए a का मान 1 बढ़ाकर दूसरा प्रयास किया जाता है। दूसरा प्रयास भी विफल हो जाता है, क्योंकि 282 फिर से एक वर्ग नहीं होता है।
+उदाहरण के लिए, कारक के लिए <math>N = 5959</math>, a के लिए प्रथम प्रयास {{math|5959}} का वर्गमूल है जिसे अगले पूर्णांक तक पूर्णांकित किया जाता है, जिसका मान {{math|78}} होता है। तब, <math>b^2 = 78^2-5959 = 125</math> होता है। चूँकि 125 एक वर्ग नहीं होता है, इसलिए a का मान 1 बढ़ाकर दूसरा प्रयास किया जाता है। दूसरा प्रयास भी विफल हो जाता है, क्योंकि 282 फिर से एक वर्ग नहीं होता है।
 {| class="wikitable" style="text-align:right;"
-! Try:
+! प्रयास:
 |     1 ||     2 ||   3
 |-
@@ Line 43: / Line 43: @@
 <math>N = cd</math> के लिए, मान लीजिए कि c सबसे बड़ा उपमूल कारक होता है। <math>a = (c+d)/2</math>, इसलिए चरणों की संख्या न्यूनाधिक निम्न प्रकार है <math>(c + d)/2 - \sqrt N = (\sqrt d - \sqrt c)^2 / 2 = (\sqrt N - c)^2 / 2c</math>.
-यदि N अभाज्य होता है (तो वह <math>c = 1</math> होती है), हमें <math>O(N)</math> उपाय की आवश्कता होती है। यह आदिमता सिद्ध करने का एक अनुपयुक्त विधि है। परन्तु  यदि N का कोई गुणनखंड इसके वर्गमूल के समीप होता है, तो विधि शीघ्रता से कार्य करती है। अधिक स्पष्ट रूप से, यदि c का अंतर <math>{\left(4N\right)}^{1/4}</math> से कम होता है तब <math>\sqrt N</math>, विधि को मात्र एक चरण की आवश्यकता होती है; यह N के आकार से स्वतंत्र होता है।
+यदि N अभाज्य होता है (तो वह <math>c = 1</math> होती है), हमें <math>O(N)</math> उपाय की आवश्कता होती है। यह मौलिकता सिद्ध करने की एक अनुपयुक्त विधि होती है। परन्तु यदि N का कोई गुणनखंड इसके वर्गमूल के समीप होता है, तो यह विधि शीघ्रता से कार्य करती है। अधिक स्पष्ट रूप से, यदि c का अंतर <math>{\left(4N\right)}^{1/4}</math> से कम होता है तब <math>\sqrt N</math>, विधि को मात्र एक चरण की आवश्यकता होती है; यह N के आकार से स्वतंत्र होता है।
 ==फर्मेट और परीक्षण प्रभाग==
-अभाज्य संख्या {{nowrap|1=''N'' = 2345678917}} का गुणनखंड करने का प्रयास करने पर विचार करें , परन्तु    ''b'' और{{nowrap|''a'' − ''b''}} की भी गणना करें। इस प्रकार से यह  <math>\sqrt{N}</math> से ऊपर जाते है, हम इसे निम्न प्रकार सारणीबद्ध कर सकते हैं:
+अभाज्य संख्या {{nowrap|1=''N'' = 2345678917}} का गुणनखंड करने का प्रयास करने पर विचार करें , परन्तु ''b'' और{{nowrap|''a'' − ''b''}} की भी गणना करें। इस प्रकार से यह <math>\sqrt{N}</math> से ऊपर जाते है, हम इसे निम्न प्रकार सारणीबद्ध कर सकते हैं:
 {| class="wikitable"
 |-
@@ Line 61: / Line 61: @@
 | 48,156.3 || 48,017.5 || 47,915.1 || 47,830.1
 |}
-व्यवहार में, कोई उस अंतिम पंक्ति से तब तक उत्तेजित नहीं होता है जब तक कि b एक पूर्णांक न हो जाएँ। परन्तु ध्यान दें कि यदि N के पास उपरोक्त उपमूल कारक  <math>a-b=47830.1</math> होता है तो इसका अर्थ यह होता है की फ़र्मेट की विधि ने इसे प्रारम्भ में ही प्राप्त कर लिया होता है।
+व्यवहार में, कोई उस अंतिम पंक्ति से तब तक उत्तेजित नहीं होता है जब तक कि b एक पूर्णांक न हो जाएँ। परन्तु ध्यान दें कि यदि N के पास उपरोक्त उपमूल कारक <math>a-b=47830.1</math> होता है तो इसका अर्थ यह होता है की फ़र्मेट की विधि ने इसे प्रारम्भ में ही प्राप्त कर लिया होता है।
 परीक्षण प्रभाग सामान्यतः 48,432 तक प्रयास करता है; परन्तु मात्र चार फ़र्मेट चरणों के बाद, हमें एक कारक अन्वेषण या प्रारंभिकता सिद्ध करने के लिए मात्र 47830 तक विभाजित करने की आवश्यकता होती है।
-यह सब एक संयुक्त फैक्टरिंग विधि का सुझाव देता है। कुछ बाध्य  <math>c > \sqrt{N}</math> का चयन किया जाता; <math>\sqrt{N}</math> और <math>c</math> के मध्य के कारकों के लिए फ़र्मेट विधि का उपयोग किया जाता है। यह ट्रायल डिवीजन के लिए एक बाध्यता देता है जो कि <math>c - \sqrt{c^2 - N}</math> होता है।  उपरोक्त उदाहरण में, <math>c = 48436</math> के साथ परीक्षण प्रभाग की सीमा 47830 होती है। एक उचित विकल्प  <math>c = 55000</math> हो सकता है जिसको सीमा 28937 होती है।
+यह सब एक संयुक्त फैक्टरिंग विधि का सुझाव देता है। कुछ बाध्य <math>c > \sqrt{N}</math> का चयन किया जाता; <math>\sqrt{N}</math> और <math>c</math> के मध्य के कारकों के लिए फ़र्मेट विधि का उपयोग किया जाता है। यह ट्रायल डिवीजन के लिए एक बाध्यता देता है जो कि <math>c - \sqrt{c^2 - N}</math> होता है। उपरोक्त उदाहरण में, <math>c = 48436</math> के साथ परीक्षण प्रभाग की सीमा 47830 होती है। एक उचित विकल्प <math>c = 55000</math> हो सकता है जिसको सीमा 28937 होती है।
 इस संबंध में, फ़र्मेट की विधि कम प्रतिफल देती है। इस बिंदु तक पहुचने से पहले कोई निश्चित रूप से रुक जाता है:
@@ Line 84: / Line 84: @@
 == सीईव में सुधार ==
-<math>N=2345678917</math> के लिए तालिका पर विचार करते समय, कोई तुरंत बता सकता है कि इनमें से कोई भी मान  <math>b^2</math> वर्ग नहीं होता हैं:
+<math>N=2345678917</math> के लिए तालिका पर विचार करते समय, कोई शीघ्र बता सकता है कि इनमें से कोई भी मान <math>b^2</math> वर्ग नहीं होता हैं:
 {| class="wikitable"  style="text-align:right;"
@@ Line 97: / Line 97: @@
 |  276.7 ||   416.5 ||   519.9 ||   605.9
 |}
-<math>a^2-N</math> के सभी वर्गमूलों की गणना करना आवश्यक नहीं होता है, और न ही {{mvar|a}} के लिए सभी मानों की जाँच करने आवश्कता होती है । वर्ग सदैव  0, 1, 4, 5, 9, 16 [[मॉड्यूलर अंकगणित]] 20 के अनुरूप होते हैं। प्रत्येक वृद्धि के साथ {{mvar|a}} 10 से मान दोहराए जाते हैं । इस उदाहरण में, N 17 मॉड 20 होता है, इसलिए 17 मॉड 20को घटाया (या 3 जोड़ें) जाता है, <math>a^2-N</math> इन मानों के लिए 3, 4, 7, 8, 12, और 19 मॉड्यूल 20 उत्पन्न करता है। यह स्पष्ट है कि इस सूची में से मात्र 4 ही एक वर्ग हो सकते हैं। इस प्रकार, <math>a^2</math> 1 मॉड 20 होना चाहिए, जिसका अर्थ {{mvar|a}} 1, 9, 11 या 19 मॉड 20 होता है; यह एक <math>b^2</math> का उत्पादन करेगा  जो 4 मॉड 20 में समाप्त होता है और, यदि यह वर्गाकार होता है, तो {{mvar|b}}<sup>2</sup>  या 8 मॉड 10 में समाप्त हो जाता है।
+<math>a^2-N</math> के सभी वर्गमूलों की गणना करना आवश्यक नहीं होता है, और न ही {{mvar|a}} के लिए सभी मानों की जाँच करने आवश्कता होती है। वर्ग सदैव 0, 1, 4, 5, 9, 16 [[मॉड्यूलर अंकगणित]] 20 के अनुरूप होते हैं। प्रत्येक वृद्धि के साथ {{mvar|a}} 10 से मान दोहराए जाते हैं । इस उदाहरण में, N 17 मॉड 20 होता है, इसलिए 17 मॉड 20 को घटाया (या 3 जोड़ें) जाता है, <math>a^2-N</math> इन मानों के लिए 3, 4, 7, 8, 12, और 19 मॉड्यूल 20 उत्पन्न करता है। यह स्पष्ट है कि इस सूची में से मात्र 4 ही एक वर्ग हो सकते हैं। इस प्रकार, <math>a^2</math> 1 मॉड 20 होना चाहिए, जिसका अर्थ {{mvar|a}} 1, 9, 11 या 19 मॉड 20 होता है; यह एक <math>b^2</math> का उत्पादन करेगा जो 4 मॉड 20 में समाप्त होता है और, यदि यह वर्गाकार होता है, तो {{mvar|b}}<sup>2</sup> या 8 मॉड 10 में समाप्त हो जाता है।
 इसे किसी भी मापांक के साथ निष्पादित किया जा सकता है। <math>N=2345678917</math> का उपयोग किया जाता हैं ,
 {|
 |-
-|modulo 16:||Squares are ||0, 1, 4, or 9
+|मॉड्यूलो 16:||वर्ग इस प्रकार है ||0, 1, 4, or 9
 |-
-|          ||N mod 16 is||5
+|          ||N मॉड 16 है ||5
 |-
-|          ||so <math>a^2</math> can only be||9
+|          ||इसलिए <math>a^2</math> मात्र उल्लेखित संख्या हो सकता है ||9
 |-
-|          ||and {{mvar|a}} must be||3 or 5 or 11 or 13 modulo 16
+|          ||और {{mvar|a}} अवश्य निम्न प्रकार है ||3 or 5 or 11 or 13 मॉड्यूलो 16
 |-
-|modulo 9: ||Squares are ||0, 1, 4, or 7
+|मॉड्यूलो 9: ||वर्ग निम्न प्रकार है ||0, 1, 4, or 7
 |-
-|          ||N mod 9 is||7
+|          ||N मॉड 9 है ||7
 |-
-|          ||so <math>a^2</math> can only be||7
+|          ||इसलिए <math>a^2</math> मात्र उल्लेखित संख्या हो सकता है ||7
 |-
-|          ||and {{mvar|a}} must be||4 or 5 modulo 9
+|          ||और {{mvar|a}} अवश्य निम्न प्रकार है ||4 or 5 मॉड्यूलो 9
 |}
 कोई सामान्यतः प्रत्येक मापांक के लिए एक अलग अभाज्य की शक्ति का चयन करता है।
 a-मानों (प्रारंभ, अंत और चरण) और एक मापांक के अनुक्रम को देखते हुए, कोई इस प्रकार आगे बढ़ सकता है:
-         फ़र्मेटसीव(N, astart, aend, astep, modulus)
+   फ़र्मेटसीव(N, astart, aend, astep, modulus)
-     a ← astart
+  a ← astart
-     '''do''' modulus '''times''':
+  '''do''' modulus '''times''':
-         b2 ← a*a - N
+   b2 ← a*a - N
-         '''if''' b2 is a square, modulo modulus:
+   '''if''' b2 is a square, मॉड्यूलो modulus:
-             फ़र्मेटसीव(N, a, aend, astep * modulus, NextModulus)
+   फ़र्मेटसीव(N, a, aend, astep * modulus, NextModulus)
-         '''endif'''
+   '''endif'''
-         a ← a + astep
+   a ← a + astep
-     '''enddo'''
+  '''enddo'''
 [[रिकर्सन (कंप्यूटर विज्ञान)]] को तब रोक दिया जाता है जब कुछ ''a''-मान शेष रह जाते हैं; तभी ({{Not a typo|aend-astart}})/{{Not a typo|astep}} छोटा होता है। इसके अतिरिक्त, क्योंकि a का चरण-आकार स्थिर होता है, कोई भी जोड़ के साथ क्रमिक b2 की गणना कर सकता है।
@@ Line 137: / Line 137: @@
 फ़र्मेट की विधि तब सबसे अच्छा काम करती है जब कोई कारक N के वर्गमूल के निकट होता है।
-यदि दो कारकों का अनुमानित अनुपात (<math>d/c</math>) ज्ञात होता है, तो एक परिमेय संख्या <math>v/u</math> उस मूल्य के निकट चुना जा सकता है। <math>Nuv = cv \cdot du</math>, और नुव पर लागू फ़र्मेट की विधि, कारकों  <math>cv</math> और <math>du</math> शीग्रता से पता लगाती है। तब <math>\gcd(N,cv)=c</math> और <math>\gcd(N,du)=d</math> ओता है। (जब तक कि c  ''u को''  विभाजित न करे या d, v को विभाजित न करे।)
+यदि दो कारकों का अनुमानित अनुपात (<math>d/c</math>) ज्ञात होता है, तो एक परिमेय संख्या <math>v/u</math> उस मूल्य के निकट चयन किया जा सकता है। <math>Nuv = cv \cdot du</math>, और नुव पर प्रयुक्त फ़र्मेट की विधि, कारकों <math>cv</math> और <math>du</math> शीग्रता से पता लगाती है। तब <math>\gcd(N,cv)=c</math> और <math>\gcd(N,du)=d</math> होता है। (जब तक कि c ''u को'' विभाजित न करे या d, v को विभाजित न करे।)
-सामान्यतः, यदि अनुपात ज्ञात नहीं है, तो विभिन्न <math>u/v</math> मूल्यों के लिए  प्रयास की जा सकता है, और प्रत्येक परिणामी एनयूवी को कारक बनाने का प्रयास किया जा सकता है।आर. लेहमैन ने ऐसा करने के लिए एक व्यवस्थित विधि  निर्मित की थी, जिससे फ़र्मेट का प्लस ट्रायल डिवीजन  <math>O(N^{1/3})</math>समय में N का कारक बन सके।<ref>{{cite journal |last=Lehman |first=R. Sherman |year=1974 |title=बड़े पूर्णांकों का गुणनखंडन|journal=[[Mathematics of Computation]] |doi=10.2307/2005940 |doi-access=free |jstor=2005940 |volume=28 |issue=126 |pages=637–646 |url=https://www.ams.org/journals/mcom/1974-28-126/S0025-5718-1974-0340163-2/S0025-5718-1974-0340163-2.pdf}}</ref>
+सामान्यतः, यदि अनुपात ज्ञात नहीं है, तो विभिन्न <math>u/v</math> मूल्यों के लिए प्रयास की जा सकता है, और प्रत्येक परिणामी एनयूवी को कारक बनाने का प्रयास किया जा सकता है।आर. लेहमैन ने ऐसा करने के लिए एक व्यवस्थित विधि निर्मित की थी, जिससे फ़र्मेट का प्लस ट्रायल डिवीजन <math>O(N^{1/3})</math>समय में N का कारक निर्मित हो सके।<ref>{{cite journal |last=Lehman |first=R. Sherman |year=1974 |title=बड़े पूर्णांकों का गुणनखंडन|journal=[[Mathematics of Computation]] |doi=10.2307/2005940 |doi-access=free |jstor=2005940 |volume=28 |issue=126 |pages=637–646 |url=https://www.ams.org/journals/mcom/1974-28-126/S0025-5718-1974-0340163-2/S0025-5718-1974-0340163-2.pdf}}</ref>
 == अन्य सुधार ==
-फ़र्मेट की गुणनखंडन विधि के मौलिक विचार [[द्विघात छलनी|द्विघात सीईव]] और सामान्य संख्या क्षेत्र सीईव के आधार होते हैं, जो बड़े [[सेमीप्राइम्स]] के गुणनखंडन के लिए सबसे प्रसिद्ध कलन विधि होती हैं, जो सबसे अनुपयुक्त स्थिति वाले हैं। फ़र्मेट की गुणनखंडन विधि की तुलना में द्विघात सीईव द्वारा किया जाने वाला प्राथमिक सुधार यह है कि अनुक्रम में मात्र एक वर्ग अन्वेषण के अतिरिक्त  <math>a^2 - n</math>, यह इस अनुक्रम के तत्वों का एक उपसमूह ढूंढता है जिसका उत्पाद एक वर्ग होता है, और यह इसे अत्यधिक कुशल विधि से करता है।अंतिम परिणाम वही है: वर्ग मॉड n का अंतर, जो कि यदि गैर-तुच्छ होता है, तो कारक n के लिए उपयोग किया जा सकता है।
+फ़र्मेट की गुणनखंडन विधि के मौलिक विचार [[द्विघात छलनी|द्विघात सीईव]] और सामान्य संख्या क्षेत्र सीईव के आधार होते हैं, जो बड़े [[सेमीप्राइम्स]] के गुणनखंडन के लिए सबसे प्रसिद्ध कलन विधि होती हैं, जो सबसे अनुपयुक्त स्थिति वाले होते हैं। फ़र्मेट की गुणनखंडन विधि की तुलना में द्विघात सीईव द्वारा किया जाने वाला प्राथमिक सुधार यह है कि अनुक्रम में मात्र एक वर्ग अन्वेषण के अतिरिक्त <math>a^2 - n</math>, यह इस अनुक्रम के तत्वों का एक उपसमूह ढूंढता है जिसका उत्पाद एक वर्ग होता है, और यह इसे अत्यधिक कुशल विधि से करता है।अंतिम परिणाम यह है की: वर्ग मॉड n का अंतर होता है, जो कि यदि गैर-तुच्छ होता है, तो कारक n के लिए उपयोग किया जा सकता है।
 ==यह भी देखें==

v t e संख्या-सिद्धांत एल्गोरिथ्म
प्राइमैलिटी टेस्ट	AKS अप्रैल BAILLIE -PSW अण्डाकार वक्र पॉकलिंगटन Fermat लुकास लुकास -लेहमेर लुकास -लेहमेर -रेज़ल ' प्रोथ का प्रमेय पेपिन का द्विघात फ्रोबेनियस सोलोवे -स्ट्रासेन मिलर -रबिन
प्राइम-जनरेटिंग	एटकिन की छलनी एरातोस्टेनेस की छलनी प्रिचर्ड की छलनी सुंदरम की छलनी पहिया कारक
पूर्णांक कारक	निरंतर अंश कारक। निरंतर अंश (CFRAC) डिक्सन Lenstra अण्डाकार-वक्र कारक Euler's पोलार्ड्स आरएचओ P - 1 पी + 1 द्विघात छलनी (क्यूएस) सामान्य संख्या क्षेत्र छलनी (GNFS) विशेष संख्या क्षेत्र छलनी (SNFS) तर्कसंगत छलनी फर्माट शैंक्स स्क्वायर फॉर्म ट्रायल डिवीजन शोर
गुणा	प्राचीन मिस्र लंबा करत्सुबा टूम - कुक Schönhage - Strassen Für's
Euclidean डिवीजन	बाइनरी चंकिंग फूरियर Goldschmidt न्यूटन-रफसन लंबा छोटा SRT
असतत लघुगणक	बेबी-स्टेप विशाल-चरण पोलार्ड रो पोलार्ड कंगारू Pohlig -Hellman इंडेक्स कैलकुलस फ़ंक्शन फ़ील्ड छलनी
महत्तम सामान्य भाजक	बाइनरी Euclidean विस्तारित यूक्लिडियन लेहमर
मॉड्यूलर वर्गमूल	Cipolla पॉकलिंगटन तनेली -शंक Berlekamp कुनरथ
अन्य एल्गोरिदम	चक्रवाला कॉर्नचिया वर्ग द्वारा घातक पूर्णांक वर्गमूल पूर्णांक संबंध मॉड्यूलर घातांक मोंटगोमरी में कमी शूफ़ ट्रेचेनबर्ग सिस्टम
इटैलिक इंगित करता है कि एल्गोरिथ्म विशेष रूपों की संख्या के लिए है

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 11:11, 24 July 2023

Contents

मूल विधि

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

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

गुणक सुधार

अन्य सुधार

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 11:11, 24 July 2023

मूल विधि

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

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

गुणक सुधार

अन्य सुधार

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories