Primality testing algorithm
A pragmatic answer: Use the Miller-Rabin test with 50 iterations.  The probability that a composite number will be wrongly declared prime by this test is at most $2^{-100}$ (see, e.g., here).  This is smaller than the chance of a cosmic ray causing a bitflip error that causes your program to output an erroneous result.  So, if you're not worried about cosmic rays, you shouldn't be worried about probabilistic algorithms.

An alternative: use any probabilistic algorithm to rule out composite numbers.  If the probabilistic algorithm claims the number is prime, use a deterministic primality test, or use a test that produces a primality certificate.  There are many such algorithms, and you can study the literature and find one which leads the best tradeoff between complexity of implementation vs speed on numbers of the size you care about.