लुकास अनुक्रम: Difference between revisions

Revision as of 12:38, 14 July 2023

गणित में, लुकास अनुक्रम $U_{n}(P,Q)$ और $V_{n}(P,Q)$ कुछ स्थिर-पुनरावर्ती अनुक्रम होता है जो पुनरावृत्ति संबंध को प्रदर्शित करते हैं

x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2}

जहाँ $P$ और $Q$ निश्चित पूर्णांक होता हैं। इस पुनरावृत्ति संबंध को सरल करने वाले किसी भी अनुक्रम को लुकास अनुक्रमों $U_{n}(P,Q)$ और $V_{n}(P,Q)$ के रैखिक संयोजन के रूप में प्रदर्शित किया जा सकता है।

अधिक सामान्यतः, लुकास अनुक्रम $U_{n}(P,Q)$ और $V_{n}(P,Q)$ में बहुपद के अनुक्रम का प्रतिनिधित्व $P$ और $Q$ पूर्णांक गुणांक के साथ करते हैं।

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

पुनरावृत्ति संबंध

दो पूर्णांक पैरामीटर $P$ और $Q$ दिए गएदिए गए है, प्रथम प्रकार के लुकास अनुक्रम $U_{n}(P,Q)$ और दूसरे प्रकार का $V_{n}(P,Q)$ पुनरावृत्ति संबंधों द्वारा परिभाषित किया जाता हैं:

{\begin{aligned}U_{0}(P,Q)&=0,\\U_{1}(P,Q)&=1,\\U_{n}(P,Q)&=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q){\mbox{  for }}n>1,\end{aligned}}

और

{\begin{aligned}V_{0}(P,Q)&=2,\\V_{1}(P,Q)&=P,\\V_{n}(P,Q)&=P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q){\mbox{  for }}n>1.\end{aligned}}

$n>0$ इसे प्रदर्शित करना कठिन नहीं होता है ,

{\begin{aligned}U_{n}(P,Q)&={\frac {P\cdot U_{n-1}(P,Q)+V_{n-1}(P,Q)}{2}},\\V_{n}(P,Q)&={\frac {(P^{2}-4Q)\cdot U_{n-1}(P,Q)+P\cdot V_{n-1}(P,Q)}{2}}.\end{aligned}}

उपरोक्त संबंधों का आव्युह रूप में इस प्रकार वर्णित किया जा सकता है:

{\begin{bmatrix}U_{n}(P,Q)\\U_{n+1}(P,Q)\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\U_{n}(P,Q)\end{bmatrix}},

{\begin{bmatrix}V_{n}(P,Q)\\V_{n+1}(P,Q)\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin{bmatrix}V_{n-1}(P,Q)\\V_{n}(P,Q)\end{bmatrix}},

{\begin{bmatrix}U_{n}(P,Q)\\V_{n}(P,Q)\end{bmatrix}}={\begin{bmatrix}P/2&1/2\\(P^{2}-4Q)/2&P/2\end{bmatrix}}\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\V_{n-1}(P,Q)\end{bmatrix}}.

उदाहरण

लुकास अनुक्रमों की प्रारंभिक स्थितियां $U_{n}(P,Q)$ और $V_{n}(P,Q)$ तालिका में निम्न प्रकार दिए गए हैं:

{\begin{array}{r|l|l}n&U_{n}(P,Q)&V_{n}(P,Q)\\\hline 0&0&2\\1&1&P\\2&P&{P}^{2}-2Q\\3&{P}^{2}-Q&{P}^{3}-3PQ\\4&{P}^{3}-2PQ&{P}^{4}-4{P}^{2}Q+2{Q}^{2}\\5&{P}^{4}-3{P}^{2}Q+{Q}^{2}&{P}^{5}-5{P}^{3}Q+5P{Q}^{2}\\6&{P}^{5}-4{P}^{3}Q+3P{Q}^{2}&{P}^{6}-6{P}^{4}Q+9{P}^{2}{Q}^{2}-2{Q}^{3}\end{array}}

स्पष्ट अभिव्यक्ति

लुकास अनुक्रमों के लिए पुनरावृत्ति संबंध का विशिष्ट समीकरण $U_{n}(P,Q)$ और $V_{n}(P,Q)$ होता है:

x^{2}-Px+Q=0\,

इसमें $D=P^{2}-4Q$ विभेदक होता और बहुपद का मूल निम्न प्रकार है:

a={\frac {P+{\sqrt {D}}}{2}}\quad {\text{and}}\quad b={\frac {P-{\sqrt {D}}}{2}}.\,

इस प्रकार:

a+b=P\,,

ab={\frac {1}{4}}(P^{2}-D)=Q\,,

a-b={\sqrt {D}}\,.

ध्यान दें कि क्रम $a^{n}$ और क्रम $b^{n}$ पुनरावृत्ति संबंध को भी सरल करते हैं। यघपि ये पूर्णांक अनुक्रम नहीं हो सकते हैं।

विशिष्ट मूल

जब $D\neq 0$ , a और b भिन्न-भिन्न होता हैं और कोई भी इसे शीघ्रता से सत्यापित कर सकता है

a^{n}={\frac {V_{n}+U_{n}{\sqrt {D}}}{2}}

b^{n}={\frac {V_{n}-U_{n}{\sqrt {D}}}{2}}.

इससे यह पता चलता है कि लुकास अनुक्रमों की स्थितियों को a और b के संदर्भ में निम्नानुसार व्यक्त किया जा सकता है

U_{n}={\frac {a^{n}-b^{n}}{a-b}}={\frac {a^{n}-b^{n}}{\sqrt {D}}}

V_{n}=a^{n}+b^{n}\,

पुनरावर्तित मूल

स्थिति $D=0$ मात्र तब होता है जब $P=2S{\text{ औ र }}Q=S^{2}$ कुछ पूर्णांक S के लिए होता जिससे $a=b=S$ होता है। इस स्थति में कोई भी इसे सरलता से प्राप्त कर सकते है

U_{n}(P,Q)=U_{n}(2S,S^{2})=nS^{n-1}\,

V_{n}(P,Q)=V_{n}(2S,S^{2})=2S^{n}.\,

गुण

कार्य उत्पन्न करना

सामान्य जनरेटिंग फलन निम्न प्रकार होता हैं

\sum _{n\geq 0}U_{n}(P,Q)z^{n}={\frac {z}{1-Pz+Qz^{2}}};

\sum _{n\geq 0}V_{n}(P,Q)z^{n}={\frac {2-Pz}{1-Pz+Qz^{2}}}.

पेल समीकरण

कब $Q=\pm 1$ , लुकास अनुक्रम $U_{n}(P,Q)$ और $V_{n}(P,Q)$ कुछ पेल समीकरण को सरल करें:

V_{n}(P,1)^{2}-D\cdot U_{n}(P,1)^{2}=4,

V_{2n}(P,-1)^{2}-D\cdot U_{2n}(P,-1)^{2}=4,

V_{2n+1}(P,-1)^{2}-D\cdot U_{2n+1}(P,-1)^{2}=-4.

विभिन्न मापदंडों के साथ अनुक्रमों के मध्य संबंध

किसी भी संख्या c के लिए, अनुक्रम $U_{n}(P',Q')$ और $V_{n}(P',Q')$ के साथ

P'=P+2c

Q'=cP+Q+c^{2}

के समान विभेदक

U_{n}(P,Q)

और

V_{n}(P,Q)

होता है:

P'^{2}-4Q'=(P+2c)^{2}-4(cP+Q+c^{2})=P^{2}-4Q=D.

किसी भी संख्या c के लिए, हमारे पास भी निम्न समीकरण होता है

U_{n}(cP,c^{2}Q)=c^{n-1}\cdot U_{n}(P,Q),

V_{n}(cP,c^{2}Q)=c^{n}\cdot V_{n}(P,Q).

अन्य संबंध

लुकास अनुक्रमों की स्थिति उन संबंधों को सरल करती हैं जो फाइबोनैचि संख्याओं के मध्य $F_{n}=U_{n}(1,-1)$ और लुकास संख्याएँ $L_{n}=V_{n}(1,-1)$ के सामान्यीकरण होता है। उदाहरण के लिए:

\begin{aligned} General case & (P, Q) = (1, - 1) \\ (P^{2} - 4 Q) U_{n} = V_{n + 1} - Q V_{n - 1} = 2 V_{n + 1} - P V_{n} & 5 F_{n} = L_{n + 1} + L_{n - 1} = 2 L_{n + 1} - L_{n} \\ V_{n} = U_{n + 1} - Q U_{n - 1} = 2 U_{n + 1} - P U_{n} & L_{n} = F_{n + 1} + F_{n - 1} = 2 F_{n + 1} - F_{n} \\ U_{2 n} = U_{n} V_{n} & F_{2 n} = F_{n} L_{n} \\ V_{2 n} = V_{n}^{2} - 2 Q^{n} & L_{2 n} = L_{n}^{2} - 2 {(- 1)}^{n} \\ U_{m + n} = U_{n} U_{m + 1} - Q U_{m} U_{n -} \end{aligned}

विभाज्यता गुण

परिणामों में सम्मिलित

U_{km}(P,Q)

U_{m}(P,Q)

का गुणज होता है, अर्थात्, अनुक्रम

(U_{m}(P,Q))_{m\geq 1}

एक विभाज्यता क्रम होता है। इसका तात्पर्य, विशेष रूप से, जब

U_{n}(P,Q)

मात्र तभी अभाज्य संख्या हो सकती है जब n अभाज्य हो। इस प्रकार अन्य परिणाम वर्ग द्वारा घातांक का अनुरूप होता है जो शीघ्रता से गणना की अनुमति देता है जों

U_{n}(P,Q)

n के बड़े मानों के लिए होता है।इसके अतिरिक्त, यदि

\gcd(P,Q)=1

होता है, तब

(U_{m}(P,Q))_{m\geq 1}

विभाज्यता क्रम होता है।

अन्य विभाज्यता गुण इस प्रकार हैं:^[1]

अगर $n\mid m$ तो विषम होता है तो $V_{m}$ विभाजित $V_{n}$ होता है।
मान लीजिए N, 2Q के सापेक्ष अभाज्य पूर्णांक है। यदि सबसे छोटा धनात्मक पूर्णांक r जिसके लिए N विभाजित होता है $U_{r}$ उपस्थिति है, तो n का वह समुच्चय जिसके लिए N विभाजित होता है $U_{n}$ अवश्य r के गुणजों का समुच्चय होता है।
यदि P और Q समता (गणित) हैं, तो $U_{n},V_{n}$ को छोड़कर $U_{1}$ सदैव सम होते हैं।
यदि P सम है और Q विषम है, तो समता (गणित) की $U_{n}$ n और $V_{n}$ के समान होते है जो सदैव सम रहता है।
यदि P विषम है और Q सम है, तो $U_{n},V_{n}$ सदैव $n=1,2,\ldots$ के लिए विषम होते हैं।
यदि P और Q विषम हैं, तो $U_{n},V_{n}$ सम होता हैं यदि और मात्र यदि n, 3 का गुणज होता है।
यदि p विषम अभाज्य है, तो $U_{p}\equiv \left({\tfrac {D}{p}}\right),V_{p}\equiv P{\pmod {p}}$ होता है (लेजेन्ड्रे प्रतीक देखें)।
यदि p विषम अभाज्य है और P और Q को विभाजित करता है, तो p प्रत्येक $n>1$ पर $U_{n}$ से विभाजित होता है।
यदि p विषम अभाज्य है और P को विभाजित करता है लेकिन Q को नहीं, तो p $U_{n}$ को विभाजित करता है यदि और मात्र यदि n सम होता है।
यदि p विषम अभाज्य है और P को नहीं जबकि Q को विभाजित करता है, तो p कभी भी $n=1,2,\ldots$ के लिए $U_{n}$ से विभाजित नहीं होता है।
यदि p विषम अभाज्य है और PQ को नहीं बल्कि D को विभाजित करता है, तो p विभाजित होता है $U_{n}$ यदि और मात्र यदि p, n को विभाजित करता है।
यदि p विषम अभाज्य है और PQD को विभाजित नहीं करता है, तो p $U_{l}$ से विभाजित होता है, जहाँ $l=p-\left({\tfrac {D}{p}}\right)$ होता है।

अंतिम तथ्य फ़र्मेट के छोटे प्रमेय का सामान्यीकरण करता है। इन तथ्यों का उपयोग लुकास-लेहमर अभाज्यलिटी परीक्षण में किया जाता है। अंतिम तथ्य का व्युत्क्रम (तर्क) मान्य नहीं होता है, जैसे फ़र्मेट के छोटे प्रमेय का व्युत्क्रम मान्य नहीं होता है। D और $U_{l}$ विभाजक के सापेक्ष भाज्य संख्या n उपस्थिति होता है, जहाँ $l=n-\left({\tfrac {D}{n}}\right)$ होता है। ऐसे सम्मिश्रण को लुकास स्यूडोअभाज्य कहा जाता है।

लुकास अनुक्रम में किसी पद का अभाज्य कारक जो अनुक्रम में किसी भी पहले के पद को विभाजित नहीं करता है उसे प्राथमिक कहा जाता है। कारमाइकल के प्रमेय में कहा गया है कि लुकास अनुक्रम में सभी लेकिन सीमित रूप से कई शब्दों में प्राथमिक अभाज्य कारक होता है।^[2] वास्तव में, कारमाइकल (1913) ने दिखाया कि यदि D धनात्मक होता है और n 1, 2 या 6 नहीं होता है, तो $U_{n}$ प्राथमिक अभाज्य कारक होता है। D नकारात्मक स्थितियों में, बिलु, हनरोट, वाउटियर और मिग्नोटे का अत्यंत परिणाम होता है^[3] जो प्रदर्शित करता है कि यदि n > 30, तो $U_{n}$ प्राथमिक अभाज्य कारक होता है और सभी स्थितियों को निर्धारित करता है $U_{n}$ कोई प्राथमिक अभाज्य गुणनखंड नहीं होता है।

विशिष्ट नाम

P और Q के कुछ मानों के लिए लुकास अनुक्रमों के विशिष्ट नाम हैं:

U n (1, -1)

: फाइबोनैचि संख्याएँ

V n (1, -1)

: लुकास संख्याएँ

U n (2, -1)

: पेलें संख्याएँ

V n (2, -1)

: पेल-लुकास संख्याएँ (सहचर पेल संख्याएँ )

U n (1, -2)

: जैकबस्थल संख्याएँ

V n (1, -2)

: जैकबस्थल-लुकास संख्याएँ

U n (3, 2)

: मेर्सन संख्या 2ⁿ‍− 1

V n (3, 2)

: फॉर्म के संख्याएँ 2ⁿ + 1, जिसमें फ़र्मेट संख्याएँ सम्मिलित होती हैं^[2]

U n (6, 1)

: वर्ग त्रिकोणीय संख्याओं का वर्गमूल।

U n (x, -1)

: फाइबोनैचि बहुपद

V n (x, -1)

: लुकास बहुपद

U n (2 x, 1)

: दूसरी तरह के चेबीशेव बहुपद

V n (2 x, 1)

: प्रथम प्रकार के चेबीशेव बहुपद को 2 से गुणा किया गया

U n (x +1, x)

: आधार x में पुनःपुनित करता है

V n (x +1, x)

: xⁿ + 1

कुछ लुकास अनुक्रमों की पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में प्रविष्टियाँ निम्न प्रकार हैं:

$P\,$	$Q\,$	$U_{n}(P,Q)\,$	$V_{n}(P,Q)\,$
−1	3	OEIS: A214733
1	−1	OEIS: A000045	OEIS: A000032
1	1	OEIS: A128834	OEIS: A087204
1	2	OEIS: A107920	OEIS: A002249
2	−1	OEIS: A000129	OEIS: A002203
2	1	OEIS: A001477
2	2	OEIS: A009545	OEIS: A007395
2	3	OEIS: A088137
2	4	OEIS: A088138
2	5	OEIS: A045873
3	−5	OEIS: A015523	OEIS: A072263
3	−4	OEIS: A015521	OEIS: A201455
3	−3	OEIS: A030195	OEIS: A172012
3	−2	OEIS: A007482	OEIS: A206776
3	−1	OEIS: A006190	OEIS: A006497
3	1	OEIS: A001906	OEIS: A005248
3	2	OEIS: A000225	OEIS: A000051
3	5	OEIS: A190959
4	−3	OEIS: A015530	OEIS: A080042
4	−2	OEIS: A090017
4	−1	OEIS: A001076	OEIS: A014448
4	1	OEIS: A001353	OEIS: A003500
4	2	OEIS: A007070	OEIS: A056236
4	3	OEIS: A003462	OEIS: A034472
4	4	OEIS: A001787
5	−3	OEIS: A015536
5	−2	OEIS: A015535
5	−1	OEIS: A052918	OEIS: A087130
5	1	OEIS: A004254	OEIS: A003501
5	4	OEIS: A002450	OEIS: A052539
6	1	OEIS: A001109	OEIS: A003499

अनुप्रयोग

लुकास अनुक्रमों का उपयोग संभाव्य लुकास स्यूडोअभाज्य परीक्षणों में किया जाता है, जो सामान्यतः प्रयोग किए जाने वाले बैली-पीएसडब्ल्यू प्रारंभिक परीक्षण का भाग होता हैं।
लुकास अनुक्रमों का उपयोग कुछ प्रारंभिक प्रमाण विधियों में किया जाता है, जिनमें लुकास-लेहमर-रीज़ल परीक्षण, और N+1और संकर N−1/N+1 विधियां जैसे ब्रिलहार्ट-लेहमर-सेल्फ्रिज 1975 सम्मिलित होता हैं।^[4]
एलयूसी लुकास अनुक्रमों पर आधारित सार्वजनिक-कुंजी क्रिप्टोप्रणाली है^[5] जो एलगमाल (LUCELG), डिफी-हेलमैन (LUCDIF), और RSA (कलन विधि) (LUCRSA) के एनालॉग्स को प्रयुक्त करता है। एलयूसी में संदेश के कूटलेखन की गणना आरएसए या डिफी-हेलमैन जैसे मॉड्यूलर घातांक का उपयोग करने के अतिरिक्त, कुछ लुकास अनुक्रम के शब्द के रूप में की जाती है। यघपि, ब्लेइचेनबैकर एट अल द्वारा पेपर ^[6] प्रदर्शित करता है कि मॉड्यूलर घातांक पर आधारित क्रिप्टोप्रणाली पर एलयूसी के कई कथित सुरक्षा लाभ या तो उपस्थिति नहीं होते हैं, या उतने पर्याप्त नहीं होते हैं जितना माना जाता है।

यह भी देखें

लुकास स्यूडोअभाज्य
फ्रोबेनियस स्यूडोअभाज्य
सोमर-लुकास स्यूडोअभाज्य

↑ For such relations and divisibility properties, see (Carmichael 1913), (Lehmer 1930) or (Ribenboim 1996, 2.IV).
↑ ^2.0 ^2.1 Yabuta, M (2001). "आदिम भाजक पर कारमाइकल के प्रमेय का एक सरल प्रमाण" (PDF). Fibonacci Quarterly. 39: 439–443. Retrieved 4 October 2018.
↑ Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M.; Mignotte, Maurice (2001). "लुकास और लेहमर संख्याओं के आदिम भाजक का अस्तित्व" (PDF). J. Reine Angew. Math. 2001 (539): 75–122. doi:10.1515/crll.2001.080. MR 1863855. S2CID 122969549.
↑ John Brillhart; Derrick Henry Lehmer; John Selfridge (April 1975). "New Primality Criteria and Factorizations of 2^m ± 1". Mathematics of Computation. 29 (130): 620–647. doi:10.1090/S0025-5718-1975-0384673-1. JSTOR 2005583.
↑ P. J. Smith; M. J. J. Lennon (1993). "LUC: A new public key system". Proceedings of the Ninth IFIP Int. Symp. On Computer Security: 103–117. CiteSeerX 10.1.1.32.1835.
↑ D. Bleichenbacher; W. Bosma; A. K. Lenstra (1995). "लुकास-आधारित क्रिप्टोसिस्टम पर कुछ टिप्पणियाँ" (PDF). Lecture Notes in Computer Science. 963: 386–396. doi:10.1007/3-540-44750-4_31. ISBN 978-3-540-60221-7.

संदर्भ

Carmichael, R. D. (1913), "On the numerical factors of the arithmetic forms αⁿ±βⁿ", Annals of Mathematics, 15 (1/4): 30–70, doi:10.2307/1967797, JSTOR 1967797
Lehmer, D. H. (1930). "An extended theory of Lucas' functions". Annals of Mathematics. 31 (3): 419–448. Bibcode:1930AnMat..31..419L. doi:10.2307/1968235. JSTOR 1968235.
Ward, Morgan (1954). "Prime divisors of second order recurring sequences". Duke Math. J. 21 (4): 607–614. doi:10.1215/S0012-7094-54-02163-8. hdl:10338.dmlcz/137477. MR 0064073.
Somer, Lawrence (1980). "The divisibility properties of primary Lucas Recurrences with respect to primes" (PDF). Fibonacci Quarterly. 18: 316.
Lagarias, J. C. (1985). "The set of primes dividing Lucas Numbers has density 2/3". Pac. J. Math. 118 (2): 449–461. doi:10.2140/pjm.1985.118.449. MR 0789184.
Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. Vol. 126 (2nd ed.). Birkhäuser. pp. 107–121. ISBN 0-8176-3743-5.
Ribenboim, Paulo; McDaniel, Wayne L. (1996). "The square terms in Lucas Sequences". J. Number Theory. 58 (1): 104–123. doi:10.1006/jnth.1996.0068.
Joye, M.; Quisquater, J.-J. (1996). "Efficient computation of full Lucas sequences" (PDF). Electronics Letters. 32 (6): 537–538. Bibcode:1996ElL....32..537J. doi:10.1049/el:19960359. Archived from the original (PDF) on 2015-02-02.
Ribenboim, Paulo (1996). The New Book of Prime Number Records (eBook ed.). Springer-Verlag, New York. doi:10.1007/978-1-4612-0759-7. ISBN 978-1-4612-0759-7.
Ribenboim, Paulo (2000). My Numbers, My Friends: Popular Lectures on Number Theory. New York: Springer-Verlag. pp. 1–50. ISBN 0-387-98911-0.
Luca, Florian (2000). "Perfect Fibonacci and Lucas numbers". Rend. Circ Matem. Palermo. 49 (2): 313–318. doi:10.1007/BF02904236. S2CID 121789033.
Yabuta, M. (2001). "A simple proof of Carmichael's theorem on primitive divisors" (PDF). Fibonacci Quarterly. 39: 439–443.
Benjamin, Arthur T.; Quinn, Jennifer J. (2003). Proofs that Really Count: The Art of Combinatorial Proof. Dolciani Mathematical Expositions. Vol. 27. Mathematical Association of America. p. 35. ISBN 978-0-88385-333-7.
Lucas sequence at Encyclopedia of Mathematics.
Weisstein, Eric W. "Lucas Sequence". MathWorld.
Wei Dai. "Lucas Sequences in Cryptography".

[1] For such relations and divisibility properties, see (Carmichael 1913), (Lehmer 1930) or (Ribenboim 1996, 2.IV).

[Yabuta-2] 2.0 ^2.1 Yabuta, M (2001). "आदिम भाजक पर कारमाइकल के प्रमेय का एक सरल प्रमाण" (PDF). Fibonacci Quarterly. 39: 439–443. Retrieved 4 October 2018.

[3] Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M.; Mignotte, Maurice (2001). "लुकास और लेहमर संख्याओं के आदिम भाजक का अस्तित्व" (PDF). J. Reine Angew. Math. 2001 (539): 75–122. doi:10.1515/crll.2001.080. MR 1863855. S2CID 122969549.

[BLS75-4] John Brillhart; Derrick Henry Lehmer; John Selfridge (April 1975). "New Primality Criteria and Factorizations of 2^m ± 1". Mathematics of Computation. 29 (130): 620–647. doi:10.1090/S0025-5718-1975-0384673-1. JSTOR 2005583.

[5] P. J. Smith; M. J. J. Lennon (1993). "LUC: A new public key system". Proceedings of the Ninth IFIP Int. Symp. On Computer Security: 103–117. CiteSeerX 10.1.1.32.1835.

[6] D. Bleichenbacher; W. Bosma; A. K. Lenstra (1995). "लुकास-आधारित क्रिप्टोसिस्टम पर कुछ टिप्पणियाँ" (PDF). Lecture Notes in Computer Science. 963: 386–396. doi:10.1007/3-540-44750-4_31. ISBN 978-3-540-60221-7.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 2: / Line 2: @@
 : <math>x_n = P \cdot x_{n - 1} - Q \cdot x_{n - 2}</math>
-जहाँ <math>P</math> और <math>Q</math> निश्चित [[पूर्णांक]] होता हैं। इस पुनरावृत्ति संबंध को संतुष्ट करने वाले किसी भी अनुक्रम को लुकास अनुक्रमों <math>U_n(P, Q)</math> और <math>V_n(P, Q)</math>के [[रैखिक संयोजन]] के रूप में प्रदर्शित किया जा सकता है।
+जहाँ <math>P</math> और <math>Q</math> निश्चित [[पूर्णांक]] होता हैं। इस पुनरावृत्ति संबंध को सरल करने वाले किसी भी अनुक्रम को लुकास अनुक्रमों <math>U_n(P, Q)</math> और <math>V_n(P, Q)</math>के [[रैखिक संयोजन]] के रूप में प्रदर्शित किया जा सकता है।
 अधिक सामान्यतः, लुकास अनुक्रम <math>U_n(P, Q)</math> और <math>V_n(P, Q)</math> में [[बहुपद]] के अनुक्रम का प्रतिनिधित्व <math>P</math> और <math>Q</math> पूर्णांक गुणांक के साथ करते हैं।
-लुकास अनुक्रमों के प्रसिद्ध उदाहरणों में [[फाइबोनैचि संख्या]]एं, मेरसेन संख्याएं, पेल संख्याएं, लुकास संख्याएं, जैकबस्टल संख्याएं और फर्मेट संख्याओं का श्रेष्ट समुच्चय सम्मिलित होता हैं (नीचे देखें)। लुकास अनुक्रमों का नाम [[फ्रांस]] के गणितज्ञ एडवर्ड लुकास के नाम पर रखा गया था।
+लुकास अनुक्रमों के प्रसिद्ध उदाहरणों में [[फाइबोनैचि संख्या]]एं, मेरसेन संख्याएं, पेल संख्याएं, लुकास संख्याएं, जैकबस्टल संख्याएं और फर्मेट संख्याओं का श्रेष्ट समुच्चय सम्मिलित होता हैं (नीचे देखें)। इस प्रकार लुकास अनुक्रमों का नाम [[फ्रांस]] के गणितज्ञ एडवर्ड लुकास के नाम पर रखा गया था।
 == पुनरावृत्ति संबंध ==
@@ Line 73: / Line 73: @@
 :<math>a b = \frac{1}{4}(P^2 - D) = Q\, ,</math>
 :<math>a - b = \sqrt{D}\, .</math>
-ध्यान दें कि क्रम <math>a^n</math> और क्रम <math>b^n</math> पुनरावृत्ति संबंध को भी संतुष्ट करते हैं। यघपि ये पूर्णांक अनुक्रम नहीं हो सकते हैं।
+ध्यान दें कि क्रम <math>a^n</math> और क्रम <math>b^n</math> पुनरावृत्ति संबंध को भी सरल करते हैं। यघपि ये पूर्णांक अनुक्रम नहीं हो सकते हैं।
 === विशिष्ट मूल ===
@@ Line 104: / Line 104: @@
 === पेल समीकरण ===
-कब <math>Q=\pm 1</math>, लुकास अनुक्रम <math>U_n(P, Q)</math> और <math>V_n(P, Q)</math> कुछ [[पेल समीकरण]] को संतुष्ट करें:
+कब <math>Q=\pm 1</math>, लुकास अनुक्रम <math>U_n(P, Q)</math> और <math>V_n(P, Q)</math> कुछ [[पेल समीकरण]] को सरल करें:
 :<math>V_n(P,1)^2 - D\cdot U_n(P,1)^2 = 4,</math>
 :<math>V_{2n}(P,-1)^2 - D\cdot U_{2n}(P,-1)^2 = 4,</math>
@@ Line 120: / Line 120: @@
 === अन्य संबंध ===
-लुकास अनुक्रमों की स्थिति उन संबंधों को संतुष्ट करती हैं जो फाइबोनैचि संख्याओं के मध्य <math>F_n=U_n(1,-1)</math> और लुकास संख्याएँ <math>L_n=V_n(1,-1)</math> के सामान्यीकरण होता है। उदाहरण के लिए:
+लुकास अनुक्रमों की स्थिति उन संबंधों को सरल करती हैं जो फाइबोनैचि संख्याओं के मध्य <math>F_n=U_n(1,-1)</math> और लुकास संख्याएँ <math>L_n=V_n(1,-1)</math> के सामान्यीकरण होता है। उदाहरण के लिए:
 :<math>
 \begin{array}{r|l}
@@ Line 157: / Line 157: @@
 === विभाज्यता गुण ===
-परिणामों में सम्मिलित <math>U_{km}(P,Q)</math><math>U_m(P,Q)</math> का गुणज होता है, अर्थात्, अनुक्रम <math>(U_m(P,Q))_{m\ge1}</math>एक [[विभाज्यता क्रम]] होता है। इसका तात्पर्य, विशेष रूप से, जब <math>U_n(P,Q)</math> मात्र तभी [[अभाज्य संख्या]] हो सकती है जब n अभाज्य हो। अन्य परिणाम [[वर्ग द्वारा घातांक]] का अनुरूप होता है जो शीघ्रता से गणना की अनुमति देता है <math>U_n(P,Q)</math> n के बड़े मानों के लिए होता है।इसके अतिरिक्त, यदि <math>\gcd(P,Q)=1</math> होता है, तब <math>(U_m(P,Q))_{m\ge1}</math> विभाज्यता क्रम होता है।
+परिणामों में सम्मिलित <math>U_{km}(P,Q)</math><math>U_m(P,Q)</math> का गुणज होता है, अर्थात्, अनुक्रम <math>(U_m(P,Q))_{m\ge1}</math>एक [[विभाज्यता क्रम]] होता है। इसका तात्पर्य, विशेष रूप से, जब <math>U_n(P,Q)</math> मात्र तभी [[अभाज्य संख्या]] हो सकती है जब n अभाज्य हो। इस प्रकार अन्य परिणाम [[वर्ग द्वारा घातांक]] का अनुरूप होता है जो शीघ्रता से गणना की अनुमति देता है जों <math>U_n(P,Q)</math> n के बड़े मानों के लिए होता है।इसके अतिरिक्त, यदि <math>\gcd(P,Q)=1</math> होता है, तब <math>(U_m(P,Q))_{m\ge1}</math> विभाज्यता क्रम होता है।
 अन्य विभाज्यता गुण इस प्रकार हैं:<ref>For such relations and divisibility properties, see {{harv|Carmichael|1913}}, {{harv|Lehmer|1930}} or {{harv|Ribenboim|1996|loc=2.IV}}.</ref>
@@ Line 270: / Line 270: @@
 * लुकास अनुक्रमों का उपयोग संभाव्य लुकास स्यूडोअभाज्य परीक्षणों में किया जाता है, जो सामान्यतः प्रयोग किए जाने वाले बैली-पीएसडब्ल्यू प्रारंभिक परीक्षण का भाग होता हैं।
 * लुकास अनुक्रमों का उपयोग कुछ प्रारंभिक प्रमाण विधियों में किया जाता है, जिनमें लुकास-लेहमर-रीज़ल परीक्षण, और N+1और संकर N−1/N+1 विधियां जैसे ब्रिलहार्ट-लेहमर-सेल्फ्रिज 1975 सम्मिलित होता हैं।<ref name="BLS75">{{ cite journal|author=John Brillhart|author2=Derrick Henry Lehmer|author3-link=John Selfridge|author3=John Selfridge|title=New Primality Criteria and Factorizations of 2<sup>m</sup> ± 1|journal=Mathematics of Computation |volume=29|number=130|date=April 1975|pages=620–647|jstor=2005583|doi=10.1090/S0025-5718-1975-0384673-1|author-link=John Brillhart|author2-link=Derrick Henry Lehmer|doi-access=free}}</ref>
-* एलयूसी लुकास अनुक्रमों पर आधारित [[सार्वजनिक-कुंजी क्रिप्टोसिस्टम|सार्वजनिक-कुंजी क्रिप्टोप्रणाली]] है<ref>{{cite journal |author1=P. J. Smith |author2=M. J. J. Lennon |title=LUC: A new public key system |journal=Proceedings of the Ninth IFIP Int. Symp. On Computer Security |year=1993 |pages=103–117 |citeseerx=10.1.1.32.1835 }}</ref> जो [[एलगमाल]] (LUCELG), डिफी-हेलमैन (LUCDIF), और RSA (कलन विधि) (LUCRSA) के एनालॉग्स को प्रयुक्त करता है। एलयूसी में संदेश के कूटलेखन की गणना आरएसए या डिफी-हेलमैन जैसे [[मॉड्यूलर घातांक]] का उपयोग करने के अतिरिक्त, कुछ लुकास अनुक्रम के शब्द के रूप में की जाती है। यघपि, ब्लेइचेनबैकर एट अल द्वारा पेपर <ref>{{cite journal |author1=D. Bleichenbacher |author2=W. Bosma |author3=A. K. Lenstra |title=लुकास-आधारित क्रिप्टोसिस्टम पर कुछ टिप्पणियाँ|journal=[[Lecture Notes in Computer Science]] |volume=963 |year=1995 |pages=386–396 |doi=10.1007/3-540-44750-4_31 |isbn=978-3-540-60221-7 |url=http://www.math.ru.nl/~bosma/pubs/CRYPTO95.pdf|doi-access=free }}</ref> प्रदर्शित करता है कि मॉड्यूलर घातांक पर आधारित क्रिप्टोप्रणाली पर एलयूसी के कई कथित सुरक्षा लाभ या तो उपस्थिति नहीं होते हैं, या उतने पर्याप्त नहीं होते हैं जितना दावा किया जाता है।
+* एलयूसी लुकास अनुक्रमों पर आधारित [[सार्वजनिक-कुंजी क्रिप्टोसिस्टम|सार्वजनिक-कुंजी क्रिप्टोप्रणाली]] है<ref>{{cite journal |author1=P. J. Smith |author2=M. J. J. Lennon |title=LUC: A new public key system |journal=Proceedings of the Ninth IFIP Int. Symp. On Computer Security |year=1993 |pages=103–117 |citeseerx=10.1.1.32.1835 }}</ref> जो [[एलगमाल]] (LUCELG), डिफी-हेलमैन (LUCDIF), और RSA (कलन विधि) (LUCRSA) के एनालॉग्स को प्रयुक्त करता है। एलयूसी में संदेश के कूटलेखन की गणना आरएसए या डिफी-हेलमैन जैसे [[मॉड्यूलर घातांक]] का उपयोग करने के अतिरिक्त, कुछ लुकास अनुक्रम के शब्द के रूप में की जाती है। यघपि, ब्लेइचेनबैकर एट अल द्वारा पेपर <ref>{{cite journal |author1=D. Bleichenbacher |author2=W. Bosma |author3=A. K. Lenstra |title=लुकास-आधारित क्रिप्टोसिस्टम पर कुछ टिप्पणियाँ|journal=[[Lecture Notes in Computer Science]] |volume=963 |year=1995 |pages=386–396 |doi=10.1007/3-540-44750-4_31 |isbn=978-3-540-60221-7 |url=http://www.math.ru.nl/~bosma/pubs/CRYPTO95.pdf|doi-access=free }}</ref> प्रदर्शित करता है कि मॉड्यूलर घातांक पर आधारित क्रिप्टोप्रणाली पर एलयूसी के कई कथित सुरक्षा लाभ या तो उपस्थिति नहीं होते हैं, या उतने पर्याप्त नहीं होते हैं जितना माना जाता है।
 ==यह भी देखें==

Anonymous

Search

लुकास अनुक्रम: Difference between revisions

Namespaces

More

Page actions

Revision as of 12:38, 14 July 2023

Contents

पुनरावृत्ति संबंध

उदाहरण