Ho dato uno sguardo veloce all'algoritmo AKS e da quanto ho capito (la lettura è stata mooolto veloce quindi c'è una possibilità che possa sbagliarmi) usa lo stesso criterio probabilistico dell'algoritmo indicato nel link che l'autore del 3d ha postato,perciò non da la certezza della primalità,d'altra parte però per numeri molto grandi non bisogna aspettare il tempo di vita dell'universo con quello

Mi sbagliavo (la lettura era effettivamente troppo veloce),AKS da la certezza della primalità anche se ha una complessità polinomiale dell'ordine di n^12 con n numero di cifre.Però è veramente complesso come algoritmo.