Primality Test

Source Code

import java.util.Random;
import java.util.Scanner;

public class PrimalityTest {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int choice;

        do {
            System.out.println();
            System.out.println("--- PRIMALITY TEST MENU ---");
            System.out.println("1. Miller-Rabin");
            System.out.println("2. Solovay-Strassen");
            System.out.println("3. Exit");
            System.out.println();
            System.out.print("Enter your choice: ");

            choice = scanner.nextInt();

            System.out.println();

            switch (choice) {
                case 1:
                    System.out.print("Enter a number to test: ");
                    int number1 = scanner.nextInt();
                    System.out.println("Miller-Rabin Test Result: " + millerRabin(number1, 5));
                    break;
                case 2:
                    System.out.print("Enter a number to test: ");
                    int number2 = scanner.nextInt();
                    System.out.println("Solovay-Strassen Test Result: " + solovayStrassen(number2, 5));
                    break;
                case 3:
                    System.out.println("Exiting...");
                    break;
                default:
                    System.out.println("Invalid choice. Please try again.");
            }
        } while (choice != 3);

        scanner.close();
    }

    public static boolean millerRabin(int n, int k) {
        if (n <= 1 || n == 4) return false;
        if (n <= 3) return true;

        int r = 0;
        int d = n - 1;
        while (d % 2 == 0) {
            d /= 2;
            r++;
        }

        Random rand = new Random();
        for (int i = 0; i < k; i++) {
            int a = 2 + rand.nextInt(n - 4);
            int x = modularExponentiation(a, d, n);
            if (x == 1 || x == n - 1) continue;

            boolean composite = true;
            for (int j = 0; j < r - 1; j++) {
                x = modularExponentiation(x, 2, n);
                if (x == n - 1) {
                    composite = false;
                    break;
                }
            }
            if (composite) return false;
        }
        return true;
    }

    public static boolean solovayStrassen(int n, int k) {
        if (n <= 1) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        Random rand = new Random();
        for (int i = 0; i < k; i++) {
            int a = 1 + rand.nextInt(n - 1);
            int x = jacobiSymbol(a, n);
            if (x == 0 || modularExponentiation(a, (n - 1) / 2, n) != (x + n) % n) {
                return false;
            }
        }
        return true;
    }

    public static int jacobiSymbol(int a, int n) {
        int result = 1;
        a = a % n;
        if (a < 0) a += n;

        while (a != 0) {
            while (a % 2 == 0) {
                a /= 2;
                int r = n % 8;
                if (r == 3 || r == 5) result = -result;
            }
            int temp = a;
            a = n;
            n = temp;
            if (a % 4 == 3 && n % 4 == 3) result = -result;
            a = a % n;
        }
        return n == 1 ? result : 0;
    }

    public static int modularExponentiation(int base, int exp, int mod) {
        int result = 1;
        base = base % mod;
        while (exp > 0) {
            if ((exp & 1) == 1) result = (result * base) % mod;
            exp >>= 1;
            base = (base * base) % mod;
        }
        return result;
    }
}

Output

--- PRIMALITY TEST MENU ---
1. Miller-Rabin
2. Solovay-Strassen
3. Exit

Enter your choice: 1

Enter a number to test: 29
Miller-Rabin Test Result: true

--- PRIMALITY TEST MENU ---
1. Miller-Rabin
2. Solovay-Strassen
3. Exit

Enter your choice: 1

Enter a number to test: 471
Miller-Rabin Test Result: false

--- PRIMALITY TEST MENU ---
1. Miller-Rabin
2. Solovay-Strassen
3. Exit

Enter your choice: 1

Enter a number to test: 6211
Miller-Rabin Test Result: true

--- PRIMALITY TEST MENU ---
1. Miller-Rabin
2. Solovay-Strassen
3. Exit

Enter your choice: 2

Enter a number to test: 61
Solovay-Strassen Test Result: true

--- PRIMALITY TEST MENU ---
1. Miller-Rabin
2. Solovay-Strassen
3. Exit

Enter your choice: 237

Invalid choice. Please try again.

--- PRIMALITY TEST MENU ---
1. Miller-Rabin
2. Solovay-Strassen
3. Exit

Enter your choice: 2

Enter a number to test: 237
Solovay-Strassen Test Result: false

--- PRIMALITY TEST MENU ---
1. Miller-Rabin
2. Solovay-Strassen
3. Exit

Enter your choice: 2

Enter a number to test: 4771
Solovay-Strassen Test Result: false

--- PRIMALITY TEST MENU ---
1. Miller-Rabin
2. Solovay-Strassen
3. Exit

Enter your choice: 3

Exiting...