◆

प्रिमिटिव रूट कैलकुलेटर

(ℤ/nℤ)* के जनक (Generators) · कोटि गणना · चक्रीय समूह संरचना

गुणात्मक समूह (ℤ/nℤ)* के सभी प्रिमिटिव रूट (जनक) ज्ञात करें। यह φ(n), φ(φ(n)), सबसे छोटा प्रिमिटिव रूट की गणना करता है और तत्वों की कोटि को सत्यापित करता है।

त्वरित उदाहरण (Quick Examples)

मापांक n (Modulus n: 2 - 1000)

तत्व a की जाँच करें (Check element a - वैकल्पिक)

n (मापांक)

—

इनपुट

φ(n)

—

समूह की कोटि (Group Order)

φ(φ(n))

—

प्रिमिटिव रूटों की संख्या

सबसे छोटा मूल

—

पहला जनक (First Generator)

रूट मौजूद हैं?

—

चक्रीय समूह (Cyclic Group)?

n के अंतर्गत सभी प्रिमिटिव रूट (All Primitive Roots mod n)

कोटि तालिका — (ℤ/nℤ)* के तत्व (Order Table)

n के सह-अभाज्य तत्व, n के साथ उनका gcd, गुणात्मक कोटि (multiplicative order), और क्या वे प्रिमिटिव रूट हैं (कोटि = φ(n))।

प्रिमिटिव रूट क्या है? (What Is a Primitive Root)

मापांक n का एक प्रिमिटिव रूट (primitive root modulo n) (जिसे गुणात्मक समूह का जनक/generator भी कहा जाता है) एक ऐसा पूर्णांक g है जिसकी घातें g¹, g², g³, ..., g^φ(n) मापांक n के अंतर्गत 1 से n तक के प्रत्येक पूर्णांक जो n के सह-अभाज्य (coprime) हैं, उन्हें ठीक एक बार उत्पन्न करती हैं। समूह सिद्धांत (group theory) की भाषा में, g चक्रीय समूह (ℤ/nℤ)* का एक जनक (generator) है।

मापांक n के अंतर्गत किसी तत्व a की गुणात्मक कोटि (multiplicative order) सबसे छोटा धनात्मक पूर्णांक k होता है जिसके लिए aᵏ ≡ 1 (mod n) हो। कोई तत्व प्रिमिटिव रूट होता है यदि और केवल यदि उसकी कोटि φ(n) — पूरे समूह की कोटि — के बराबर हो। प्रिमिटिव रूट वे तत्व हैं जो 1 पर वापस आने से पहले पूरे समूह में चक्र पूरा करते हैं।

किन मापांकों (Moduli) के प्रिमिटिव रूट होते हैं? (Which Moduli Have Roots)

प्रत्येक n के प्रिमिटिव रूट नहीं होते हैं — प्रिमिटिव रूट प्रमेय (Primitive Root Theorem - गॉस द्वारा सिद्ध) एक संपूर्ण विशेषता देता है। प्रिमिटिव रूट केवल तभी मौजूद होते हैं जब:

n = 1 या n = 2 (तुच्छ मामले)
n = 4
n = p^k किसी भी विषम अभाज्य p और k ≥ 1 के लिए
n = 2·p^k किसी भी विषम अभाज्य p और k ≥ 1 के लिए

संख्याएँ जो इस परीक्षण में विफल रहती हैं — जैसे n = 8, 12, 15, 16, 20, 24 — उनके गुणात्मक समूह चक्रीय नहीं होते हैं, इसलिए कोई भी एकल तत्व पूरे समूह को उत्पन्न नहीं करता है। उदाहरण के लिए, (ℤ/8ℤ)* ≅ ℤ&sub2; × ℤ&sub2; (क्लेन फोर-ग्रुप), जहां प्रत्येक तत्व की कोटि 2 है।

प्रिमिटिव रूटों की संख्या कितनी होती है? (How Many Primitive Roots)

जब n के लिए प्रिमिटिव रूट मौजूद होते हैं, तो उनका सटीक मान φ(φ(n)) होता है। यह चक्रीय समूहों की संरचना से आता है: m कोटि के चक्रीय समूह में ठीक φ(m) जनक होते हैं। चूंकि (ℤ/nℤ)*, φ(n) कोटि का चक्रीय समूह है, इसलिए इसके φ(φ(n)) जनक (अर्थात प्रिमिटिव रूट) होते हैं।

उदाहरण के लिए, n = 7 (अभाज्य) के लिए, φ(7) = 6 और φ(6) = 2 है, इसलिए ठीक 2 प्रिमिटिव रूट मौजूद हैं: {3, 5}। n = 23 के लिए, φ(23) = 22 और φ(22) = 10 है, जिससे 10 प्रिमिटिव रूट मिलते हैं।

एक प्रिमिटिव रूट से सभी प्रिमिटिव रूट उत्पन्न करना

यदि g मापांक n का एक प्रिमिटिव रूट है, तो अन्य सभी प्रिमिटिव रूट gᵏ (mod n) के रूप के होते हैं जहाँ gcd(k, φ(n)) = 1 है, 1 ≤ k ≤ φ(n) के लिए। यह सबसे छोटा रूट मिलने के बाद अन्य सभी रूटों को खोजने का एक तेज़ तरीका देता है।

संदर्भ तालिका: सामान्य प्रिमिटिव रूट (Reference Table)

n (मापांक)	प्रकार (Type)	φ(n) (समूह कोटि)	φ(φ(n)) (रूट संख्या)	प्रिमिटिव रूट (Primitive Roots)	रूट मौजूद हैं?
2	2	1	1	{1}	YES
3	prime	2	1	{2}	YES
4	4	2	1	{3}	YES
5	prime	4	2	{2, 3}	YES
7	prime	6	2	{3, 5}	YES
8	2³	4	—	none	NO
9	3²	6	2	{2, 5}	YES
10	2·5	4	2	{3, 7}	YES
12	4·3	4	—	none	NO
23	prime	22	10	{5, 7, 10, 11, 14, 15, 17, 19, 20, 21}	YES

क्रिप्टोग्राफी में अनुप्रयोग (Applications in Cryptography)

डिफी-हेलमैन कुंजी विनिमय (Diffie-Hellman Key Exchange): इस प्रोटोकॉल के लिए एक बड़ा अभाज्य p और मापांक p का एक प्रिमिटिव रूट g चुनना आवश्यक है। प्रत्येक पक्ष g को एक गुप्त घातांक तक बढ़ाता है और परिणाम का आदान-प्रदान करता है। साझा रहस्य इस तथ्य से आता है कि gᵃᵇ = (gᵃ)ᵇ = (gᵇ)ᵃ (mod p) है। प्रिमिटिव रूट का उपयोग करने से सुरक्षा अधिकतम होती है।

एलगामल एन्क्रिप्शन (ElGamal Encryption): डिफी-हेलमैन से निकटता से संबंधित, एलगामल भी एक अभाज्य p के प्रिमिटिव रूट g पर निर्भर करता है। संदेश m का एन्क्रिप्शन एक यादृच्छिक घातांक k का उपयोग करता है; डिक्रिप्शन के लिए साझा रहस्य के असतत लघुगणक की गणना करना आवश्यक होता है।

असतत लघुगणक समस्या (Discrete Logarithm Problem - DLP): इन सभी प्रणालियों की सुरक्षा DLP पर टिकी हुई है: g और gᵏ mod p दिए जाने पर, k खोजना। जब g एक बड़े सुरक्षित अभाज्य p के मापांक में एक प्रिमिटिव रूट होता है, तो DLP को कम्प्यूटेशनल रूप से दुर्गम माना जाता है।

फर्मेट के लघु प्रमेय (Fermat's Little Theorem) से संबंध: अभाज्य p के लिए, फर्मेट का लघु प्रमेय बताता है कि p द्वारा विभाजित न होने वाले सभी a के लिए aᵖ⁻¹ ≡ 1 (mod p) होता है। इसका मतलब है कि (ℤ/pℤ)* के प्रत्येक तत्व की कोटि p-1 = φ(p) को विभाजित करती है। एक प्रिमिटिव रूट वास्तव में वह तत्व है जिसकी कोटि ठीक p-1 है।

Frequently Asked Questions

What is a primitive root?

A primitive root modulo n is an integer g whose powers g¹, g², ..., g^φ(n) (mod n) cycle through every integer coprime to n. Equivalently, g is a generator of the cyclic group (ℤ/nℤ)*. The smallest such k with gᵏ ≡ 1 (mod n) is k = φ(n) — the full group order.

Which numbers have primitive roots?

By the Primitive Root Theorem, primitive roots exist for n if and only if n ∈ {1, 2, 4, p^k, 2·p^k} for odd prime p. All primes have primitive roots (since every prime p falls in the p¹ case). Numbers like 8, 12, 15, 16, 20 do not have primitive roots because their multiplicative groups are products of smaller cyclic groups, not a single cyclic group.

How many primitive roots does n have?

When primitive roots exist, the count is exactly φ(φ(n)). A cyclic group of order m has exactly φ(m) generators. Since (ℤ/nℤ)* is cyclic of order φ(n) when primitive roots exist, it has φ(φ(n)) generators. For n = 7: φ(7) = 6, φ(6) = 2, so 2 primitive roots. For n = 23: φ(23) = 22, φ(22) = 10, so 10 primitive roots.

How do you find the smallest primitive root?

To find the smallest primitive root modulo n: (1) Compute φ(n). (2) Find all distinct prime factors p₁, p₂, ... of φ(n). (3) Test each integer g ≥ 2, checking that g^(φ(n)/p) ¬≡ 1 (mod n) for every prime factor p. The first g passing all these tests is the smallest primitive root. This works because an element has order φ(n) if and only if no "reduced" exponent maps it to 1.

What is the connection between primitive roots and Diffie-Hellman?

In Diffie-Hellman key exchange, a large prime p and a primitive root g modulo p are published. Alice sends gᵃ mod p, Bob sends gᵇ mod p, and both compute the shared secret gᵃᵇ mod p. Security relies on the discrete logarithm problem: recovering a from gᵃ mod p is computationally hard. Using g as a primitive root ensures the entire group (ℤ/pℤ)* is used, preventing small-subgroup attacks.

Why doesn't n=8 have a primitive root?

The group (ℤ/8ℤ)* = {1, 3, 5, 7} has order φ(8) = 4, but it is isomorphic to ℤ&sub2; × ℤ&sub2; (the Klein four-group), not the cyclic group ℤ&sub4;. Every non-identity element satisfies a² ≡ 1 (mod 8): 3² = 9 ≡ 1, 5² = 25 ≡ 1, 7² = 49 ≡ 1. Since no element has order 4, no primitive root exists. For n = 2^k with k ≥ 3, the group is always ℤ&sub2; × ℤ_{2^{k-2}}, which is never cyclic.

What is the discrete logarithm problem?

Given a primitive root g modulo n and an element y, the discrete logarithm problem asks to find k such that gᵏ ≡ y (mod n). Computing gᵏ mod n is fast via repeated squaring (O(log k) multiplications). But going backward — finding k from gᵏ mod n — has no known polynomial-time algorithm for general large n. This computational asymmetry underpins the security of Diffie-Hellman, ElGamal, and the Digital Signature Algorithm (DSA).