test di primalità

Un test di primalità è un algoritmo che, applicato ad un numero intero, ha lo scopo di determinare se esso è primo. Non va confuso con un algoritmo di fattorizzazione, che invece ha lo scopo di determinare i fattori primi di un numero: quest'ultima operazione è infatti generalmente più lunga e complessa. Con la significativa eccezione del metodo delle curve ellittiche (noto come ECPP) e dell'algoritmo AKS, i test di primalità più efficienti oggi utilizzati sono probabilistici, nel senso che danno una risposta certa solo quando rispondono NO (ossia quando dicono che il numero è composto) mentre nel caso di risposta SÌ assicurano soltanto un limite inferiore alla probabilità che il numero sia primo. L'errore dei test può essere però reso piccolo a piacere.