How many times do I loop Solovay--Strassen primality test First, I am aware of this former thread:
math.stackexchange
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
 A: 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.
