Primitive Root Calculator Source Code Java

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. In simpler terms, it's a number whose powers modulo n produce all the numbers from 1 to n-1 exactly once.

Primitive roots exist only for certain numbers, typically prime numbers. The number of primitive roots modulo a prime p is φ(p-1), where φ is Euler's totient function.

Properties of Primitive Roots

• Every number has exactly φ(φ(n)) primitive roots if n is 2, 4, p^k, or 2p^k, where p is an odd prime and k is a positive integer.
• Primitive roots can be used to generate all other numbers in the multiplicative group.
• They are fundamental in cryptographic algorithms like Diffie-Hellman key exchange.

Java Implementation

The following Java code demonstrates how to find primitive roots modulo a prime number:

Source Code

import java.util.ArrayList;
import java.util.List;

public class PrimitiveRootCalculator {

    // Function to check if a number is prime
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;

        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    // Function to find the prime factors of a number
    public static List<Integer> primeFactors(int n) {
        List<Integer> factors = new ArrayList<>();

        // Handle 2 separately
        while (n % 2 == 0) {
            factors.add(2);
            n /= 2;
        }

        // Check for odd divisors
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            while (n % i == 0) {
                factors.add(i);
                n /= i;
            }
        }

        // If n is a prime number greater than 2
        if (n > 2) {
            factors.add(n);
        }

        return factors;
    }

    // Function to find the primitive roots modulo p
    public static List<Integer> findPrimitiveRoots(int p) {
        List<Integer> primitiveRoots = new ArrayList<>();

        if (!isPrime(p)) {
            System.out.println("Primitive roots exist only for prime numbers.");
            return primitiveRoots;
        }

        int phi = p - 1;
        List<Integer> primeFactors = primeFactors(phi);

        // Check each number from 2 to p-1
        for (int g = 2; g < p; g++) {
            boolean isPrimitiveRoot = true;

            for (int factor : primeFactors) {
                int exponent = phi / factor;
                if (modularExponentiation(g, exponent, p) == 1) {
                    isPrimitiveRoot = false;
                    break;
                }
            }

            if (isPrimitiveRoot) {
                primitiveRoots.add(g);
            }
        }

        return primitiveRoots;
    }

    // Function to compute (a^b) mod m
    public static int modularExponentiation(int a, int b, int m) {
        int result = 1;
        a = a % m;

        while (b > 0) {
            if (b % 2 == 1) {
                result = (result * a) % m;
            }
            a = (a * a) % m;
            b = b / 2;
        }

        return result;
    }

    public static void main(String[] args) {
        int p = 11; // Example prime number
        List<Integer> roots = findPrimitiveRoots(p);

        System.out.println("Primitive roots modulo " + p + ":");
        for (int root : roots) {
            System.out.print(root + " ");
        }
    }
}

How to Use the Code

1. Copy the code into a Java file (e.g., PrimitiveRootCalculator.java).
2. Compile the code using javac PrimitiveRootCalculator.java.
3. Run the program using java PrimitiveRootCalculator.
4. Modify the value of p in the main method to find primitive roots for different primes.

Example Calculation

Let's find the primitive roots modulo 7:

Now, we check each number from 2 to 6 to see if it's a primitive root:

• For g = 2:
  • 2^(6/2) = 2^3 = 8 ≡ 1 mod 7? No (8 mod 7 = 1)
  • Since 2^3 ≡ 1 mod 7, 2 is not a primitive root.
• For g = 3:
  • 3^(6/2) = 3^3 = 27 ≡ 6 mod 7? No (27 mod 7 = 6)
  • 3^(6/3) = 3^2 = 9 ≡ 2 mod 7? No (9 mod 7 = 2)
  • Since neither condition holds, 3 is a primitive root.
• For g = 4:
  • 4^(6/2) = 4^3 = 64 ≡ 1 mod 7? No (64 mod 7 = 1)
  • Since 4^3 ≡ 1 mod 7, 4 is not a primitive root.
• For g = 5:
  • 5^(6/2) = 5^3 = 125 ≡ 6 mod 7? No (125 mod 7 = 6)
  • 5^(6/3) = 5^2 = 25 ≡ 4 mod 7? No (25 mod 7 = 4)
  • Since neither condition holds, 5 is a primitive root.
• For g = 6:
  • 6^(6/2) = 6^3 = 216 ≡ 6 mod 7? No (216 mod 7 = 6)
  • 6^(6/3) = 6^2 = 36 ≡ 1 mod 7? No (36 mod 7 = 1)
  • Since neither condition holds, 6 is a primitive root.

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