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

Revision as of 17:47, 12 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^{n}={\frac {V_{n}+U_{n}{\sqrt {D}}}{2}}

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

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

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{ and }}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 विभाजित होता है $U_{n}$ हरके लिए $n>1$ .
यदि p विषम अभाज्य है और P को विभाजित करता है लेकिन Q को नहीं, तो p विभाजित करता है $U_{n}$ यदि और केवल यदि n सम है।
यदि p विषम अभाज्य है और P को नहीं बल्कि Q को विभाजित करता है, तो p कभी भी विभाजित नहीं होता है $U_{n}$ के लिए $n=1,2,\ldots$ .
यदि p विषम अभाज्य है और PQ को नहीं बल्कि D को विभाजित करता है, तो p विभाजित होता है $U_{n}$ यदि और केवल यदि p, n को विभाजित करता है।
यदि p विषम अभाज्य है और PQD को विभाजित नहीं करता है, तो p विभाजित होता है $U_{l}$ , कहाँ $l=p-\left({\tfrac {D}{p}}\right)$ .

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

लुकास अनुक्रम में किसी पद का अभाज्य कारक जो अनुक्रम में किसी भी पहले के पद को विभाजित नहीं करता है उसे आदिम कहा जाता है। कारमाइकल के प्रमेय में कहा गया है कि लुकास अनुक्रम में सभी लेकिन सीमित रूप से कई शब्दों में आदिम अभाज्य कारक होता है।^[2] दरअसल, कारमाइकल (1913) ने दिखाया कि यदि डी सकारात्मक है और एन 1, 2 या 6 नहीं है, तो $U_{n}$ आदिम अभाज्य कारक है. मामले में डी नकारात्मक है, बिलु, हनरोट, वाउटियर और मिग्नोटे का गहरा परिणाम है^[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)

: एक्सⁿ + 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

अनुप्रयोग

लुकास अनुक्रमों का उपयोग संभाव्य लुकास स्यूडोप्राइम परीक्षणों में किया जाता है, जो आमतौर पर इस्तेमाल किए जाने वाले बैली-पीएसडब्ल्यू प्राइमलिटी परीक्षण का हिस्सा हैं।
लुकास अनुक्रमों का उपयोग कुछ प्रारंभिक प्रमाण विधियों में किया जाता है, जिनमें लुकास-लेहमर-रीज़ल परीक्षण, और एन+1 और हाइब्रिड एन−1/एन+1 विधियां जैसे ब्रिलहार्ट-लेहमर-सेल्फ्रिज 1975 शामिल हैं।^[4]
LUC लुकास अनुक्रमों पर आधारित सार्वजनिक-कुंजी क्रिप्टोसिस्टम है^[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 7: / Line 7: @@
 अधिक सामान्यतः, लुकास अनुक्रम <math>U_n(P, Q)</math> और <math>V_n(P, Q)</math> में [[बहुपद]]ों के अनुक्रम का प्रतिनिधित्व करते हैं <math>P</math> और <math>Q</math> पूर्णांक गुणांक के साथ.
-लुकास अनुक्रमों के प्रसिद्ध उदाहरणों में [[फाइबोनैचि संख्या]]एं, मेरसेन संख्याएं, पेल संख्याएं, लुकास संख्याएं, जैकबस्टल संख्याएं और फर्मेट संख्याओं का एक सुपरसेट शामिल हैं (नीचे देखें)। लुकास अनुक्रमों का नाम [[फ्रांस]] के गणितज्ञ एडवर्ड लुकास के नाम पर रखा गया है।
+लुकास अनुक्रमों के प्रसिद्ध उदाहरणों में [[फाइबोनैचि संख्या]]एं, मेरसेन संख्याएं, पेल संख्याएं, लुकास संख्याएं, जैकबस्टल संख्याएं और फर्मेट संख्याओं का सुपरसेट शामिल हैं (नीचे देखें)। लुकास अनुक्रमों का नाम [[फ्रांस]] के गणितज्ञ एडवर्ड लुकास के नाम पर रखा गया है।
 == पुनरावृत्ति संबंध ==
@@ Line 68: / Line 68: @@
 लुकास अनुक्रमों के लिए पुनरावृत्ति संबंध का विशिष्ट समीकरण <math>U_n(P,Q)</math> और <math>V_n(P,Q)</math> है:
 :<math>x^2 - Px + Q=0 \,</math>
-<!-- The \, is to keep the formula rendered as PNG instead of HTML. Please don't remove it.-->
+इसमें विवेचक है <math>D = P^2 - 4Q</math> और बहुपद का मूल:
-इसमें विवेचक है <math>D = P^2 - 4Q</math> और एक बहुपद का मूल:
 :<math>a = \frac{P+\sqrt{D}}2\quad\text{and}\quad b = \frac{P-\sqrt{D}}2. \,</math>
 इस प्रकार:
@@ Line 86: / Line 85: @@
 :<math>U_n = \frac{a^n-b^n}{a-b} = \frac{a^n-b^n}{ \sqrt{D}}</math>
 :<math>V_n = a^n+b^n \,</math>
-<!-- The \, is to keep the formula rendered as PNG instead of HTML. Please don't remove it.-->
 === दोहराया गया रूट ===
 मामला <math> D=0 </math> बिल्कुल तब होता है जब <math> P=2S \text{ and }Q=S^2</math> कुछ पूर्णांक S के लिए ताकि <math>a=b=S</math>. इस मामले में कोई भी इसे आसानी से पा सकता है
 :<math>U_n(P,Q)=U_n(2S,S^2) = nS^{n-1}\,</math>
 :<math>V_n(P,Q)=V_n(2S,S^2)=2S^n.\,</math>
 == गुण ==
@@ Line 108: / Line 103: @@
 \sum_{n\ge 0} V_n(P,Q)z^n = \frac{2-Pz}{1-Pz+Qz^2}.
 </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>
 :<math>V_{2n+1}(P,-1)^2 - D\cdot U_{2n+1}(P,-1)^2 = -4.</math>
 === विभिन्न मापदंडों के साथ अनुक्रमों के बीच संबंध ===
 *किसी भी संख्या c के लिए, अनुक्रम <math>U_n(P', Q')</math> और <math>V_n(P', Q')</math> साथ
 ::<math> P' = P + 2c  </math>
@@ Line 128: / Line 119: @@
 :: <math>U_n(cP,c^2Q) = c^{n-1}\cdot U_n(P,Q),</math>
 :: <math>V_n(cP,c^2Q) = c^n\cdot V_n(P,Q).</math>
 === अन्य संबंध ===
 लुकास अनुक्रमों की शर्तें उन संबंधों को संतुष्ट करती हैं जो फाइबोनैचि संख्याओं के बीच के सामान्यीकरण हैं <math>F_n=U_n(1,-1)</math> और लुकास संख्याएँ <math>L_n=V_n(1,-1)</math>. उदाहरण के लिए:
 :<math>
@@ Line 167: / Line 156: @@
 \end{array}
 </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>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>\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>
 * अगर <math>n \mid m</math> तो [[समता (गणित)]] है <math>V_m</math> विभाजित <math>V_n</math>.
-*मान लीजिए N, 2Q के सापेक्ष एक अभाज्य पूर्णांक है। यदि सबसे छोटा धनात्मक पूर्णांक r जिसके लिए N विभाजित होता है <math>U_r</math> मौजूद है, तो n का वह सेट जिसके लिए N विभाजित होता है <math>U_n</math> बिल्कुल r के गुणजों का समुच्चय है।
+*मान लीजिए N, 2Q के सापेक्ष अभाज्य पूर्णांक है। यदि सबसे छोटा धनात्मक पूर्णांक r जिसके लिए N विभाजित होता है <math>U_r</math> मौजूद है, तो n का वह सेट जिसके लिए N विभाजित होता है <math>U_n</math> बिल्कुल r के गुणजों का समुच्चय है।
 * यदि P और Q समता (गणित) हैं, तो <math>U_n, V_n</math> को छोड़कर सदैव सम होते हैं <math>U_1</math>.
 * यदि P सम है और Q विषम है, तो समता (गणित) की <math>U_n</math> n और के समान है <math>V_n</math> सदैव सम रहता है.
 * यदि P विषम है और Q सम है, तो <math>U_n, V_n</math> के लिए हमेशा अजीब होते हैं <math>n=1, 2, \ldots</math>.
 * यदि P और Q विषम हैं, तो <math>U_n, V_n</math> सम हैं यदि और केवल यदि n, 3 का गुणज है।
-* यदि p एक विषम अभाज्य है, तो <math>U_p\equiv\left(\tfrac{D}{p}\right), V_p\equiv P\pmod{p}</math> (लेजेन्ड्रे प्रतीक देखें)।
+* यदि p विषम अभाज्य है, तो <math>U_p\equiv\left(\tfrac{D}{p}\right), V_p\equiv P\pmod{p}</math> (लेजेन्ड्रे प्रतीक देखें)।
-* यदि p एक विषम अभाज्य है और P और Q को विभाजित करता है, तो p विभाजित होता है <math>U_n</math> हरएक के लिए <math>n>1</math>.
+* यदि p विषम अभाज्य है और P और Q को विभाजित करता है, तो p विभाजित होता है <math>U_n</math> हरके लिए <math>n>1</math>.
-* यदि p एक विषम अभाज्य है और P को विभाजित करता है लेकिन Q को नहीं, तो p विभाजित करता है <math>U_n</math> यदि और केवल यदि n सम है।
+* यदि p विषम अभाज्य है और P को विभाजित करता है लेकिन Q को नहीं, तो p विभाजित करता है <math>U_n</math> यदि और केवल यदि n सम है।
-* यदि p एक विषम अभाज्य है और P को नहीं बल्कि Q को विभाजित करता है, तो p कभी भी विभाजित नहीं होता है <math>U_n</math> के लिए <math>n=1, 2, \ldots</math>.
+* यदि p विषम अभाज्य है और P को नहीं बल्कि Q को विभाजित करता है, तो p कभी भी विभाजित नहीं होता है <math>U_n</math> के लिए <math>n=1, 2, \ldots</math>.
-* यदि p एक विषम अभाज्य है और PQ को नहीं बल्कि D को विभाजित करता है, तो p विभाजित होता है <math>U_n</math> यदि और केवल यदि p, n को विभाजित करता है।
+* यदि p विषम अभाज्य है और PQ को नहीं बल्कि D को विभाजित करता है, तो p विभाजित होता है <math>U_n</math> यदि और केवल यदि p, n को विभाजित करता है।
-* यदि p एक विषम अभाज्य है और PQD को विभाजित नहीं करता है, तो p विभाजित होता है <math>U_l</math>, कहाँ <math>l=p-\left(\tfrac{D}{p}\right)</math>.
+* यदि p विषम अभाज्य है और PQD को विभाजित नहीं करता है, तो p विभाजित होता है <math>U_l</math>, कहाँ <math>l=p-\left(\tfrac{D}{p}\right)</math>.
 अंतिम तथ्य फ़र्मेट के छोटे प्रमेय का सामान्यीकरण करता है। इन तथ्यों का उपयोग लुकास-लेहमर प्राइमलिटी परीक्षण में किया जाता है।
-अंतिम तथ्य का व्युत्क्रम (तर्क) मान्य नहीं है, जैसे फ़र्मेट के छोटे प्रमेय का व्युत्क्रम मान्य नहीं है। D और विभाजक के सापेक्ष एक भाज्य संख्या n मौजूद है <math>U_l</math>, कहाँ <math>l=n-\left(\tfrac{D}{n}\right)</math>. ऐसे सम्मिश्रण को [[लुकास स्यूडोप्राइम]] कहा जाता है।
+अंतिम तथ्य का व्युत्क्रम (तर्क) मान्य नहीं है, जैसे फ़र्मेट के छोटे प्रमेय का व्युत्क्रम मान्य नहीं है। D और विभाजक के सापेक्ष भाज्य संख्या n मौजूद है <math>U_l</math>, कहाँ <math>l=n-\left(\tfrac{D}{n}\right)</math>. ऐसे सम्मिश्रण को [[लुकास स्यूडोप्राइम]] कहा जाता है।
-लुकास अनुक्रम में किसी पद का एक अभाज्य कारक जो अनुक्रम में किसी भी पहले के पद को विभाजित नहीं करता है उसे आदिम कहा जाता है।
+लुकास अनुक्रम में किसी पद का अभाज्य कारक जो अनुक्रम में किसी भी पहले के पद को विभाजित नहीं करता है उसे आदिम कहा जाता है।
-कारमाइकल के प्रमेय में कहा गया है कि लुकास अनुक्रम में सभी लेकिन सीमित रूप से कई शब्दों में एक आदिम अभाज्य कारक होता है।<ref name=Yabuta>{{cite journal |last1=Yabuta |first1=M |title=आदिम भाजक पर कारमाइकल के प्रमेय का एक सरल प्रमाण|journal=Fibonacci Quarterly |date=2001 |volume=39 |pages=439–443 |url=http://www.fq.math.ca/Scanned/39-5/yabuta.pdf |access-date=4 October 2018}}</ref> दरअसल, कारमाइकल (1913) ने दिखाया कि यदि डी सकारात्मक है और एन 1, 2 या 6 नहीं है, तो <math>U_n</math> एक आदिम अभाज्य कारक है. मामले में डी नकारात्मक है, बिलु, हनरोट, वाउटियर और मिग्नोटे का गहरा परिणाम है<ref>{{cite journal | first1=Yuri | last1=Bilu | first2=Guillaume | last2=Hanrot | first3=Paul M. | last3=Voutier | first4=Maurice | last4=Mignotte | title=लुकास और लेहमर संख्याओं के आदिम भाजक का अस्तित्व| journal = J. Reine Angew. Math. | year=2001 | volume=2001 | issue=539 |pages= 75–122 | mr=1863855 | doi=10.1515/crll.2001.080| s2cid=122969549 | url=https://hal.inria.fr/inria-00072867/file/RR-3792.pdf }}
+कारमाइकल के प्रमेय में कहा गया है कि लुकास अनुक्रम में सभी लेकिन सीमित रूप से कई शब्दों में आदिम अभाज्य कारक होता है।<ref name=Yabuta>{{cite journal |last1=Yabuta |first1=M |title=आदिम भाजक पर कारमाइकल के प्रमेय का एक सरल प्रमाण|journal=Fibonacci Quarterly |date=2001 |volume=39 |pages=439–443 |url=http://www.fq.math.ca/Scanned/39-5/yabuta.pdf |access-date=4 October 2018}}</ref> दरअसल, कारमाइकल (1913) ने दिखाया कि यदि डी सकारात्मक है और एन 1, 2 या 6 नहीं है, तो <math>U_n</math> आदिम अभाज्य कारक है. मामले में डी नकारात्मक है, बिलु, हनरोट, वाउटियर और मिग्नोटे का गहरा परिणाम है<ref>{{cite journal | first1=Yuri | last1=Bilu | first2=Guillaume | last2=Hanrot | first3=Paul M. | last3=Voutier | first4=Maurice | last4=Mignotte | title=लुकास और लेहमर संख्याओं के आदिम भाजक का अस्तित्व| journal = J. Reine Angew. Math. | year=2001 | volume=2001 | issue=539 |pages= 75–122 | mr=1863855 | doi=10.1515/crll.2001.080| s2cid=122969549 | url=https://hal.inria.fr/inria-00072867/file/RR-3792.pdf }}
-</ref> दर्शाता है कि यदि n > 30, तो <math>U_n</math> एक आदिम अभाज्य कारक है और सभी मामलों को निर्धारित करता है <math>U_n</math> कोई आदिम अभाज्य गुणनखंड नहीं है.
+</ref> दर्शाता है कि यदि n > 30, तो <math>U_n</math> आदिम अभाज्य कारक है और सभी मामलों को निर्धारित करता है <math>U_n</math> कोई आदिम अभाज्य गुणनखंड नहीं है.
 == विशिष्ट नाम ==
@@ Line 285: / Line 272: @@
 |}
+== अनुप्रयोग ==
-==अनुप्रयोग==
 * लुकास अनुक्रमों का उपयोग संभाव्य लुकास स्यूडोप्राइम परीक्षणों में किया जाता है, जो आमतौर पर इस्तेमाल किए जाने वाले बैली-पीएसडब्ल्यू प्राइमलिटी परीक्षण का हिस्सा हैं।
 * लुकास अनुक्रमों का उपयोग कुछ प्रारंभिक प्रमाण विधियों में किया जाता है, जिनमें लुकास-लेहमर-रीज़ल परीक्षण, और एन+1 और हाइब्रिड एन−1/एन+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>
-* LUC लुकास अनुक्रमों पर आधारित एक [[सार्वजनिक-कुंजी क्रिप्टोसिस्टम]] है<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> दर्शाता है कि मॉड्यूलर एक्सपोनेंटिएशन पर आधारित क्रिप्टोसिस्टम पर एलयूसी के कई कथित सुरक्षा लाभ या तो मौजूद नहीं हैं, या उतने पर्याप्त नहीं हैं जितना दावा किया गया है।
+* LUC लुकास अनुक्रमों पर आधारित [[सार्वजनिक-कुंजी क्रिप्टोसिस्टम]] है<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 17:47, 12 July 2023

Contents

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

उदाहरण