How to compute Euler's totient function φ in Java?

Learn how to compute euler's totient function φ in java? with practical examples, diagrams, and best practices. Covers java, function, math development techniques with visual explanations.
Tags:
Categories:

Computing Euler's Totient Function φ in Java

Hero image for How to compute Euler's totient function φ in Java?

Explore various methods to implement Euler's totient function (φ) in Java, a cornerstone of number theory and cryptography.

Euler's totient function, denoted as φ(n) or phi(n), counts the number of positive integers up to a given integer n that are relatively prime to n. Two integers are relatively prime if their greatest common divisor (GCD) is 1. This function is fundamental in number theory and has significant applications in cryptography, particularly in RSA encryption. This article will guide you through different approaches to compute φ(n) in Java, from a naive brute-force method to more optimized solutions leveraging prime factorization.

Understanding Euler's Totient Function (φ)

Before diving into implementation, let's solidify our understanding of φ(n). For example, if n = 9, the positive integers less than or equal to 9 are {1, 2, 3, 4, 5, 6, 7, 8, 9}. We need to find which of these are relatively prime to 9. The numbers relatively prime to 9 are {1, 2, 4, 5, 7, 8} because their GCD with 9 is 1. Thus, φ(9) = 6.

Key properties of φ(n) that are useful for computation:

  1. If n is a prime number (p): φ(p) = p - 1. (e.g., φ(7) = 6)
  2. If n is a prime power (p^k): φ(p^k) = p^k - p^(k-1) = p^k * (1 - 1/p). (e.g., φ(9) = φ(3^2) = 3^2 - 3^1 = 9 - 3 = 6)
  3. If n and m are relatively prime: φ(n * m) = φ(n) * φ(m). This is known as the multiplicative property.
  4. General formula using prime factorization: If the prime factorization of n is p₁^k₁ * p₂^k₂ * ... * pᵣ^kᵣ, then φ(n) = n * (1 - 1/p₁) * (1 - 1/p₂) * ... * (1 - 1/pᵣ).
flowchart TD
    A[Input: Integer n]
    B{Is n prime?}
    C[φ(n) = n - 1]
    D{Find prime factors of n}
    E[n = p1^k1 * p2^k2 * ... * pr^kr]
    F[Calculate φ(n) = n * (1 - 1/p1) * ... * (1 - 1/pr)]
    A --> B
    B -- Yes --> C
    B -- No --> D
    D --> E
    E --> F
    C --> G[Output φ(n)]
    F --> G

Flowchart for computing Euler's Totient Function based on prime factorization

Method 1: Naive Brute-Force Approach

The simplest way to compute φ(n) is to iterate from 1 to n-1 and count how many numbers share a GCD of 1 with n. This method is straightforward to implement but can be inefficient for large values of n due to the repeated GCD calculations.

public class EulerTotient {

    // Function to compute GCD using Euclidean algorithm
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // Naive method to compute Euler's Totient Function
    public static int phiNaive(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("Input must be a positive integer.");
        }
        int result = 1; // 1 is always relatively prime to n
        for (int i = 2; i < n; i++) {
            if (gcd(i, n) == 1) {
                result++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println("phi(1) = " + phiNaive(1)); // Expected: 1
        System.out.println("phi(9) = " + phiNaive(9)); // Expected: 6
        System.out.println("phi(10) = " + phiNaive(10)); // Expected: 4
        System.out.println("phi(7) = " + phiNaive(7)); // Expected: 6
    }
}

Java implementation of the naive brute-force φ(n) calculation.

Method 2: Optimized using Prime Factorization

A more efficient approach leverages the general formula for φ(n) based on its prime factorization: φ(n) = n * Π (1 - 1/p), where the product is over the distinct prime factors p of n. This method involves finding all unique prime factors of n and then applying the formula.

import java.util.HashSet;
import java.util.Set;

public class EulerTotientOptimized {

    // Optimized method to compute Euler's Totient Function using prime factorization
    public static int phiOptimized(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("Input must be a positive integer.");
        }
        if (n == 1) {
            return 1; // phi(1) = 1
        }

        int result = n;
        int tempN = n;

        // Iterate through all possible prime factors up to sqrt(n)
        for (int p = 2; p * p <= tempN; p++) {
            // If p is a prime factor
            if (tempN % p == 0) {
                // Subtract multiples of p from result
                result -= result / p;
                // Divide all occurrences of p from tempN
                while (tempN % p == 0) {
                    tempN /= p;
                }
            }
        }

        // If tempN is still greater than 1, it means tempN itself is a prime factor
        // (e.g., if n was a prime number or had a large prime factor left)
        if (tempN > 1) {
            result -= result / tempN;
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println("phi(1) = " + phiOptimized(1)); // Expected: 1
        System.out.println("phi(9) = " + phiOptimized(9)); // Expected: 6
        System.out.println("phi(10) = " + phiOptimized(10)); // Expected: 4
        System.out.println("phi(7) = " + phiOptimized(7)); // Expected: 6
        System.out.println("phi(12) = " + phiOptimized(12)); // Expected: 4 (1, 5, 7, 11)
        System.out.println("phi(36) = " + phiOptimized(36)); // Expected: 12
    }
}

Java implementation of the optimized φ(n) calculation using prime factorization.

Method 3: Sieve-based Approach for Multiple φ(n) Values

If you need to compute φ(n) for all numbers up to a certain limit (e.g., for a range of values or in competitive programming), a sieve-based approach is the most efficient. Similar to the Sieve of Eratosthenes for finding primes, you can precompute all φ values up to a limit in O(N log log N) time.

import java.util.Arrays;

public class EulerTotientSieve {

    // Sieve method to compute Euler's Totient Function for all numbers up to N
    public static int[] phiSieve(int N) {
        if (N < 0) {
            throw new IllegalArgumentException("Input must be a non-negative integer.");
        }
        int[] phi = new int[N + 1];

        // Initialize phi[i] = i
        for (int i = 0; i <= N; i++) {
            phi[i] = i;
        }

        // Apply the formula: phi[i] = phi[i] - phi[i]/p for each prime p
        for (int i = 2; i <= N; i++) {
            if (phi[i] == i) { // i is a prime number
                for (int j = i; j <= N; j += i) {
                    phi[j] -= phi[j] / i;
                }
            }
        }
        return phi;
    }

    public static void main(String[] args) {
        int limit = 10;
        int[] phiValues = phiSieve(limit);

        System.out.println("Euler's Totient Function values up to " + limit + ":");
        for (int i = 0; i <= limit; i++) {
            System.out.println("phi(" + i + ") = " + phiValues[i]);
        }
        // Expected:
        // phi(0) = 0
        // phi(1) = 1
        // phi(2) = 1
        // phi(3) = 2
        // phi(4) = 2
        // phi(5) = 4
        // phi(6) = 2
        // phi(7) = 6
        // phi(8) = 4
        // phi(9) = 6
        // phi(10) = 4
    }
}

Java implementation of the Sieve-based φ(n) calculation for a range of numbers.