# Primitive Root Finder Smallest primitive root mod n with certificate g^(φ/q) ≠ 1, root count φ(φ(n)), up to 50 listed roots, and candidate verification. n ≤ 10¹². > Canonical page: https://elysiatools.com/en/tools/primitive-root-finder - **Category:** Math & Numbers - **Keywords:** primitive root, multiplicative group, cyclic group, euler totient, carmichael function, number theory, discrete logarithm ## Overview The Primitive Root Finder calculates the smallest primitive root modulo n, validates cyclic group structures, and verifies generator candidates for moduli up to 10¹². It provides complete certificates based on prime factors of Euler's totient φ(n), determines total primitive root counts with φ(φ(n)), and can list up to 50 valid primitive roots. ## Inputs - **Modulus n** (text): 2 ≤ n ≤ 10¹² (trial-division factorization bound). - **Output mode** (select) - **Candidate g (verify mode)** (text): Required when verifying; reduced modulo n automatically. ## When to use - When selecting cyclic group generators for cryptographic algorithms such as Diffie-Hellman key exchange or ElGamal encryption. - When verifying whether a specific candidate integer g has full multiplicative order modulo n. - When solving number theory assignments or analyzing multiplicative group structures (ℤ/nℤ)*. ## How it works - Evaluates whether the modulus n admits primitive roots by verifying the form n ∈ {2, 4, p^k, 2p^k} for odd primes p. - Computes Euler's totient φ(n), Carmichael's function λ(n), and factors φ(n) into its distinct prime divisors q. - Tests candidates g using modular exponentiation to confirm that g^(φ(n)/q) ≢ 1 (mod n) for every prime factor q. - Outputs the minimal root, total count φ(φ(n)), up to 50 primitive roots, or detailed verification results. ## Use cases - Generating public base parameters for discrete logarithm cryptosystems. - Checking group cyclicity and finding generators in abstract algebra coursework. - Auditing whether proposed protocol constants are valid primitive roots modulo prime p. ## Frequently asked questions ### Which moduli n have primitive roots? A primitive root exists modulo n if and only if n is 2, 4, p^k, or 2·p^k, where p is an odd prime and k ≥ 1. ### What is the maximum modulus n supported? The tool supports integers n up to 10¹² using trial-division factorization. ### How is a primitive root mathematically certified? For gcd(g, n) = 1, g is certified if g^(φ(n)/q) ≢ 1 (mod n) for every prime factor q of φ(n). ### How many primitive roots exist modulo n? If the multiplicative group is cyclic, the total number of primitive roots is exactly φ(φ(n)). ### What happens if candidate g fails verification? The tool identifies the prime factor witness q where g^(φ(n)/q) ≡ 1 (mod n) and reports the actual order of g. ## Related tools - [Quadratic Residue Checker (Legendre / Jacobi Symbol)](https://elysiatools.com/en/tools/quadratic-residue-checker): Jacobi/Legendre symbol with deterministic Miller–Rabin primality, Tonelli–Shanks square roots for prime moduli, and brute-force resolution for small composite moduli. - [Blood Gas Acid-Base Interpretation (AG / ΔAG)](https://elysiatools.com/en/tools/blood-gas-anion-gap): Complete ABG analysis: pH, primary disorder, compensation (Winter's formula), anion gap ± albumin correction, delta ratio for mixed disorder detection. Derived from Emmett 2016, Kraut 2007, Rastegar 2007, LITFL, MDCalc, and Adrogué 1998. Not medical advice. - [DNA Concentration Calculator (A260 Absorbance)](https://elysiatools.com/en/tools/dna-concentration-a260): Beer–Lambert DNA quantitation: c = A260 × dilution factor × K / path length with 1 OD = 50 µg/mL dsDNA or 33 µg/mL ssDNA, plus ng/µL, total yield, and a 0.1–1.5 linear-range check. Derived from Marmur & Doty, Sambrook & Russell, Thermo Fisher NanoDrop notes. Educational use only. - [OD260/230 Nucleic Acid Purity Ratio Calculator](https://elysiatools.com/en/tools/od260-230-ratio): Check salt/organic-solvent contamination with A260/A230 (pure 2.0–2.2; below 2.0 = guanidinium/phenol/EDTA/salt carryover from TRIzol or columns), with an optional A260/280 cross-check. Derived from Thermo Fisher T042, Sambrook & Russell, Manchester 1995. Educational use only. - [OD260/280 Nucleic Acid Purity Ratio Calculator](https://elysiatools.com/en/tools/od260-280-ratio): Judge DNA/RNA purity from A260/A280 (pure DNA ~1.8, pure RNA ~2.0; low = protein/phenol contamination, DNA > 2.0 = RNA contamination) plus the optional A260/A230 secondary check. Derived from Manchester 1995, Sambrook & Russell, Thermo Fisher T042. Educational use only. - [RNA Concentration Calculator (A260, 1 OD = 40 µg/mL)](https://elysiatools.com/en/tools/rna-concentration-a260): Beer–Lambert RNA quantitation: c = A260 × dilution factor × 40 / path length, plus ng/µL, total yield, a 0.1–1.5 linear-range check, and the RNA OD260/280 ≈ 2.0 purity reminder. Derived from Marmur & Doty, Sambrook & Russell, Manchester 1995, Thermo Fisher NanoDrop notes. Educational use only. - [Train/Test Split with Stratification](https://elysiatools.com/en/tools/train-test-split-with-stratification): Class-stratified train/validation/test split or stratified k-fold for CSV/JSON datasets — seeded, reproducible, with distribution reports, leakage checks, SMOTE preview and CSV export. - [Significant Figures Calculator](https://elysiatools.com/en/tools/sig-fig-calculator): Count significant figures and round numbers to a target number of significant digits ## Samples - [Web Image Processing Python Samples](https://elysiatools.com/en/samples/web-image-processing-python): Web Python image processing examples using PIL/Pillow including reading, saving, resizing, and format conversion - [Android Image Processing Java Samples](https://elysiatools.com/en/samples/android-image-processing-java): Android Java image processing examples including reading/saving images, scaling, and format conversion - [Android Image Processing Kotlin Samples](https://elysiatools.com/en/samples/android-image-processing-kotlin): Android Kotlin image processing examples including reading/saving images, scaling, and format conversion - [Web Image Processing Rust Samples](https://elysiatools.com/en/samples/web-image-processing-rust): Web Rust image processing examples including image read/save, scaling, and format conversion