NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/sci/math/14432

Text File | 1992-11-05 | 3.7 KB | 89 lines

Newsgroups: sci.math
Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!SAIL.Stanford.EDU!rivin
From: [e-mail] (Igor Rivin)
Subject: Re: How to respond to enthusiasm [Was Re: Help X^2 == Y mod N]
Message-ID: <[e-mail]>
Sender: [e-mail]
Organization: Computer Science Department,  Stanford University.
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Thu, 5 Nov 1992 17:40:33 GMT
Lines: 77

In article <[e-mail]> [e-mail] (Robert D. Silverman) writes:
>In article <[e-mail]> [e-mail] (Michael L. Brundage) writes:
>:[e-mail] (Robert D. Silverman) writes:
>:
>:>In article <[e-mail]> [e-mail] (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.