5
$\begingroup$

I'm teaching myself cryptography but have realised that it has a lot of number theory as a part of it, one area which I'm a bit confused over is the Miller-Rabin test and how to use it in questions. A question which I have come across is:

Prove that $ n^2=4 \space mod \space p $ if $p$ {is an odd prime?} then there are two solutions $ n = \pm2 $ if $ p $ is an odd prime

Find an example of p where $n^2 = 9 \space mod \space p$ has one solution for $n \space mod \space p$

the part in curly brackets is missing from the question I am assuming that this is a mistake and what is inside the brackets should, in fact, be there.

Any help with this question would be extremely helpful and really appreciated!

EDIT: Forgot to add in this line:

The Miller-Rabin Test uses the fact that the only two solutions to the equation $n^2=1 \space mod \space p$ are $ n=\pm1 $ if $p$ is an odd prime

$\endgroup$
  • $\begingroup$ How are those questions related to the Miller-Rabin-Test ? $\endgroup$ – Peter Mar 29 '17 at 11:43
  • 1
    $\begingroup$ @Peter The Miller-Rabin Test uses the fact that the only two solutions to the equation $n^2=1 \space mod \space p$ are $n= \pm 1$ if $p$ is an odd prime $\endgroup$ – Unblazon Mar 29 '17 at 11:51
  • $\begingroup$ $n^2\equiv 4\mod p$ means $p|n^2-4=(n-2)(n+2)$. A prime divides a product if and only if it divides one of the factors. If $p$ is odd, then $-2\ne 2\mod p$, so we have two distinct solutions. For the second question, you can choose $p=2$ or $p=3$. For every $p>3$, we have again two distinct solutions. $\endgroup$ – Peter Mar 29 '17 at 12:16

Your Answer

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

Browse other questions tagged or ask your own question.