Você poderia sugerir um método determinístico rápido que seja útil na prática, para testar se um número grande é primo ou não?

Além disso, eu gostaria de saber como usar corretamente os testes não determinísticos de primalidade. Por exemplo, se eu estiver usando esse método, posso ter certeza de que um número não será primo se a saída for "não", mas e o outro caso, quando a saída for "provavelmente"? Preciso testar a primalidade manualmente neste caso?

Desde já, obrigado.