First, I am aware of this former thread:
Yet it doesn't answer my question.
If I want to check if an integer $n$ is prime using the Solovay--Strassen test, how many times do I have to loop over this test? As the error probability is at most $\frac1{2^k}$, one might want to choose $k$ such that $\frac1{2^k}< 10^{-10}$ or $<10^{-100}$, or whatever.
Is there a reasonable bound which is somehow comparable to the probability of a calculation error inside my cpu/pc?
Best,
reinbot
If you are looking at small inputs, we can construct deterministic sets. The first 12 primes (primes to 37) suffice for 32-bit inputs; the first 23 primes (to 83) suffice for all 64-bit inputs. Of course we could find more efficient sets just like people have done for Miller-Rabin. These sets are made possible since the Euler pseudoprimes are subsets of the Fermat pseudoprimes to the same base (Pomerance,Selfridge,Wagstaff 1980), so the Feitsma/Galway database of base-2 pseudoprimes lets us quickly find all the base-2 epsps under 2^64.
For crypto use, I think looking at FIPS 186-4 and their suggestions on error bounds, translated from the 4^-k of Miller-Rabin to the 2^-k of Solovay-Strassen, would be worthwhile. Their suggestions are from 2^-80 to 2^-128 for key generation.
Informally, Peter's numbers look reasonable to me.
Miller-Rabin is more efficient and there is a lot more literature about using it. It may be worthwhile to use it instead from a practicality standpoint, but that's an aside.