Prueba de primalidad AKS

Hay varias pruebas de primalidad disponibles para verificar si el número es primo o no, como el teorema de Fermat , la prueba de primalidad de Miller-Rabin y muchas más. Pero el problema con todos ellos es que todos son de naturaleza probabilística. Entonces, aquí viene otro método, es decir, la prueba de primalidad AKS (prueba de primalidad Agrawal-Kayal-Saxena) y es determinísticamente correcta para cualquier número general.
Características de la prueba de primalidad AKS: 
1. El algoritmo AKS se puede utilizar para verificar la primalidad de cualquier número general dado. 
2. El tiempo máximo de ejecución del algoritmo se puede expresar como un polinomio sobre el número de dígitos en el número de destino. 
3. Se garantiza que el algoritmo distinguirá de forma determinista si el número objetivo es primo o compuesto. 
4. La corrección de AKS no está condicionada a ninguna hipótesis subsidiaria no probada.
La prueba de primalidad AKS se basa en el siguiente teorema: un número entero n mayor que 2 es primo si y solo si la relación de congruencia polinomial se 

cumple para algunos coprimos con n . Aquí x es solo un símbolo formal.
La prueba AKS evalúa la igualdad haciendo que la complejidad dependa del tamaño de r . Esto se expresa como 

que se puede expresar en un término más simple que 

para algunos polinomios f y g. 
Esta congruencia se puede verificar en tiempo polinomial cuando r es polinomial a los dígitos de n. El algoritmo AKS evalúa esta congruencia para un gran conjunto de valores, cuyo tamaño es polinomial a los dígitos de n. La prueba de validez del algoritmo AKS muestra que uno puede encontrar r y un conjunto de valores con las propiedades anteriores, de modo que si las congruencias se mantienen, entonces n es una potencia de un número primo. El enfoque de fuerza bruta requeriría la expansión del polinomio (x – a)^n y una reducción (mod n) de los n + 1 coeficientes resultantes.
Como a debería ser coprimo con n. Entonces, para implementar este algoritmo podemos verificar tomando a = 1, pero para valores grandes de n debemos tomar valores grandes de a. 
El algoritmo se basa en la condición de que si n es cualquier número, entonces es primo si, 
( x – 1 )^n – ( x^n – 1) es divisible por n.
Comprobación de n = 3:
(x-1)^3 – (x^3 – 1) 
= (x^3 – 3x^2 + 3x – 1) – (x^3 – 1) 
= -3x^2 + 3x
Como todos los coeficientes son divisibles por n, es decir, 3, 3 (n) es primo. A medida que aumenta el número, aumenta el tamaño. 
El código aquí se basa en esta condición y puede verificar números primos hasta 64 .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ code to check if number is prime. This
// program demonstrates concept behind AKS
// algorithm and doesn't implement the actual
// algorithm (This works only till n = 64)
#include <bits/stdc++.h>
using namespace std;
 
// array used to store coefficients .
long long c[100];
 
// function to calculate the coefficients
// of (x - 1)^n - (x^n - 1) with the help
// of Pascal's triangle .
void coef(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];
    }
}
 
// function to check whether
// the number is prime or not
bool isPrime(int n)
{
    // Calculating all the coefficients by
    // the function coef and storing all
    // the coefficients in c array .
    coef(n);
 
    // subtracting c[n] and adding c[0] by 1
    // as ( x - 1 )^n - ( x^n - 1), here we
    // are subtracting c[n] by 1 and adding
    // 1 in expression.
    c[0]++, c[n]--;
 
    // checking all the coefficients whether
    // they are divisible by n or not.
    // if n is not prime, then loop breaks
    // and (i > 0).
    int i = n;
    while (i-- && c[i] % n == 0)
        ;
 
    // Return true if all coefficients are
    // divisible by n.
    return i < 0;
}
 
// driver program
int main()
{
    int n = 37;
    if (isPrime(n))
        cout << "Prime" << endl;
    else
        cout << "Not Prime" << endl;
    return 0;
}

// Java code to check if number is prime. This
// program demonstrates concept behind AKS
// algorithm and doesn't implement the actual
// algorithm (This works only till n = 64)
 
class GFG {
    // array used to store coefficients .
    static long c[] = new long[100];
 
    // function to calculate the coefficients
    // of (x - 1)^n - (x^n - 1) with the help
    // of Pascal's triangle .
    static void coef(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];
        }
    }
 
    // function to check whether
    // the number is prime or not
    static boolean isPrime(int n)
    {
        // Calculating all the coefficients by
        // the function coef and storing all
        // the coefficients in c array .
        coef(n);
 
        // subtracting c[n] and adding c[0] by 1
        // as ( x - 1 )^n - ( x^n - 1), here we
        // are subtracting c[n] by 1 and adding
        // 1 in expression.
        c[0]++;
        c[n]--;
 
        // checking all the coefficients whether
        // they are divisible by n or not.
        // if n is not prime, then loop breaks
        // and (i > 0).
        int i = n;
        while ((i--) > 0 && c[i] % n == 0)
            ;
 
        // Return true if all coefficients are
        // divisible by n.
        return i < 0;
    }
    // Driver code
    public static void main(String[] args)
    {
        int n = 37;
        if (isPrime(n))
            System.out.println("Prime");
        else
            System.out.println("Not Prime");
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 code to check if
# number is prime. This
# program demonstrates concept
# behind AKS algorithm and
# doesn't implement the actual
# algorithm (This works only
# till n = 64)
 
# array used to
# store coefficients .
c = [0] * 100;
 
# function to calculate the
# coefficients of (x - 1)^n -
# (x^n - 1) with the help
# of Pascal's triangle .
def coef(n):
    c[0] = 1;
    for i in range(n):
        c[1 + i] = 1;
        for j in range(i, 0, -1):
            c[j] = c[j - 1] - c[j];
        c[0] = -c[0];
         
# function to check whether
# the number is prime or not
def isPrime(n):
     
    # Calculating all the coefficients
    # by the function coef and storing
    # all the coefficients in c array .
    coef(n);
     
    # subtracting c[n] and adding
    # c[0] by 1 as ( x - 1 )^n -
    # ( x^n - 1), here we are
    # subtracting c[n] by 1 and
    # adding 1 in expression.
    c[0] = c[0] + 1;
    c[n] = c[n] - 1;
     
    # checking all the coefficients
    # whether they are divisible by
    # n or not. if n is not prime,
    # then loop breaks and (i > 0).
    i = n;
    while (i > -1 and c[i] % n == 0):
        i = i - 1;
     
    # Return true if all coefficients
    # are divisible by n.
    return True if i < 0 else False;
 
# Driver Code
n = 37;
if (isPrime(n)):
    print("Prime");
else:
    print("Not Prime");
     
# This code is contributed by mits

// C# code to check if number is prime. This
// program demonstrates concept behind AKS
// algorithm and doesn't implement the actual
// algorithm (This works only till n = 64)
using System;
 
class GFG {
     
    // array used to store coefficients .
    static long []c = new long[100];
 
    // function to calculate the coefficients
    // of (x - 1)^n - (x^n - 1) with the help
    // of Pascal's triangle .
    static void coef(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];
        }
    }
 
    // function to check whether
    // the number is prime or not
    static bool isPrime(int n)
    {
         
        // Calculating all the coefficients by
        // the function coef and storing all
        // the coefficients in c array .
        coef(n);
 
        // subtracting c[n] and adding c[0] by 1
        // as ( x - 1 )^n - ( x^n - 1), here we
        // are subtracting c[n] by 1 and adding
        // 1 in expression.
        c[0]++;
        c[n]--;
 
        // checking all the coefficients whether
        // they are divisible by n or not.
        // if n is not prime, then loop breaks
        // and (i > 0).
        int i = n;
        while ((i--) > 0 && c[i] % n == 0)
            ;
 
        // Return true if all coefficients are
        // divisible by n.
        return i < 0;
    }
     
    // Driver code
    public static void Main()
    {
        int n = 37;
        if (isPrime(n))
            Console.WriteLine("Prime");
        else
            Console.WriteLine("Not Prime");
    }
}
 
// This code is contributed by anuj_67.

<?php
// PHP code to check if number
// is prime. This program
// demonstrates concept behind
// AKS algorithm and doesn't
// implement the actual
// algorithm (This works only
// till n = 64)
 
// array used to
// store coefficients .
global $c;
 
// function to calculate
// the coefficients
// of (x - 1)^n -
// (x^n - 1) with the help
// of Pascal's triangle .
function coef($n)
{
    $c[0] = 1;
    for ($i = 0; $i < $n; $c[0] = -$c[0], $i++)
    {
        $c[1 + $i] = 1;
 
        for ($j = $i; $j > 0; $j--)
            $c[$j] = $c[$j - 1] - $c[$j];
    }
}
 
// function to check whether
// the number is prime or not
function isPrime($n)
{
    global $c;
     
    // Calculating all the
    // coefficients by the
    // function coef and
    // storing all the
    // coefficients in c array .
    coef($n);
 
    // subtracting c[n] and
    // adding c[0] by 1 as
    // ( x - 1 )^n - ( x^n - 1),
    // here we are subtracting c[n]
    // by 1 and adding 1 in expression.
    // $c[0]++; $c[$n]--;
     
    // checking all the coefficients whether
    // they are divisible by n or not.
    // if n is not prime, then loop breaks
    // and (i > 0).
    $i = $n;
    while ($i-- && $c[$i] % $n == 0)
 
    // Return true if all
    // coefficients are
    // divisible by n.
    return $i < 0;
}
 
    // Driver Code
    $n = 37;
    if (isPrime($n))
        echo "Not Prime", "\n";
    else
        echo "Prime", "\n";
 
// This code is contributed by aj_36
?>

<script>
 
// Javascript program to check if number is prime.
// This program demonstrates concept behind AKS
// algorithm and doesn't implement the actual
// algorithm (This works only till n = 64)
 
    // array used to store coefficients .
    let c = [];
   
    // function to calculate the coefficients
    // of (x - 1)^n - (x^n - 1) with the help
    // of Pascal's triangle .
    function coef(n)
    {
        c[0] = 1;
        for (let i = 0; i < n; c[0] = -c[0], i++) {
            c[1 + i] = 1;
   
            for (let j = i; j > 0; j--)
                c[j] = c[j - 1] - c[j];
        }
    }
   
    // function to check whether
    // the number is prime or not
    function isPrime(n)
    {
        // Calculating all the coefficients by
        // the function coef and storing all
        // the coefficients in c array .
        coef(n);
   
        // subtracting c[n] and adding c[0] by 1
        // as ( x - 1 )^n - ( x^n - 1), here we
        // are subtracting c[n] by 1 and adding
        // 1 in expression.
        c[0]++;
        c[n]--;
   
        // checking all the coefficients whether
        // they are divisible by n or not.
        // if n is not prime, then loop breaks
        // and (i > 0).
        let i = n;
        while ((i--) > 0 && c[i] % n == 0)
            ;
   
        // Return true if all coefficients are
        // divisible by n.
        return i < 0;
    }
 
// Driver code
 
        let n = 37;
        if (isPrime(n))
            document.write("Prime");
        else
            document.write("Not Prime");
 
</script>

Producción: 

Prime

Referencias:  
https://en.wikipedia.org/wiki/AKS_primality_test  
https://rosettacode.org/wiki/AKS_test_for_primes#C  
https://www.youtube.com/watch?v=HvMSRWTE2mI