प्रिमिटिव रूट मॉड्यूलो n: Difference between revisions

Latest revision as of 17:21, 25 May 2023

मॉड्यूलर अंकगणित में, संख्या $g$ प्रिमिटिव रूट मॉड्यूलो $n$ है $n$ यदि हर नंबर $a$ सह अभाज्य $n$ की शक्ति से सर्वांगसमता संबंध है $g$ मापांक $n$ वह है, $g$ प्रिमिटिव रूट मॉड्यूलो है $n$ यदि प्रत्येक पूर्णांक के लिए $a$ कोप्राइम $n$ , कुछ पूर्णांक है $k$ जिसके लिए $g$ ^$k$ ≡ $a$ (mod n). ऐसा मान $k$ का सूचकांक या असतत लघुगणक कहा जाता है $a$ आधार के लिए $g$ मापांक $n$ . इसलिए $g$ प्रिमिटिव रूट मॉड्यूलो है $n$ यदि और केवल यदि $g$ पूर्णांक मॉड्यूलो n पूर्णांक मॉड्यूलो के गुणक समूह का जेनरेटिंग समुच्चय $n$ है।

कार्ल फ्रेडरिक गॉस ने प्रिमिटिव रूट को अंकगणितीय शोध (1801) के अनुच्छेद 57 में परिभाषित किया, जहां उन्होंने इस शब्द को गढ़ने का श्रेय यूलर को दिया। अनुच्छेद 56 में उन्होंने कहा कि जोहान हेनरिक लैम्बर्ट और यूलर उनके बारे में जानते थे, लेकिन वह पहले व्यक्ति थे जिन्होंने कठोर रूप से प्रदर्शित किया कि अभाज्य संख्या के लिए प्रिमिटिव रूट उपस्थित हैं। $n$ वास्तव में, विवादों में दो प्रमाण होते हैं: अनुच्छेद 54 में एक गैर-रचनात्मक अस्तित्व प्रमेय है, जबकि अनुच्छेद 55 में प्रमाण रचनात्मक प्रमाण है।

प्रारंभिक उदाहरण

नंबर 3 प्रिमिटिव रूट मोडुलो 7 है^[1] क्योंकि

{\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\\3^{7}&=&3^{6}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\\end{array}}

यहाँ हम देखते हैं कि 3 का क्रम (समूह सिद्धांत) 3^k मॉड्यूलो 7 और 6 है। अवधि में अवशेष, जो 3, 2, 6, 4, 5, 1 हैं, सभी अशून्य अवशेषों मॉड्यूलो 7 की पुनर्व्यवस्था बनाते हैं, जिसका अर्थ है कि 3 वास्तव में प्रिमिटिव रूट मॉड्यूलो 7 है यह इस तथ्य से निकला है कि अनुक्रम ( $g$ ^$k$ मोडुलो $n$ ) के कुछ मान के बाद हमेशा दोहराता है $k$ , मॉड्यूल के बाद से $n$ मूल्यों की सीमित संख्या उत्पन्न करता है। यदि $g$ प्रिमिटिव रूट मॉड्यूलो है $n$ और $n$ प्रधान है, तो पुनरावृत्ति की अवधि है $n$ − 1. इस तरह से बनाए गए क्रमपरिवर्तन (और उनके वृत्ताकार बदलाव) कोस्टास सरणी वेल्च के रूप में दिखाए गए हैं।

परिभाषा

यदि $n$ धनात्मक पूर्णांक है, 0 से पूर्णांक $n$ − 1 जो कि कोप्राइम हैं $n$ (या समतुल्य रूप से, सर्वांगसमता वर्ग सह अभाज्य हैं $n$ ) गुणन मॉड्यूलर अंकगणित के साथ समूह (गणित) बनाते हैं $n$ ऑपरेशन के रूप में; इसे पूर्णांकों के गुणक समूह n द्वारा निरूपित किया जाता है $\mathbb {Z}$ ^×
_$n$, और इकाइयों का समूह कहा जाता है $n$ , या प्रिमिटिव क्लास मोडुलो का समूह $n$ . जैसा कि लेख में बताया गया है कि पूर्णांकों का गुणक समूह मॉड्यूल n पूर्णांक मॉड्यूलो का गुणक समूह $n$ , यह गुणात्मक समूह ( $\mathbb {Z}$ ^×
_$n$) चक्रीय समूह है यदि और केवल यदि $n$ 2, 4 के बराबर है, $p k$ , या 2 $p k$ कहाँ $p k$ एक विषम अभाज्य संख्या की शक्ति है।^[2]^[3] कब (और केवल कब) यह समूह $\mathbb {Z}$ ^×
_$n$ चक्रीय है, इस चक्रीय समूह के समूह के जनरेटिंग समुच्चय को प्रिमिटिव रूट मॉड्यूल कहा जाता है $n$ ^[4] (या पूर्ण भाषा में एकता मॉड्यूलो की प्रिमिटिव रूट $n$ , एकता मॉड्यूल n बहुपद समीकरण x की रूट के मौलिक समाधान के रूप में अपनी भूमिका पर बल देते हुए^$m$
− 1 वलय में $\mathbb {Z}$ _$n$), या बस का एक आदिम तत्व $\mathbb {Z}$ ^×
_$n$ है।

जब $\mathbb {Z}$ ^×
_$n$ गैर-चक्रीय है, ऐसे आदिम तत्व मॉड $n$ उपस्थित नहीं है। इसके बजाय, प्रत्येक प्रमुख घटक $n$ की अपनी उप-प्रिमिटिव रूट हैं (देखें $15$ नीचे दिए गए उदाहरणों में)

किसी के लिए $n$ (की भी होगी या नहीं $\mathbb {Z}$ ^×
_$n$ चक्रीय है), का क्रम $\mathbb {Z}$ ^×
_$n$ यूलर के कुल फलन द्वारा दिया गया है $φ$ ( $n$ ) (sequence A000010 in the OEIS). और फिर, यूलर प्रमेय यह कहता है $a$ ^{$φ$ ( $n$ )} ≡ 1 (mod $n$ ) हर एक के लिए $a$ कोप्राइम $n$ ; की सबसे कम शक्ति $a$ जो 1 मॉड्यूलो के अनुरूप है $n$ का गुणन क्रम कहा जाता है $a$ मापांक $n$ . विशेष रूप से, के लिए $a$ प्रिमिटिव रूट मॉड्यूल होना $n$ , $a$ ^{$φ$ ( $n$ )} की सबसे छोटी शक्ति होनी चाहिए $a$ जो 1 मॉड्यूलो के अनुरूप $n$ है।

उदाहरण

उदाहरण के लिए, यदि $n$ = 14 फिर के तत्व $\mathbb {Z}$ ^×
_$n$ सर्वांगसमता वर्ग {1, 3, 5, 9, 11, 13} हैं; वहाँ हैं $φ$ (14) = 6 उनमें से। यहाँ उनकी शक्तियों की तालिका 14 मॉड्यूल है:

x     x, x2, x3, ... (mod 14)
 1 :   1
 3 :   3,  9, 13, 11,  5,  1 
 5 :   5, 11, 13,  9,  3,  1
 9 :   9, 11,  1
11 :  11,  9,  1
13 :  13,  1

1 का क्रम 1 है, 3 और 5 का क्रम 6 है, 9 और 11 का क्रम 3 है, और 13 का क्रम 2 है। इस प्रकार, 3 और 5 प्रिमिटिव रूट मॉड्यूलो 14 हैं।

दूसरे उदाहरण के लिए आइए $n$ = 15 . के तत्व $\mathbb {Z}$ ^×
₁₅ सर्वांगसमता वर्ग {1, 2, 4, 7, 8, 11, 13, 14} हैं; वहाँ हैं $φ$ (15) = 8 उनमें से

 x     x, x2, x3, ... (mod 15)
 1 :   1
 2 :   2,  4,  8, 1 
 4 :   4,  1
 7 :   7,  4, 13, 1
 8 :   8,  4,  2, 1
11 :  11,  1
13 :  13,  4,  7, 1
14 :  14,  1

चूँकि ऐसी कोई संख्या नहीं है जिसका क्रम 8 है, कोई प्रिमिटिव रूट मॉड्यूलो 15 नहीं है। वास्तव में, $λ$ (15) = 4, कहाँ $λ$ कारमाइकल फलन है। (sequence A002322 in the OEIS)

प्रिमिटिव रूट की तालिका

नंबर $n$ जिनकी मूल रूट आकार की होती है

n\in \{1,2,4,p^{k},2\cdot p^{k}\;\;|\;\;2<p{\text{ prime}};\;k\in \mathbb {N} \},

= {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...} ^[5]

ये नंबर हैं $n$ साथ $\varphi (n)=\lambda (n),$ क्रम में भी रखा A033948 OEIS में।

निम्न तालिका प्रिमिटिव रूट मॉड्यूलो को सूचीबद्ध करती है $n$ तक $n=31$ :

$n$	प्रिमिटिव रूट मॉड्यूलो $n$	क्रम $\varphi (n),$ (OEIS: A000010)	एक्सपोनेंट $\lambda (n),$ (OEIS: A002322)
1	0	1	1
2	1	1	1
3	2	2	2
4	3	2	2
5	2, 3	4	4
6	5	2	2
7	3, 5	6	6
8		4	2
9	2, 5	6	6
10	3, 7	4	4
11	2, 6, 7, 8	10	10
12		4	2
13	2, 6, 7, 11	12	12
14	3, 5	6	6
15		8	4
16		8	4
17	3, 5, 6, 7, 10, 11, 12, 14	16	16
18	5, 11	6	6
19	2, 3, 10, 13, 14, 15	18	18
20		8	4
21		12	6
22	7, 13, 17, 19	10	10
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22	22
24		8	2
25	2, 3, 8, 12, 13, 17, 22, 23	20	20
26	7, 11, 15, 19	12	12
27	2, 5, 11, 14, 20, 23	18	18
28		12	6
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28	28
30		8	4
31	3, 11, 12, 13, 17, 21, 22, 24	30	30

गुण

गॉस सिद्ध हुआ^[6] कि किसी भी अभाज्य संख्या के लिए $p$ (एकमात्र अपवाद के साथ $p$ = 3), इसकी प्रिमिटिव रूट का गुणनफल 1 मॉड्यूल के अनुरूप है $p$ वह सिद्ध भी हुआ^[7] कि किसी भी अभाज्य संख्या के लिए $p$ , इसके आदिम मूलों का योग सर्वांगसम है $μ$ ( $p$ − 1) रूप $p$ , कहाँ $μ$ मोबियस फलन है।

उदाहरण के लिए,

$p$ = 3,	$μ$ (2) = −1.	मूल रूट 2 है
$p$ = 5,	$μ$ (4) = 0.	प्रिमिटिव रूट 2 और 3 हैं।
$p$ = 7,	$μ$ (6) = 1.	प्रिमिटिव रूट 3 और 5 हैं।
$p$ = 31,	$μ$ (30) = −1.	प्रिमिटिव रूट 3, 11, 12, 13, 17, 21, 22 और 24 हैं।

जैसे, बाद की प्रिमिटिव रूट का उत्पाद है $2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}$ , और उनका योग है $123\equiv -1\equiv \mu (31-1){\pmod {31}}$ .

यदि $a$ प्रिमिटिव रूट मॉड्यूलो प्राइम है $p$ , तब $a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$ .

प्रिमिटिव रूट पर आर्टिन का अनुमान बताता है कि दिया हुआ पूर्णांक $a$ जो कि न तो वर्ग संख्या है और न ही -1 प्रिमिटिव रूट मॉडुलो अपरिमित रूप से अनेक अभाज्य संख्या है।

प्रिमिटिव रूट ढूँढना

प्रिमिटिव रूट के मॉड्यूलो की गणना करने के लिए कोई सामान्य सामान्य सूत्र नहीं है $n$ ज्ञात है।^{[lower-alpha 1]}^{[lower-alpha 2]} चुकीं , प्रिमिटिव रूट का पता लगाने की विधियाँ हैं जो सभी उम्मीदवारों को आज़माने की तुलना में तेज़ हैं। यदि किसी संख्या का गुणन क्रम (इसका मरोड़ समूह) $m$ मापांक $n$ यूलर के फाई फलन के बराबर है $\varphi (n)$ (के लिए $\mathbb {Z}$ ^×
_$n$), तो यह प्रिमिटिव रूट है। वास्तव में विलोम सत्य है: यदि $m$ प्रिमिटिव रूट मॉड्यूलो है $n$ , फिर का गुणक क्रम $m$ है $\varphi (n)=\lambda (n)~.$ हम इसका उपयोग उम्मीदवार का परीक्षण करने के लिए कर सकते हैं $m$ यह देखने के लिए कि क्या यह आदिम है।

के लिए $n>1$ सबसे पहले, गणना करें $\varphi (n)~.$ फिर के विभिन्न प्रमुख कारकों का निर्धारण करें $\varphi (n)$ , कहना $p$ ₁, ..., $p k$ . अंत में गणना करें

g^{\varphi (n)/p_{i}}{\bmod {n}}\qquad {\mbox{ for }}i=1,\ldots ,k

मॉड्यूलर घातांक के लिए तेज़ एल्गोरिथम का उपयोग करना जैसे कि वर्ग बनाकर घातांक संख्या $g$ जिसके लिए ये $k$ परिणाम सभी भिन्न हैं 1 से प्रिमिटिव रूट है।

प्रिमिटिव रूट की संख्या मॉड्यूलो $n$ , यदि कोई हो, के बराबर है।^[8]

\varphi \left(\varphi (n)\right)

चूंकि, सामान्य तौर पर, चक्रीय समूह के साथ $r$ तत्व होते हैं $\varphi (r)$ जनरेटर, के साथ $r$ को अभाज्य पूर्णांक होने के नाते $n$ , जो उत्पन्न करता है प्रधान के लिए $n$ , यह बराबर है $\varphi (n-1)$ , और तबसे $n/\varphi (n-1)\in O(\log \log n)$ जेनरेटर {2, ..., के बीच बहुत आम हैं $n$ −1} और इस प्रकार इसे खोजना अपेक्षाकृत सरल है।^[9]

यदि $g$ प्रिमिटिव रूट मॉड्यूलो है $p$ , तब $g$ भी प्रिमिटिव रूट मॉड्यूलो सभी शक्तियां हैं $p k$ जब तक $g$ ^{$p$ −1} ≡ 1 (मॉड $p$ ²); उस स्थिति में, $g$ + $p$ है।^[10]

यदि $g$ प्रिमिटिव रूट मॉड्यूलो है $p k$ , तब $g$ भी सभी छोटी शक्तियों का प्रिमिटिव रूट मोडुलो $p$ है।

यदि $g$ प्रिमिटिव रूट मॉड्यूलो है $p k$ , तो कोई $g$ या $g$ + $p k$ (जो भी विषम हो) प्रिमिटिव रूट मॉड्यूल 2 $p k$ है।^[10]

प्रिमिटिव रूट का पता लगाना $p$ की रूट को खोजने के बराबर भी है ( $p$ − 1) सेंट साइक्लोटोमिक बहुपद मोडुलो $p$ है।

प्रिमिटिव रूट के परिमाण का क्रम

सबसे कम प्रिमिटिव रूट $g p$ मापांक $p$ (श्रेणी 1, 2, ..., में $p$ − 1 ) सामान्यतः छोटा होता है।

ऊपरी सीमा

बर्गेस (1962) सिद्ध हुआ^[11]^[12] कि प्रत्येक ε > 0 के लिए एक है $C$ ऐसा है कि $g_{p}\leq C\,p^{{\frac {1}{4}}+\varepsilon }~.$

एमिल ग्रॉसवाल्ड (1981) ने सिद्ध किया^[11]^[13] कि यदि $p>e^{e^{24}}\approx 10^{11504079571}$ , तब $g_{p}<p^{0.499}~.$

विक्टर शौप (1990, 1992) ने सिद्ध किया,^[14] सामान्यीकृत रीमैन परिकल्पना मानते हुए, कि $g p$ = O(log⁶ $p$ ).

निचली सीमा

फ्रिडलैंडर (1949) और साली (1950) सिद्ध हुए^[11]कि सकारात्मक स्थिरांक है $C$ जैसे कि असीम रूप से कई अभाज्य संख्याओं के लिए $g p$ > $C$ log $p$ .यह सिद्ध किया जा सकता है^[11] प्राथमिक विधि से कि किसी भी सकारात्मक पूर्णांक के लिए $M$ ऐसे अपरिमित रूप से अनेक अभाज्य संख्याएँ $M$ < $g p$ < $p$ − $M$ .है।

अनुप्रयोग

प्रिमिटिव रूट मॉड्यूलो $n$ अधिकांशतः छद्म यादृच्छिक संख्या जनरेटर में प्रयोग किया जाता है^[15] और क्रिप्टोग्राफी, जिसमें डिफी-हेलमैन कुंजी विनिमय योजना शामिल है। प्रसार (ध्वनिकी) आदिम-रूट विसारक संख्या-सैद्धांतिक अवधारणाओं जैसे कि प्रिमिटिव रूट और द्विघात अवशेष पर आधारित हैं।^[16]^[17]

यह भी देखें

डिरिचलेट चरित्र
पूर्ण पश्चाताप प्रधान
विल्सन की प्रमेय गौस.27s सामान्यीकरण|विल्सन की प्रमेय का गॉस का सामान्यीकरण
गुणक क्रम
द्विघात अवशेष
एकता मॉड्यूलो की जड़ n एकता मॉड्यूलो की जड़ $n$

फुटनोट्स

↑ "One of the most important unsolved problems in the theory of finite fields is designing a fast algorithm to construct primitive roots. von zur Gathen & Shparlinski 1998, pp. 15–24
↑ "There is no convenient formula for computing [the least primitive root]." Robbins 2006, p. 159

संदर्भ

↑ Stromquist, Walter. "What are primitive roots?". Mathematics. Bryn Mawr College. Archived from the original on 2017-07-03. Retrieved 2017-07-03.
↑ Weisstein, Eric W. "Modulo Multiplication Group". MathWorld.
↑ Primitive root, Encyclopedia of Mathematics.
↑ Vinogradov 2003, p. 106.
↑ Gauss & Clarke 1986, art 92.
↑ Gauss & Clarke 1986, arts. 80.
↑ Gauss & Clarke 1986, art 81.
↑ (sequence A010554 in the OEIS)
↑ Knuth, Donald E. (1998). Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (3rd ed.). Addison–Wesley. section 4.5.4, page 391.
↑ ^10.0 ^10.1 Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. p. 26. ISBN 978-3-540-55640-4.
↑ ^11.0 ^11.1 ^11.2 ^11.3 Ribenboim, Paulo (1996). The New Book of Prime Number Records. New York, NY: Springer. p. 24. ISBN 978-0-387-94457-9.
↑ Burgess, D. A. (1962). "On Character Sums and Primitive Roots †". Proceedings of the London Mathematical Society (in English). s3-12 (1): 179–192. doi:10.1112/plms/s3-12.1.179.
↑ Grosswald, E. (1981). "On Burgess' Bound for Primitive Roots Modulo Primes and an Application to Γ(p)". American Journal of Mathematics. 103 (6): 1171–1183. doi:10.2307/2374229. ISSN 0002-9327. JSTOR 2374229.
↑ Bach & Shallit 1996, p. 254.
↑ Gentle, James E. (2003). यादृच्छिक संख्या पीढ़ी और मोंटे कार्लो के तरीके (2nd ed.). New York: Springer. ISBN 0-387-00178-6. OCLC 51534945.
↑ Walker, R. (1990). The design and application of modular acoustic diffusing elements (PDF). BBC Research Department (Report). British Broadcasting Corporation. Retrieved 25 March 2019.
↑ Feldman, Eliot (July 1995). "A reflection grating that nullifies the specular reflection: A cone of silence". J. Acoust. Soc. Am. 98 (1): 623–634. Bibcode:1995ASAJ...98..623F. doi:10.1121/1.413656.

स्रोत

Bach, Eric; Shallit, Jeffrey (1996). कुशल एल्गोरिदम. Algorithmic Number Theory. Vol. I. Cambridge, MA: The MIT Press. ISBN 978-0-262-02405-1.

Carella, N. A. (2015). "कम से कम प्रधान आदिम जड़ें". International Journal of Mathematics and Computer Science. 10 (2): 185–194. arXiv:1709.01172.

डिक्विजिशन एरिथमेटिका का अनुवाद गॉस के सिसरोनियन लैटिन से अंग्रेजी और जर्मन में किया गया है। जर्मन संस्करण में संख्या सिद्धांत पर उनके सभी कागजात शामिल हैं: द्विघात पारस्परिकता के सभी प्रमाण, गॉस योग के चिह्न का निर्धारण, द्विवर्गीय पारस्परिकता की जांच, और अप्रकाशित नोट्स।

Gauss, Carl Friedrich (1986) [1801]. अंकगणितीय शोध (in English). Translated by Clarke, Arthur A. (2nd, corrected ed.). New York, NY: Springer. ISBN 978-0-387-96254-2.

Gauss, Carl Friedrich (1965) [1801]. उच्च अंकगणित पर जांच [Studies of Higher Arithmetic] (in Deutsch). Translated by Maser, H. (2nd ed.). New York, NY: Chelsea. ISBN 978-0-8284-0191-3.

Robbins, Neville (2006). शुरुआत संख्या सिद्धांत. Jones & Bartlett Learning. ISBN 978-0-7637-3768-9.

Vinogradov, I.M. (2003). "§ VI Primitive roots and indices". संख्या सिद्धांत के तत्व. Mineola, NY: Dover Publications. pp. 105–121. ISBN 978-0-486-49530-9.

von zur Gathen, Joachim; Shparlinski, Igor (1998). "परिमित क्षेत्रों में गॉस काल के आदेश". Applicable Algebra in Engineering, Communication and Computing. 9 (1): 15–24. CiteSeerX 10.1.1.46.5504. doi:10.1007/s002000050093. MR 1624824. S2CID 19232025.

अग्रिम पठन

Ore, Oystein (1988). Number Theory and Its History. Dover. pp. 284–302. ISBN 978-0-486-65620-5..

बाहरी संबंध

Weisstein, Eric W. "Primitive Root". MathWorld.
Holt. "Quadratic residues and primitive roots". Mathematics. Michigan Tech.
"Primitive roots calculator". BlueTulip.

[8] "One of the most important unsolved problems in the theory of finite fields is designing a fast algorithm to construct primitive roots. von zur Gathen & Shparlinski 1998, pp. 15–24

[9] "There is no convenient formula for computing [the least primitive root]." Robbins 2006, p. 159

[1] Stromquist, Walter. "What are primitive roots?". Mathematics. Bryn Mawr College. Archived from the original on 2017-07-03. Retrieved 2017-07-03.

[2] Weisstein, Eric W. "Modulo Multiplication Group". MathWorld.

[3] Primitive root, Encyclopedia of Mathematics.

[4] Vinogradov 2003, p. 106.

[5] Gauss & Clarke 1986, art 92.

[6] Gauss & Clarke 1986, arts. 80.

[7] Gauss & Clarke 1986, art 81.

[10] (sequence A010554 in the OEIS)

[Knuth-1998-11] Knuth, Donald E. (1998). Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (3rd ed.). Addison–Wesley. section 4.5.4, page 391.

[Cohen1993-12] 10.0 ^10.1 Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Berlin: Springer. p. 26. ISBN 978-3-540-55640-4.

[Ribenboim,_p.24-13] 11.0 ^11.1 ^11.2 ^11.3 Ribenboim, Paulo (1996). The New Book of Prime Number Records. New York, NY: Springer. p. 24. ISBN 978-0-387-94457-9.

[14] Burgess, D. A. (1962). "On Character Sums and Primitive Roots †". Proceedings of the London Mathematical Society (in English). s3-12 (1): 179–192. doi:10.1112/plms/s3-12.1.179.

[15] Grosswald, E. (1981). "On Burgess' Bound for Primitive Roots Modulo Primes and an Application to Γ(p)". American Journal of Mathematics. 103 (6): 1171–1183. doi:10.2307/2374229. ISSN 0002-9327. JSTOR 2374229.

[16] Bach & Shallit 1996, p. 254.

[17] Gentle, James E. (2003). यादृच्छिक संख्या पीढ़ी और मोंटे कार्लो के तरीके (2nd ed.). New York: Springer. ISBN 0-387-00178-6. OCLC 51534945.

[Walker-1990-18] Walker, R. (1990). The design and application of modular acoustic diffusing elements (PDF). BBC Research Department (Report). British Broadcasting Corporation. Retrieved 25 March 2019.

[Feldman-19] Feldman, Eliot (July 1995). "A reflection grating that nullifies the specular reflection: A cone of silence". J. Acoust. Soc. Am. 98 (1): 623–634. Bibcode:1995ASAJ...98..623F. doi:10.1121/1.413656.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[lower-alpha 1]

[lower-alpha 2]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

@@ Line 1: / Line 1: @@
 {{Short description|Modular arithmetic concept}}
 {{DISPLAYTITLE:Primitive root modulo {{mvar|n}}}}
-[[मॉड्यूलर अंकगणित]] में, संख्या {{mvar|g}} आदिम रूट मॉड्यूलो {{mvar|n}} है {{mvar|n}} अगर हर नंबर {{mvar|a}} [[सह अभाज्य]] {{mvar|n}} की शक्ति से [[सर्वांगसमता संबंध]] है {{mvar|g}} मापांक {{mvar|n}} वह है, {{mvar|g}} आदिम रूट मॉड्यूलो है {{mvar|n}} यदि प्रत्येक पूर्णांक के लिए {{mvar|a}} कोप्राइम {{mvar|n}}, कुछ पूर्णांक है {{mvar|k}} जिसके लिए {{mvar|g}}<sup>{{mvar|k}}</sup> ≡ {{mvar|a}} (mod n). ऐसा मान {{mvar|k}} का सूचकांक या [[असतत लघुगणक]] कहा जाता है {{mvar|a}} आधार के लिए {{mvar|g}} मापांक {{mvar|n}}. इसलिए {{mvar|g}} आदिम रूट मॉड्यूलो है {{mvar|n}} अगर और केवल अगर {{mvar|g}} पूर्णांक मॉड्यूलो n पूर्णांक मॉड्यूलो के गुणक समूह का जेनरेटिंग सेट {{mvar|n}} है।
+[[मॉड्यूलर अंकगणित]] में, संख्या {{mvar|g}} प्रिमिटिव रूट मॉड्यूलो {{mvar|n}} है {{mvar|n}} यदि हर नंबर {{mvar|a}} [[सह अभाज्य]] {{mvar|n}} की शक्ति से [[सर्वांगसमता संबंध]] है {{mvar|g}} मापांक {{mvar|n}} वह है, {{mvar|g}} प्रिमिटिव रूट मॉड्यूलो है {{mvar|n}} यदि प्रत्येक पूर्णांक के लिए {{mvar|a}} कोप्राइम {{mvar|n}}, कुछ पूर्णांक है {{mvar|k}} जिसके लिए {{mvar|g}}<sup>{{mvar|k}}</sup> ≡ {{mvar|a}} (mod n). ऐसा मान {{mvar|k}} का सूचकांक या [[असतत लघुगणक]] कहा जाता है {{mvar|a}} आधार के लिए {{mvar|g}} मापांक {{mvar|n}}. इसलिए {{mvar|g}} प्रिमिटिव रूट मॉड्यूलो है {{mvar|n}} यदि और केवल यदि {{mvar|g}} पूर्णांक मॉड्यूलो n पूर्णांक मॉड्यूलो के गुणक समूह का जेनरेटिंग समुच्चय {{mvar|n}} है।
-[[कार्ल फ्रेडरिक गॉस]] ने आदिम रूट को [[अंकगणितीय शोध]] (1801) के अनुच्छेद 57 में परिभाषित किया, जहां उन्होंने इस शब्द को गढ़ने का श्रेय [[यूलर]] को दिया। अनुच्छेद 56 में उन्होंने कहा कि [[जोहान हेनरिक लैम्बर्ट]] और यूलर उनके बारे में जानते थे, लेकिन वह पहले व्यक्ति थे जिन्होंने कठोर रूप से प्रदर्शित किया कि [[ अभाज्य संख्या |अभाज्य संख्या]] के लिए आदिम रूट उपस्थित हैं। {{mvar|n}} वास्तव में, विवादों में दो प्रमाण होते हैं: अनुच्छेद 54 में एक गैर-रचनात्मक [[अस्तित्व प्रमेय]] है, जबकि अनुच्छेद 55 में प्रमाण [[रचनात्मक प्रमाण]] है।
+[[कार्ल फ्रेडरिक गॉस]] ने प्रिमिटिव रूट को [[अंकगणितीय शोध]] (1801) के अनुच्छेद 57 में परिभाषित किया, जहां उन्होंने इस शब्द को गढ़ने का श्रेय [[यूलर]] को दिया। अनुच्छेद 56 में उन्होंने कहा कि [[जोहान हेनरिक लैम्बर्ट]] और यूलर उनके बारे में जानते थे, लेकिन वह पहले व्यक्ति थे जिन्होंने कठोर रूप से प्रदर्शित किया कि [[ अभाज्य संख्या |अभाज्य संख्या]] के लिए प्रिमिटिव रूट उपस्थित हैं। {{mvar|n}} वास्तव में, विवादों में दो प्रमाण होते हैं: अनुच्छेद 54 में एक गैर-रचनात्मक [[अस्तित्व प्रमेय]] है, जबकि अनुच्छेद 55 में प्रमाण [[रचनात्मक प्रमाण]] है।
 == प्रारंभिक उदाहरण ==
@@ Line 18: / Line 18: @@
 \end{array}
 </math>
-यहाँ हम देखते हैं कि 3 का क्रम (समूह सिद्धांत) 3<sup>k</sup> मॉड्यूलो 7 और 6 है। अवधि में अवशेष, जो 3, 2, 6, 4, 5, 1 हैं, सभी अशून्य अवशेषों मॉड्यूलो 7 की पुनर्व्यवस्था बनाते हैं, जिसका अर्थ है कि 3 वास्तव में आदिम रूट मॉड्यूलो 7 है यह इस तथ्य से निकला है कि अनुक्रम ({{mvar|g}}<sup>{{mvar|k}}</sup> मोडुलो{{mvar|n}}) के कुछ मान के बाद हमेशा दोहराता है {{mvar|k}}, मॉड्यूल के बाद से {{mvar|n}} मूल्यों की सीमित संख्या उत्पन्न करता है। अगर {{mvar|g}} आदिम रूट मॉड्यूलो है {{mvar|n}} और {{mvar|n}} प्रधान है, तो पुनरावृत्ति की अवधि है {{nowrap|{{mvar|n}} − 1.}} इस तरह से बनाए गए क्रमपरिवर्तन (और उनके वृत्ताकार बदलाव) कोस्टास सरणी वेल्च के रूप में दिखाए गए हैं।
+यहाँ हम देखते हैं कि 3 का क्रम (समूह सिद्धांत) 3<sup>k</sup> मॉड्यूलो 7 और 6 है। अवधि में अवशेष, जो 3, 2, 6, 4, 5, 1 हैं, सभी अशून्य अवशेषों मॉड्यूलो 7 की पुनर्व्यवस्था बनाते हैं, जिसका अर्थ है कि 3 वास्तव में प्रिमिटिव रूट मॉड्यूलो 7 है यह इस तथ्य से निकला है कि अनुक्रम ({{mvar|g}}<sup>{{mvar|k}}</sup> मोडुलो{{mvar|n}}) के कुछ मान के बाद हमेशा दोहराता है {{mvar|k}}, मॉड्यूल के बाद से {{mvar|n}} मूल्यों की सीमित संख्या उत्पन्न करता है। यदि {{mvar|g}} प्रिमिटिव रूट मॉड्यूलो है {{mvar|n}} और {{mvar|n}} प्रधान है, तो पुनरावृत्ति की अवधि है {{nowrap|{{mvar|n}} − 1.}} इस तरह से बनाए गए क्रमपरिवर्तन (और उनके वृत्ताकार बदलाव) कोस्टास सरणी वेल्च के रूप में दिखाए गए हैं।
 == परिभाषा ==
-अगर {{mvar|n}} धनात्मक पूर्णांक है, 0 से पूर्णांक {{nowrap|{{mvar|n}} − 1}} जो कि कोप्राइम हैं {{mvar|n}} (या समतुल्य रूप से, सर्वांगसमता वर्ग सह अभाज्य हैं {{mvar|n}}) गुणन मॉड्यूलर अंकगणित के साथ [[समूह (गणित)]] बनाते हैं {{mvar|n}} ऑपरेशन के रूप में; इसे पूर्णांकों के गुणक समूह n द्वारा निरूपित किया जाता है <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}, और [[इकाइयों का समूह]] कहा जाता है {{mvar|n}}, या प्रिमिटिव क्लास मोडुलो का समूह {{mvar|n}}. जैसा कि लेख में बताया गया है कि पूर्णांकों का गुणक समूह मॉड्यूल n पूर्णांक मॉड्यूलो का गुणक समूह {{mvar|n}}, यह गुणात्मक समूह (<math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}) [[चक्रीय समूह]] है अगर और केवल अगर {{mvar|n}} 2, 4 के बराबर है, {{mvar|p{{sup|k}}}}, या 2{{mvar|p{{sup|k}}}} कहाँ {{mvar|p{{sup|k}}}} एक विषम अभाज्य संख्या की शक्ति है।<ref>{{MathWorld |title=Modulo Multiplication Group |urlname=ModuloMultiplicationGroup}}
+यदि {{mvar|n}} धनात्मक पूर्णांक है, 0 से पूर्णांक {{nowrap|{{mvar|n}} − 1}} जो कि कोप्राइम हैं {{mvar|n}} (या समतुल्य रूप से, सर्वांगसमता वर्ग सह अभाज्य हैं {{mvar|n}}) गुणन मॉड्यूलर अंकगणित के साथ [[समूह (गणित)]] बनाते हैं {{mvar|n}} ऑपरेशन के रूप में; इसे पूर्णांकों के गुणक समूह n द्वारा निरूपित किया जाता है <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}, और [[इकाइयों का समूह]] कहा जाता है {{mvar|n}}, या प्रिमिटिव क्लास मोडुलो का समूह {{mvar|n}}. जैसा कि लेख में बताया गया है कि पूर्णांकों का गुणक समूह मॉड्यूल n पूर्णांक मॉड्यूलो का गुणक समूह {{mvar|n}}, यह गुणात्मक समूह (<math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}) [[चक्रीय समूह]] है यदि और केवल यदि {{mvar|n}} 2, 4 के बराबर है, {{mvar|p{{sup|k}}}}, या 2{{mvar|p{{sup|k}}}} कहाँ {{mvar|p{{sup|k}}}} एक विषम अभाज्य संख्या की शक्ति है।<ref>{{MathWorld |title=Modulo Multiplication Group |urlname=ModuloMultiplicationGroup}}
-</ref><ref>[http://www.encyclopediaofmath.org/index.php/Primitive_root Primitive root], [[Encyclopedia of Mathematics]].</ref> कब (और केवल कब) यह समूह <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} चक्रीय है, इस चक्रीय समूह के समूह के जनरेटिंग सेट को आदिम रूट मॉड्यूल कहा जाता है {{mvar|n}}<ref>{{Harvnb|Vinogradov|2003|p=106}}.</ref> (या पूर्ण भाषा में एकता मॉड्यूलो की आदिम रूट {{mvar|n}}, एकता मॉड्यूल n बहुपद समीकरण x की रूट के मौलिक समाधान के रूप में अपनी भूमिका पर बल देते हुए{{su|p={{mvar|m}}}} − 1 वलय में <math>\mathbb{Z}</math>{{sub|{{mvar|n}}}}), या बस का एक आदिम तत्व <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} है।
+</ref><ref>[http://www.encyclopediaofmath.org/index.php/Primitive_root Primitive root], [[Encyclopedia of Mathematics]].</ref> कब (और केवल कब) यह समूह <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} चक्रीय है, इस चक्रीय समूह के समूह के जनरेटिंग समुच्चय को प्रिमिटिव रूट मॉड्यूल कहा जाता है {{mvar|n}}<ref>{{Harvnb|Vinogradov|2003|p=106}}.</ref> (या पूर्ण भाषा में एकता मॉड्यूलो की प्रिमिटिव रूट {{mvar|n}}, एकता मॉड्यूल n बहुपद समीकरण x की रूट के मौलिक समाधान के रूप में अपनी भूमिका पर बल देते हुए{{su|p={{mvar|m}}}} − 1 वलय में <math>\mathbb{Z}</math>{{sub|{{mvar|n}}}}), या बस का एक आदिम तत्व <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} है।
-जब <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} गैर-चक्रीय है, ऐसे आदिम तत्व मॉड {{mvar|n}} उपस्थित नहीं है। इसके बजाय, प्रत्येक प्रमुख घटक {{mvar|n}} की अपनी उप-आदिम रूट हैं (देखें {{math|15}} नीचे दिए गए उदाहरणों में)
+जब <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} गैर-चक्रीय है, ऐसे आदिम तत्व मॉड {{mvar|n}} उपस्थित नहीं है। इसके बजाय, प्रत्येक प्रमुख घटक {{mvar|n}} की अपनी उप-प्रिमिटिव रूट हैं (देखें {{math|15}} नीचे दिए गए उदाहरणों में)
-किसी के लिए {{mvar|n}} (की भी होगी या नहीं <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} चक्रीय है), का क्रम <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} यूलर के कुल फलन द्वारा दिया गया है {{mvar|φ}}({{mvar|n}}) {{OEIS|id=A000010}}. और फिर, यूलर प्रमेय यह कहता है {{nowrap|{{mvar|a}}<sup>{{mvar|φ}}({{mvar|n}})</sup> ≡ 1 (mod {{mvar|n}})}} हर एक के लिए {{mvar|a}} कोप्राइम {{mvar|n}}; की सबसे कम शक्ति {{mvar|a}} जो 1 मॉड्यूलो के अनुरूप है {{mvar|n}} का गुणन क्रम कहा जाता है {{mvar|a}} मापांक {{mvar|n}}. विशेष रूप से, के लिए {{mvar|a}} आदिम रूट मॉड्यूल होना {{mvar|n}}, {{nowrap|{{mvar|a}}<sup>{{mvar|φ}}({{mvar|n}})</sup> }} की सबसे छोटी शक्ति होनी चाहिए {{mvar|a}} जो 1 मॉड्यूलो के अनुरूप {{mvar|n}} है।
+किसी के लिए {{mvar|n}} (की भी होगी या नहीं <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} चक्रीय है), का क्रम <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} यूलर के कुल फलन द्वारा दिया गया है {{mvar|φ}}({{mvar|n}}) {{OEIS|id=A000010}}. और फिर, यूलर प्रमेय यह कहता है {{nowrap|{{mvar|a}}<sup>{{mvar|φ}}({{mvar|n}})</sup> ≡ 1 (mod {{mvar|n}})}} हर एक के लिए {{mvar|a}} कोप्राइम {{mvar|n}}; की सबसे कम शक्ति {{mvar|a}} जो 1 मॉड्यूलो के अनुरूप है {{mvar|n}} का गुणन क्रम कहा जाता है {{mvar|a}} मापांक {{mvar|n}}. विशेष रूप से, के लिए {{mvar|a}} प्रिमिटिव रूट मॉड्यूल होना {{mvar|n}}, {{nowrap|{{mvar|a}}<sup>{{mvar|φ}}({{mvar|n}})</sup> }} की सबसे छोटी शक्ति होनी चाहिए {{mvar|a}} जो 1 मॉड्यूलो के अनुरूप {{mvar|n}} है।
 == उदाहरण ==
@@ Line 44: / Line 44: @@
-का क्रम 1 है, 3 और 5 का क्रम 6 है, 9 और 11 का क्रम 3 है, और 13 का क्रम 2 है। इस प्रकार, 3 और 5 आदिम रूट मॉड्यूलो 14 हैं।
+का क्रम 1 है, 3 और 5 का क्रम 6 है, 9 और 11 का क्रम 3 है, और 13 का क्रम 2 है। इस प्रकार, 3 और 5 प्रिमिटिव रूट मॉड्यूलो 14 हैं।
 दूसरे उदाहरण के लिए आइए {{nowrap|{{mvar|n}} {{=}} 15 .}} के तत्व <math>\mathbb{Z}</math>{{su|b=15|p=×}} सर्वांगसमता वर्ग {1, 2, 4, 7, 8, 11, 13, 14} हैं; वहाँ हैं {{nowrap|{{mvar|φ}}(15) {{=}} 8}} उनमें से<syntaxhighlight>
@@ Line 62: / Line 62: @@
-चूँकि ऐसी कोई संख्या नहीं है जिसका क्रम 8 है, कोई आदिम रूट मॉड्यूलो 15 नहीं है। वास्तव में, {{nowrap|{{mvar|λ}}(15) {{=}} 4}}, कहाँ {{mvar|λ}} [[कारमाइकल समारोह|कारमाइकल फलन]] है। {{OEIS|id=A002322}}
+चूँकि ऐसी कोई संख्या नहीं है जिसका क्रम 8 है, कोई प्रिमिटिव रूट मॉड्यूलो 15 नहीं है। वास्तव में, {{nowrap|{{mvar|λ}}(15) {{=}} 4}}, कहाँ {{mvar|λ}} [[कारमाइकल समारोह|कारमाइकल फलन]] है। {{OEIS|id=A002322}}
-== आदिम रूट की तालिका ==
+== प्रिमिटिव रूट की तालिका ==
 नंबर <math>n</math> जिनकी मूल रूट आकार की होती है
@@ Line 71: / Line 71: @@
 ये नंबर हैं <math>n</math> साथ <math>\varphi(n) = \lambda(n),</math> क्रम में भी रखा {{OEIS link|id=A033948}} [[OEIS]] में।
-निम्न तालिका आदिम रूट मॉड्यूलो को सूचीबद्ध करती है {{mvar|n}} तक <math>n=31</math>:
+निम्न तालिका प्रिमिटिव रूट मॉड्यूलो को सूचीबद्ध करती है {{mvar|n}} तक <math>n=31</math>:
 {|class="wikitable"
 !{{tmath|n}}
-!आदिम रूट मॉड्यूलो {{tmath|n}}
+!प्रिमिटिव रूट मॉड्यूलो {{tmath|n}}
 !क्रम <math>\varphi(n),</math><br />({{oeis|id=A000010}})
 ![[Torsion group|एक्सपोनेंट]] <math>\lambda(n),</math><br />({{oeis|id=A002322}})
@@ Line 144: / Line 144: @@
 == गुण ==
-गॉस सिद्ध हुआ<ref>{{Harvnb|Gauss|Clarke|1986|loc=arts. 80}}.</ref> कि किसी भी अभाज्य संख्या के लिए {{mvar|p}} (एकमात्र अपवाद के साथ {{nowrap|{{mvar|p}} {{=}} 3),}} इसकी आदिम रूट का गुणनफल 1 मॉड्यूल के अनुरूप है {{mvar|p}} वह सिद्ध भी हुआ<ref>{{Harvnb|Gauss|Clarke|1986|loc=art 81}}.</ref> कि किसी भी अभाज्य संख्या के लिए {{mvar|p}}, इसके आदिम मूलों का योग सर्वांगसम है {{mvar|μ}}({{mvar|p}} − 1) रूप {{mvar|p}}, कहाँ {{mvar|μ}} मोबियस फलन है।
+गॉस सिद्ध हुआ<ref>{{Harvnb|Gauss|Clarke|1986|loc=arts. 80}}.</ref> कि किसी भी अभाज्य संख्या के लिए {{mvar|p}} (एकमात्र अपवाद के साथ {{nowrap|{{mvar|p}} {{=}} 3),}} इसकी प्रिमिटिव रूट का गुणनफल 1 मॉड्यूल के अनुरूप है {{mvar|p}} वह सिद्ध भी हुआ<ref>{{Harvnb|Gauss|Clarke|1986|loc=art 81}}.</ref> कि किसी भी अभाज्य संख्या के लिए {{mvar|p}}, इसके आदिम मूलों का योग सर्वांगसम है {{mvar|μ}}({{mvar|p}} − 1) रूप {{mvar|p}}, कहाँ {{mvar|μ}} मोबियस फलन है।
 उदाहरण के लिए,
@@ Line 151: / Line 151: @@
 |{{mvar|p}} = 3, || {{mvar|μ}}(2) = −1. || मूल रूट 2 है
 |-
-|{{mvar|p}} = 5, || {{mvar|μ}}(4) = 0. || आदिम रूट 2 और 3 हैं।
+|{{mvar|p}} = 5, || {{mvar|μ}}(4) = 0. || प्रिमिटिव रूट 2 और 3 हैं।
 |-
-|{{mvar|p}} = 7, || {{mvar|μ}}(6) = 1. || आदिम रूट 3 और 5 हैं।
+|{{mvar|p}} = 7, || {{mvar|μ}}(6) = 1. || प्रिमिटिव रूट 3 और 5 हैं।
 |-
-|{{mvar|p}} = 31, ||{{mvar|μ}}(30) = −1. || आदिम रूट 3, 11, 12, 13, 17, 21, 22 और 24 हैं।
+|{{mvar|p}} = 31, ||{{mvar|μ}}(30) = −1. || प्रिमिटिव रूट 3, 11, 12, 13, 17, 21, 22 और 24 हैं।
 |}
-जैसे, बाद की आदिम रूट का उत्पाद है <math>2^6\cdot 3^4\cdot 7\cdot 11^2\cdot 13\cdot 17 = 970377408 \equiv 1 \pmod{31}</math>, और उनका योग है <math>123 \equiv -1 \equiv \mu(31-1) \pmod{31}</math>.
+जैसे, बाद की प्रिमिटिव रूट का उत्पाद है <math>2^6\cdot 3^4\cdot 7\cdot 11^2\cdot 13\cdot 17 = 970377408 \equiv 1 \pmod{31}</math>, और उनका योग है <math>123 \equiv -1 \equiv \mu(31-1) \pmod{31}</math>.
-अगर <math>a</math> आदिम रूट मॉड्यूलो प्राइम है <math>p</math>, तब <math>a^\frac{p-1}{2}\equiv -1 \pmod p</math>.
+यदि <math>a</math> प्रिमिटिव रूट मॉड्यूलो प्राइम है <math>p</math>, तब <math>a^\frac{p-1}{2}\equiv -1 \pmod p</math>.
-आदिम रूट पर आर्टिन का अनुमान बताता है कि दिया हुआ पूर्णांक {{mvar|a}} जो कि न तो [[वर्ग संख्या]] है और न ही -1 आदिम रूट मॉडुलो अपरिमित रूप से अनेक अभाज्य संख्या है।
+प्रिमिटिव रूट पर आर्टिन का अनुमान बताता है कि दिया हुआ पूर्णांक {{mvar|a}} जो कि न तो [[वर्ग संख्या]] है और न ही -1 प्रिमिटिव रूट मॉडुलो अपरिमित रूप से अनेक अभाज्य संख्या है।
-== आदिम रूट ढूँढना ==
+== प्रिमिटिव रूट ढूँढना ==
-आदिम रूट के मॉड्यूलो की गणना करने के लिए कोई सामान्य सामान्य सूत्र नहीं है {{mvar|n}} ज्ञात है।{{efn|"One of the most important unsolved problems in the theory of finite fields is designing a fast algorithm to construct primitive roots. {{Harvnb|von zur Gathen|Shparlinski|1998|pp=15–24}} }}{{efn|"There is no convenient formula for computing [the least primitive root]." {{Harvnb|Robbins|2006|p=159}} }} चुकीं , आदिम रूट का पता लगाने की विधियाँ हैं जो सभी उम्मीदवारों को आज़माने की तुलना में तेज़ हैं। यदि किसी संख्या का गुणन क्रम (इसका [[मरोड़ समूह]]) {{mvar|m}} मापांक {{mvar|n}} यूलर के फाई फलन के बराबर है<math>\varphi(n)</math>(के लिए <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}), तो यह आदिम रूट है। वास्तव में विलोम सत्य है: यदि {{mvar|m}} आदिम रूट मॉड्यूलो है {{mvar|n}}, फिर का गुणक क्रम {{mvar|m}} है <math>\varphi(n) = \lambda(n)~.</math> हम इसका उपयोग उम्मीदवार का परीक्षण करने के लिए कर सकते हैं {{mvar|m}} यह देखने के लिए कि क्या यह आदिम है।
+प्रिमिटिव रूट के मॉड्यूलो की गणना करने के लिए कोई सामान्य सामान्य सूत्र नहीं है {{mvar|n}} ज्ञात है।{{efn|"One of the most important unsolved problems in the theory of finite fields is designing a fast algorithm to construct primitive roots. {{Harvnb|von zur Gathen|Shparlinski|1998|pp=15–24}} }}{{efn|"There is no convenient formula for computing [the least primitive root]." {{Harvnb|Robbins|2006|p=159}} }} चुकीं , प्रिमिटिव रूट का पता लगाने की विधियाँ हैं जो सभी उम्मीदवारों को आज़माने की तुलना में तेज़ हैं। यदि किसी संख्या का गुणन क्रम (इसका [[मरोड़ समूह]]) {{mvar|m}} मापांक {{mvar|n}} यूलर के फाई फलन के बराबर है<math>\varphi(n)</math>(के लिए <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}), तो यह प्रिमिटिव रूट है। वास्तव में विलोम सत्य है: यदि {{mvar|m}} प्रिमिटिव रूट मॉड्यूलो है {{mvar|n}}, फिर का गुणक क्रम {{mvar|m}} है <math>\varphi(n) = \lambda(n)~.</math> हम इसका उपयोग उम्मीदवार का परीक्षण करने के लिए कर सकते हैं {{mvar|m}} यह देखने के लिए कि क्या यह आदिम है।
 के लिए <math>n > 1</math> सबसे पहले, गणना करें <math>\varphi(n)~.</math> फिर के विभिन्न प्रमुख कारकों का निर्धारण करें <math>\varphi(n)</math>, कहना {{mvar|p}}<sub>1</sub>, ..., {{mvar|p{{sub|k}}}}. अंत में गणना करें
 :<math>g^{\varphi(n)/p_i}\bmod n \qquad\mbox{ for } i=1,\ldots,k</math>
-[[मॉड्यूलर घातांक]] के लिए तेज़ एल्गोरिथम का उपयोग करना जैसे कि वर्ग बनाकर घातांक संख्या {{mvar|g}} जिसके लिए ये {{mvar|k}} परिणाम सभी भिन्न हैं 1 से आदिम रूट है।
+[[मॉड्यूलर घातांक]] के लिए तेज़ एल्गोरिथम का उपयोग करना जैसे कि वर्ग बनाकर घातांक संख्या {{mvar|g}} जिसके लिए ये {{mvar|k}} परिणाम सभी भिन्न हैं 1 से प्रिमिटिव रूट है।
-आदिम रूट की संख्या मॉड्यूलो {{mvar|n}}, यदि कोई हो, के बराबर है।<ref>{{OEIS|A010554}}</ref>
+प्रिमिटिव रूट की संख्या मॉड्यूलो {{mvar|n}}, यदि कोई हो, के बराबर है।<ref>{{OEIS|A010554}}</ref>
 :<math>\varphi\left(\varphi(n)\right)</math>
 चूंकि, सामान्य तौर पर, चक्रीय समूह के साथ {{mvar|r}} तत्व होते हैं <math>\varphi(r)</math> जनरेटर, के साथ {{mvar|r}} को अभाज्य पूर्णांक होने के नाते {{mvar|n}}, जो उत्पन्न करता है  प्रधान के लिए {{mvar|n}}, यह बराबर है <math>\varphi(n-1)</math>, और तबसे <math>n / \varphi(n-1) \in O(\log\log n)</math> जेनरेटर {2, ..., के बीच बहुत आम हैं {{mvar|n}}&minus;1} और इस प्रकार इसे खोजना अपेक्षाकृत सरल है।<ref name="Knuth-1998" />
-अगर {{mvar|g}} आदिम रूट मॉड्यूलो है {{mvar|p}}, तब {{mvar|g}} भी आदिम रूट मॉड्यूलो सभी शक्तियां हैं {{mvar|p{{sup|k}}}} जब तक {{mvar|g}}<sup>{{mvar|p}}−1</sup> ≡ 1 (मॉड {{mvar|p}}<sup>2</sup>); उस स्थिति में, {{mvar|g}} + {{mvar|p}} है।<ref name="Cohen1993"/>
+यदि {{mvar|g}} प्रिमिटिव रूट मॉड्यूलो है {{mvar|p}}, तब {{mvar|g}} भी प्रिमिटिव रूट मॉड्यूलो सभी शक्तियां हैं {{mvar|p{{sup|k}}}} जब तक {{mvar|g}}<sup>{{mvar|p}}−1</sup> ≡ 1 (मॉड {{mvar|p}}<sup>2</sup>); उस स्थिति में, {{mvar|g}} + {{mvar|p}} है।<ref name="Cohen1993"/>
-अगर {{mvar|g}} आदिम रूट मॉड्यूलो है {{mvar|p{{sup|k}}}}, तब {{mvar|g}} भी सभी छोटी शक्तियों का आदिम रूट मोडुलो {{mvar|p}} है।
+यदि {{mvar|g}} प्रिमिटिव रूट मॉड्यूलो है {{mvar|p{{sup|k}}}}, तब {{mvar|g}} भी सभी छोटी शक्तियों का प्रिमिटिव रूट मोडुलो {{mvar|p}} है।
-अगर {{mvar|g}} आदिम रूट मॉड्यूलो है {{mvar|p{{sup|k}}}}, तो कोई {{mvar|g}} या {{mvar|g}} + {{mvar|p{{sup|k}}}} (जो भी विषम हो) आदिम रूट मॉड्यूल 2 {{mvar|p{{sup|k}}}} है।<ref name="Cohen1993"/>
+यदि {{mvar|g}} प्रिमिटिव रूट मॉड्यूलो है {{mvar|p{{sup|k}}}}, तो कोई {{mvar|g}} या {{mvar|g}} + {{mvar|p{{sup|k}}}} (जो भी विषम हो) प्रिमिटिव रूट मॉड्यूल 2 {{mvar|p{{sup|k}}}} है।<ref name="Cohen1993"/>
-आदिम रूट का पता लगाना {{mvar|p}} की रूट को खोजने के बराबर भी है ({{mvar|p}} − 1) सेंट [[साइक्लोटोमिक बहुपद]] मोडुलो {{mvar|p}} है।
+प्रिमिटिव रूट का पता लगाना {{mvar|p}} की रूट को खोजने के बराबर भी है ({{mvar|p}} − 1) सेंट [[साइक्लोटोमिक बहुपद]] मोडुलो {{mvar|p}} है।
-== आदिम रूट के परिमाण का क्रम ==
+== प्रिमिटिव रूट के परिमाण का क्रम ==
-सबसे कम आदिम रूट {{mvar|g{{sub|p}}}} मापांक {{mvar|p}} (श्रेणी 1, 2, ..., में {{nowrap|{{mvar|p}} − 1 )}} सामान्यतः छोटा होता है।
+सबसे कम प्रिमिटिव रूट {{mvar|g{{sub|p}}}} मापांक {{mvar|p}} (श्रेणी 1, 2, ..., में {{nowrap|{{mvar|p}} − 1 )}} सामान्यतः छोटा होता है।
 === ऊपरी सीमा ===
 बर्गेस (1962) सिद्ध हुआ<ref name="Ribenboim, p.24"/><ref>{{Cite journal |last=Burgess |first=D. A. |date=1962 |title=On Character Sums and Primitive Roots † |url=http://doi.wiley.com/10.1112/plms/s3-12.1.179 |journal=Proceedings of the London Mathematical Society |language=en |volume=s3-12 |issue=1 |pages=179–192 |doi=10.1112/plms/s3-12.1.179}}</ref> कि प्रत्येक ε > 0 के लिए एक है {{mvar|C}} ऐसा है कि <math>g_p \leq C\,p^{\frac{1}{4}+\varepsilon}~.</math>
-[[एमिल ग्रॉसवाल्ड]] (1981) ने सिद्ध किया<ref name="Ribenboim, p.24" /><ref>{{Cite journal |last=Grosswald |first=E. |date=1981 |title=On Burgess' Bound for Primitive Roots Modulo Primes and an Application to Γ(p) |url=https://www.jstor.org/stable/2374229 |journal=American Journal of Mathematics |volume=103 |issue=6 |pages=1171–1183 |doi=10.2307/2374229 |jstor=2374229 |issn=0002-9327}}</ref> कि अगर <math>p > e^{e^{24}} \approx 10^{11504079571}</math>, तब <math>g_p < p^{0.499}~.</math>
+[[एमिल ग्रॉसवाल्ड]] (1981) ने सिद्ध किया<ref name="Ribenboim, p.24" /><ref>{{Cite journal |last=Grosswald |first=E. |date=1981 |title=On Burgess' Bound for Primitive Roots Modulo Primes and an Application to Γ(p) |url=https://www.jstor.org/stable/2374229 |journal=American Journal of Mathematics |volume=103 |issue=6 |pages=1171–1183 |doi=10.2307/2374229 |jstor=2374229 |issn=0002-9327}}</ref> कि यदि <math>p > e^{e^{24}} \approx 10^{11504079571}</math>, तब <math>g_p < p^{0.499}~.</math>
 [[विक्टर शौप]] (1990, 1992) ने सिद्ध किया,<ref>{{Harvnb|Bach|Shallit|1996|p=254}}.</ref> [[सामान्यीकृत रीमैन परिकल्पना]] मानते हुए, कि {{nowrap|{{mvar|g{{sub|p}}}} {{=}} O(log<sup>6</sup> {{mvar|p}}).}}
@@ Line 199: / Line 199: @@
 == अनुप्रयोग ==
-आदिम रूट मॉड्यूलो {{mvar|n}} अधिकांशतः [[छद्म यादृच्छिक संख्या जनरेटर]] में प्रयोग किया जाता है<ref>{{Cite book |last=Gentle |first=James E. |url=https://www.worldcat.org/oclc/51534945 |title=यादृच्छिक संख्या पीढ़ी और मोंटे कार्लो के तरीके|date=2003 |publisher=Springer |isbn=0-387-00178-6 |edition=2nd |location=New York |oclc=51534945}}</ref> और [[क्रिप्टोग्राफी]], जिसमें डिफी-हेलमैन कुंजी विनिमय योजना शामिल है। प्रसार (ध्वनिकी) आदिम-रूट विसारक संख्या-सैद्धांतिक अवधारणाओं जैसे कि आदिम रूट और [[द्विघात अवशेष]] पर आधारित हैं।<ref name=Walker-1990/><ref name=Feldman/>
+प्रिमिटिव रूट मॉड्यूलो {{mvar|n}} अधिकांशतः [[छद्म यादृच्छिक संख्या जनरेटर]] में प्रयोग किया जाता है<ref>{{Cite book |last=Gentle |first=James E. |url=https://www.worldcat.org/oclc/51534945 |title=यादृच्छिक संख्या पीढ़ी और मोंटे कार्लो के तरीके|date=2003 |publisher=Springer |isbn=0-387-00178-6 |edition=2nd |location=New York |oclc=51534945}}</ref> और [[क्रिप्टोग्राफी]], जिसमें डिफी-हेलमैन कुंजी विनिमय योजना शामिल है। प्रसार (ध्वनिकी) आदिम-रूट विसारक संख्या-सैद्धांतिक अवधारणाओं जैसे कि प्रिमिटिव रूट और [[द्विघात अवशेष]] पर आधारित हैं।<ref name=Walker-1990/><ref name=Feldman/>
@@ Line 337: / Line 337: @@
   | url = http://www.bluetulip.org/programs/primitive.html
 }}
-[[Category: मॉड्यूलर अंकगणित]]
+[[Category:CS1]]
+[[Category:CS1 Deutsch-language sources (de)]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
 [[Category:Created On 18/05/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Multi-column templates]]
+[[Category:Pages using div col with small parameter]]
+[[Category:Pages with ignored display titles]]
+[[Category:Pages with script errors]]
+[[Category:Pages with syntax highlighting errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Templates using under-protected Lua modules]]
+[[Category:Wikipedia fully protected templates|Div col]]
+[[Category:मॉड्यूलर अंकगणित]]

Anonymous

Search

प्रिमिटिव रूट मॉड्यूलो n: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 17:21, 25 May 2023

Contents

प्रारंभिक उदाहरण

परिभाषा

उदाहरण

प्रिमिटिव रूट की तालिका

गुण

प्रिमिटिव रूट ढूँढना

प्रिमिटिव रूट के परिमाण का क्रम

ऊपरी सीमा

निचली सीमा

अनुप्रयोग

यह भी देखें

फुटनोट्स

संदर्भ

स्रोत

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

प्रिमिटिव रूट मॉड्यूलो n: Difference between revisions

Latest revision as of 17:21, 25 May 2023

प्रारंभिक उदाहरण

परिभाषा

उदाहरण

प्रिमिटिव रूट की तालिका

गुण

प्रिमिटिव रूट ढूँढना

प्रिमिटिव रूट के परिमाण का क्रम

ऊपरी सीमा

निचली सीमा

अनुप्रयोग

यह भी देखें

फुटनोट्स

संदर्भ

स्रोत

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories