2
$\begingroup$

I have question about a homework.

The question is:

Why can we be $100\%$ sure after $4$ tests for the special case of $p=13$?

I don't get it. I have a formula that states, that every test increases certainty by $\left(\frac14\right)^k$, where $k$ is the number of tests. So after $4$ tests I get around $99.6\%$ certainty, not $100\%.$

$\endgroup$
  • 3
    $\begingroup$ Speaking for myself, I am 100% certain for p=13 even before your first test :) $\endgroup$ – MooS Jul 24 '17 at 13:35
  • $\begingroup$ Here's a MathJax tutorial :) $\endgroup$ – Shaun Jul 24 '17 at 13:38
2
$\begingroup$

Actually your 'formula' is a statement that says that a non-prime number passes the Miller-Rabin-Test for at most 1/4 of all possible bases. That would be no more than three for the number 13. That answers your question.

$\endgroup$
  • $\begingroup$ i don't get it? What are the possible bases? $\endgroup$ – tevlon84 Jul 24 '17 at 14:00
  • $\begingroup$ Where does $1/4$ comes from ? (see Rabin's paper) It seems it reduces the problem to $n = p_1^{k_1} p_2^{k_2}$ and look at $x^{\phi(n)/t}$ versus $x^{n-1}$ where $t = gcd(\phi(n),n-1)$ $\endgroup$ – reuns Jul 27 '17 at 9:28
0
$\begingroup$

One way of thinking about it is that your $(1/4)^k$ is if you choose $k$ bases completely at random. But if you do this it is possible that you'll randomly pick the same base more than once, and of course this isn't optimal. So you can get a slightly better probability (than $(1/4)^k$) by making sure that you don't pick the same base twice.

If $p$ is large, this doesn't make much difference, since you're very unlikely to accidentally choose the same base twice anyway. But for small $p$, making sure you choose $k$ different bases can significantly improve the probability.

$\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.