# 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

• I think, $10^{-20}$ is absolutely sufficient. If the number is very large and the test time-consuming, you can stop at $10^{-9}$, or so. If the number is "small" (lets say, $400$ digits or less) , the primilaty can be proven efficiently. – Peter Jan 8 '16 at 20:27