Step by Step solution about How to resolve the algorithm AKS test for primes step by step in the Java programming language

Description: The code snippet implements an algorithm to test whether a given number n is prime or not, and it also calculates the coefficients of the polynomial (x-1)^n.

Implementation:

• coeff(n):

  • Calculates the coefficients of the polynomial (x-1)^n using the recurrence relation c[i] = c[i-1] - c[i] and c[0] = 1.

• isPrime(n):

  • Checks if the given number n is prime.
  • To do this, it first calculates the coefficients of (x-1)^n using coeff(n).
  • Then, it increments c[0] and decrements c[n] to transform the polynomial into a binomial (x-1)^n + 1.
  • Finally, it checks if all the coefficients except c[0] are divisible by n, in which case n is prime.

• show(n):

  • Prints the polynomial (x-1)^n by iterating over the coefficients and printing the terms.

Example:

• For n = 2, the polynomial (x-1)^2 is (x-1)^2 = 1 - 2x + 1x^2.
• For n = 3, the polynomial (x-1)^3 is (x-1)^3 = 1 - 3x + 3x^2 - 1x^3.

Note: The code uses constant arrays to store the coefficients of the polynomial, which is not very efficient for large values of n. However, it demonstrates the concept of calculating polynomial coefficients and testing primality using algebraic properties.

public class AksTest {
    private static final long[] c = new long[64];

    public static void main(String[] args) {
        for (int n = 0; n < 10; n++) {
            coeff(n);
            show(n);
        }

        System.out.print("Primes:");
        for (int n = 1; n < c.length; n++)
            if (isPrime(n))
                System.out.printf(" %d", n);

        System.out.println();
    }

    static void coeff(int n) {
        c[0] = 1;
        for (int i = 0; i < n; c[0] = -c[0], i++) {
            c[1 + i] = 1;
            for (int j = i; j > 0; j--)
                c[j] = c[j - 1] - c[j];
        }
    }

    static boolean isPrime(int n) {
        coeff(n);
        c[0]++;
        c[n]--;

        int i = n;
        while (i-- != 0 && c[i] % n == 0)
            continue;
        return i < 0;
    }

    static void show(int n) {
        System.out.print("(x-1)^" + n + " =");
        for (int i = n; i >= 0; i--) {
            System.out.print(" + " + c[i] + "x^" + i);
        }
        System.out.println();
    }
}