Primitive Root Calculator C++

What is a Primitive Root?

A primitive root modulo n is an integer g that has the same order as n in the multiplicative group of integers modulo n. In simpler terms, a primitive root modulo n is a number whose powers generate all the integers from 1 to n-1 modulo n.

For a given prime p, there are exactly φ(p-1) primitive roots, where φ is Euler's totient function. This means that for a prime p, the number of primitive roots is p-1.

How to Find Primitive Roots

Finding primitive roots involves checking the powers of potential candidates modulo n. The steps are:

1. Factorize n-1 into its prime factors.
2. For each candidate g from 2 to n-1, check if g^(n-1/p) ≡ 1 mod n for all prime factors p of n-1.
3. If g does not satisfy the above condition for any prime factor, it is a primitive root.

C++ Implementation

Here's a C++ function to find primitive roots modulo n:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int power(int a, int b, int mod) {
    int result = 1;
    a = a % mod;
    while (b > 0) {
        if (b & 1)
            result = (result * a) % mod;
        b = b >> 1;
        a = (a * a) % mod;
    }
    return result;
}

vector<int> findPrimitiveRoots(int n) {
    vector<int> primitiveRoots;
    if (n == 1) return primitiveRoots;

    int phi = n - 1;
    vector<int> factors;

    // Factorize phi
    for (int i = 2; i * i <= phi; ++i) {
        if (phi % i == 0) {
            factors.push_back(i);
            while (phi % i == 0)
                phi /= i;
        }
    }
    if (phi > 1)
        factors.push_back(phi);

    for (int g = 2; g <= n - 1; ++g) {
        bool isPrimitive = true;
        for (int factor : factors) {
            if (power(g, (n - 1) / factor, n) == 1) {
                isPrimitive = false;
                break;
            }
        }
        if (isPrimitive)
            primitiveRoots.push_back(g);
    }

    return primitiveRoots;
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;

    vector<int> roots = findPrimitiveRoots(n);
    if (roots.empty()) {
        cout << "No primitive roots exist for " << n << endl;
    } else {
        cout << "Primitive roots modulo " << n << " are: ";
        for (int root : roots)
            cout << root << " ";
        cout << endl;
    }

    return 0;
}

Examples

Let's find the primitive roots modulo 7:

1. Factorize 6 (7-1): 6 = 2 × 3
2. Check numbers from 2 to 6:
   • 2: 2^3 ≡ 1 mod 7 (not primitive)
   • 3: 3^3 ≡ 6 mod 7 ≠ 1 (primitive)
   • 4: 4^3 ≡ 1 mod 7 (not primitive)
   • 5: 5^3 ≡ 6 mod 7 ≠ 1 (primitive)
   • 6: 6^3 ≡ 6 mod 7 ≠ 1 (primitive)

The primitive roots modulo 7 are 3, 5, and 6.