next up previous contents
Next: Probabilistic Encryption Up: A probabilistic test for Previous: A probabilistic test for

Analysis of the Rabin test

We will calculate how many $a$ are witnesses that 247 is not a prime. Our analysis will make use of the fact that $247=13(19)$ and that 2 is a primitive root for both 13 and 19. However, it should be emphasized that this information (which will not be available in general) was not used when we did the test itself.


How many $a$ satisfy $a^{123}\equiv1\hbox{ (mod }247)$? We must have $a^{123}\equiv1\hbox{ (mod }13)$and $a^{123}\equiv1\hbox{ (mod }19)$. Let $a\equiv2^x\hbox{ (mod }13)$. Then we must have $123x$divisible by 12. This gives the possible values $0,4,8$ for $x$, which implies $a\equiv1,3$, or 9 mod 13. Similarly, if $a\equiv2^x\hbox{ (mod }19)$, $123x$must be divisible by 18, which leads to $a\equiv1,7$, or 11 mod 19. (we actually found 178 above by solving $a\equiv9\hbox{ (mod }13)$ and $a\equiv7\hbox{ (mod }19))$The 3 choices mod 13 and mod 19 imply there are 9 $a$ with $a^{123}\equiv1$.


How many $a$ satisfy $a^{123}\equiv-1\hbox{ (mod }247)$? If $2^{123x}\equiv-1\hbox{ (mod }13)$, we must have $123x\equiv6\hbox{ (mod }12)$, which leads to $a\equiv4,7$, or 17 mod 13. Similarly, we get $a\equiv8,18$, or 12 mod 19. Thus we get 9 $a$ satisfying this condition.


If we choose $1\le a\le246$ at random, the chances of getting an $a$ that is not a witness are $18/246\approx.073$. If we do the test 5 times, the chance of incorrectly concluding 247 is a prime is $\approx2(10^{-6})$.


[We actually did more work than necessary, ident ifying the exact set of numbers which would lead to a wrong conclusion. If we only want to count how many numbers there are, we could make use of observations such as that, for any $k$, an equation $123x\equivk\hbox{ (mod }12)$will either have 3 solutions or no solutions.]

Theorem 19 (Rabin)   If $p$ is not a prime, at least $3/4$of $1\le a\le p-1$ are witnesses.

This implies that for any non-prime $p$, the chance of being incorrectly identified after 5 tests is $\le4^{-5}<.001$.

next up previous contents
Next: Probabilistic Encryption Up: A probabilistic test for Previous: A probabilistic test for
Translated from LaTeX by Scott Sutherland
1998-03-15