1
$\begingroup$

I was trying to solve a question by programming , where one needs to find $X$ such that $X^2\;mod\;M=N$ ,such that $0 \le N \lt M \le 10^6$. Now here I was able to prove:

Let $Y = q * M + X$ where $0 \le X \lt M$ and $1 \le q$. So $M-1 \lt Y$
$Y^2 \;mod\; M = ((Y \;mod\; M) * (Y \;mod\; M)) \;mod\; M = (X * X) \;mod\; M = X^2 \;mod\; M$
But $0 \le X \lt M$

So $0 \le X \lt M$

However few optimisations has been suggested(In the given answer in book) such that :

1.) $\sqrt{N} \le X \lt M$
2.)Further it is also mentioned that the value of $X^2\;mod\;M$ shall repeat from $M/2$ on wards. So we can change the upper bound from $(M-1)$ to $M/2$

How to prove these above two optimsations mathematically?

$\endgroup$
7
  • $\begingroup$ Can I please know the reason why it was downvoted? $\endgroup$
    – Sourajit
    Jun 27, 2018 at 15:33
  • $\begingroup$ It does not appear you used MathJax or LaTeX, which are probably the main reasons. $\endgroup$
    – Prime
    Jun 27, 2018 at 15:50
  • $\begingroup$ Is this ok now? $\endgroup$
    – Sourajit
    Jun 27, 2018 at 16:29
  • $\begingroup$ It’s better. What does the percent symbol mean? $\endgroup$
    – Prime
    Jun 27, 2018 at 16:34
  • 1
    $\begingroup$ Thanks...I have mentioned that $\endgroup$
    – Sourajit
    Jun 27, 2018 at 16:46

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .