2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Peter Jan 8 '16 at 20:27
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.