Primitive Root Calculator Source Code

What is a Primitive Root?

A primitive root modulo n is an integer g that is a generator of the multiplicative group of integers modulo n. For a prime p, the multiplicative group is cyclic of order p-1, and a primitive root modulo p is an element g whose powers modulo p give all the integers from 1 to p-1.

How to Find a Primitive Root

Finding a primitive root modulo p involves checking each number from 2 to p-1 to see if it is a primitive root. The steps are:

1. Factorize p-1 into its prime factors.
2. For each candidate g from 2 to p-1, check if g^((p-1)/q) ≢ 1 mod p for every prime factor q of p-1.
3. The first number that satisfies this condition is a primitive root.

Primitive Root Calculator

Use the calculator in the sidebar to find primitive roots for your numbers. The source code for the algorithm is provided below.

Source Code

The following JavaScript code implements the algorithm to find primitive roots:

// Function to find the primitive root modulo p
function findPrimitiveRoot(p) {
    if (!isPrime(p)) {
        return "Primitive roots exist only for prime numbers.";
    }

    const phi = p - 1;
    const factors = getPrimeFactors(phi);

    for (let g = 2; g <= p; g++) {
        let isPrimitive = true;
        for (let factor of factors) {
            if (modularExponentiation(g, phi / factor, p) === 1) {
                isPrimitive = false;
                break;
            }
        }
        if (isPrimitive) {
            return g;
        }
    }
    return "No primitive root found.";
}

// Helper function to check if a number is prime
function isPrime(num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 === 0 || num % 3 === 0) return false;
    for (let i = 5; i * i <= num; i += 6) {
        if (num % i === 0 || num % (i + 2) === 0) return false;
    }
    return true;
}

// Helper function to get prime factors of a number
function getPrimeFactors(num) {
    const factors = [];
    let n = num;
    for (let i = 2; i * i <= n; i++) {
        while (n % i === 0) {
            factors.push(i);
            n /= i;
        }
    }
    if (n > 1) {
        factors.push(n);
    }
    return [...new Set(factors)];
}

// Helper function for modular exponentiation
function modularExponentiation(base, exponent, modulus) {
    if (modulus === 1) return 0;
    let result = 1;
    base = base % modulus;
    while (exponent > 0) {
        if (exponent % 2 === 1) {
            result = (result * base) % modulus;
        }
        exponent = Math.floor(exponent / 2);
        base = (base * base) % modulus;
    }
    return result;
}