home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14415 < prev    next >
Encoding:
Text File  |  1992-11-05  |  3.1 KB  |  68 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!spool.mu.edu!agate!linus!linus.mitre.org!gauss!bs
  3. From: bs@gauss.mitre.org (Robert D. Silverman)
  4. Subject: Re: How to respond to enthusiasm [Was Re: Help X^2 == Y mod N]
  5. Message-ID: <1992Nov5.131125.22075@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: gauss.mitre.org
  8. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  9. References: <1992Nov3.042721.2035@vela.acs.oakland.edu> <1992Nov3.114800.23056@linus.mitre.org> <1da1ggINNk95@gap.caltech.edu>
  10. Date: Thu, 5 Nov 1992 13:11:25 GMT
  11. Lines: 55
  12.  
  13. In article <1da1ggINNk95@gap.caltech.edu> mokie@cco.caltech.edu (Michael L. Brundage) writes:
  14. :bs@fatima.mitre.org (Robert D. Silverman) writes:
  15. :
  16. :>In article <1992Nov3.042721.2035@vela.acs.oakland.edu> phkahler@vela.acs.oakland.edu (KAHLER PAUL H.) writes:
  17. :>:I would like to know if any one knows of a (good) method of finding X in
  18. :>:the following congruence:
  19. :>:
  20. :>:X^2 == Y mod N        given Y and N
  21. :>:
  22. :>:I know how to determine if X exists and how to find it if N is prime.
  23.    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  24.  
  25. :>:However, my N is not prime.
  26. :>:
  27. :>:My math prof told me there is a way but he didn't know it off the top of his
  28. :>:head. I checked the library and can't find it. I'm not convinced that anyone
  29. :>:has a way, or if it can be done in general. (oh boy! an unsolved problem?!)
  30. :> 
  31. :>Its trivial.
  32. :
  33. :This is being picky, but when someone says "Oh boy!" about a problem, and
  34. :someone else replies with "It's trivial"  it (at first, at least)
  35. :either (a) sounds egotistical or (b) squelches the enthusiasm of the poser.
  36. :Of course, you probably just meant "It's not a hard problem, see, here's the
  37. :way to do it," but it sounds much less kind than that on a first (and
  38. :second, for that matter) reading.
  39.  
  40. As you may recall, the original poser said that he *already knew* how
  41. to solve square roots modulo a prime. The best algorithm(s)
  42. for doing this are variations of a random method due to Shanks, that 
  43. searches for a quadratic non-residue.  Direct methods are known when the prime
  44. is 3 mod 4, or 5 mod 8, but in other cases there does not seem to be a
  45. fast *deterministic* method.
  46.  
  47. For someone who knows this much, factoring the modulus and using the
  48. Chinese remainder theorem should indeed be trivial, because understanding
  49. the first problem itself isn't trivial.
  50.  
  51. Of course, maybe the original poser really did NOT know how to find 
  52. square roots modulo a prime and was doing it by some stupid method, like
  53. direct search. However, when someone says that he knows how to do something,
  54. I have no reason to doubt him/her.
  55.  
  56. In any event, I tend to use the word 'trivial' to refer to something
  57. that is elementary. In this case, understanding the method requires
  58. nothing more than high school algebra.
  59.  
  60. Implying that the answer to the original question is NON-trivial would
  61. be insulting to the reader, rather than the other way around.
  62.  
  63. --
  64. Bob Silverman
  65. These are my opinions and not MITRE's.
  66. Mitre Corporation, Bedford, MA 01730
  67. "You can lead a horse's ass to knowledge, but you can't make him think"
  68.