From: rivin@SAIL.Stanford.EDU (Igor Rivin)
Subject: Re: How to respond to enthusiasm [Was Re: Help X^2 == Y mod N]
Organization: Computer Science Department,  Stanford University.
Date: Thu, 5 Nov 1992 17:40:33 GMT

In article <1992Nov5.131125.22075@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
>In article <1da1ggINNk95@gap.caltech.edu> mokie@cco.caltech.edu (Michael L. Brundage) writes:
>:bs@fatima.mitre.org (Robert D. Silverman) writes:
>:
>:>In article <1992Nov3.042721.2035@vela.acs.oakland.edu> phkahler@vela.acs.oakland.edu (KAHLER PAUL H.) writes:
>:>:I would like to know if any one knows of a (good) method of finding X in
>:>:the following congruence:
>:>:
>:>:X^2 == Y mod N        given Y and N
>:>:
>:>:I know how to determine if X exists and how to find it if N is prime.
>   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
>:>:However, my N is not prime.
>:>:
>:>:My math prof told me there is a way but he didn't know it off the top of his
>:>:head. I checked the library and can't find it. I'm not convinced that anyone
>:>:has a way, or if it can be done in general. (oh boy! an unsolved problem?!)
>:> 
>:>Its trivial.
>:
>:This is being picky, but when someone says "Oh boy!" about a problem, and
>:someone else replies with "It's trivial"  it (at first, at least)
>:either (a) sounds egotistical or (b) squelches the enthusiasm of the poser.
>:Of course, you probably just meant "It's not a hard problem, see, here's the
>:way to do it," but it sounds much less kind than that on a first (and
>:second, for that matter) reading.
> 
>As you may recall, the original poser said that he *already knew* how
>to solve square roots modulo a prime. The best algorithm(s)
>for doing this are variations of a random method due to Shanks, that 
>searches for a quadratic non-residue.  Direct methods are known when the prime
>is 3 mod 4, or 5 mod 8, but in other cases there does not seem to be a
>fast *deterministic* method.
>
>
>For someone who knows this much, factoring the modulus and using the
>Chinese remainder theorem should indeed be trivial, because understanding
>the first problem itself isn't trivial.
>
Firstly, the original poster's question could have been phrased as:

Assume we know how to solve this congruence mod a prime, how do we do
it for all integers?

It COULD have been phrased as "assume the Riemann Hypothesis holds" --
would you assume that the poster was God?


Secondly, you still seem to insist that all numbers are square-free.
Is that really true?

>Of course, maybe the original poser really did NOT know how to find 
>square roots modulo a prime and was doing it by some stupid method, like
>direct search. However, when someone says that he knows how to do something,
>I have no reason to doubt him/her.
>
>In any event, I tend to use the word 'trivial' to refer to something
>that is elementary.

This is an incredibly misguided view. "Trivial" and "elementary" are
completely orthogonal concepts.

> In this case, understanding the method requires
>nothing more than high school algebra.
>
>Implying that the answer to the original question is NON-trivial would
>be insulting to the reader, rather than the other way around.

Did you learn how to solve non-linear congruences by yourself, while
in high school, in total isolation,  or did
you learn it from a book or a class? (Yes, a problem course qualifies
as a class). If the latter, you have no right to say that the question
is trivial.