Jacobi Symbol

Source Code

import java.util.Scanner;

public class JacobiSymbol {
    public static int jacobiSymbol(int a, int p) {
        if (p <= 2 || p % 2 == 0) {
            throw new IllegalArgumentException("p must be an odd prime.");
        }

        int result = 1;
        a = a % p;

        while (a != 0) {
            while (a % 2 == 0) {
                a /= 2;
                int k = p % 8;
                if (k == 3 || k == 5) {
                    result = -result;
                }
            }
            int temp = a;
            a = p;
            p = temp;

            if (a % 4 == 3 && p % 4 == 3) {
                result = -result;
            }
            a = a % p;
        }

        if (p == 1) {
            return result;
        } else {
            return 0;
        }
    }

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

        System.out.print("Enter (a): ");
        int a = scanner.nextInt();
        System.out.print("Enter (p): ");
        int p = scanner.nextInt();

        int result = jacobiSymbol(a, p);

        System.out.println("Result of J(a/p): " + result);

        scanner.close();
    }
}