home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9435 < prev    next >
Encoding:
Internet Message Format  |  1992-07-22  |  1.8 KB
  1. Path: sparky!uunet!darwin.sura.net!mlb.semi.harris.com!uflorida!mailer.cc.fsu.edu!fsu1.cc.fsu.edu!rose
  2. From: rose@fsu1.cc.fsu.edu (Kermit Rose)
  3. Newsgroups: sci.math
  4. Subject: Re: Quadratic Residue Question
  5. Message-ID: <1992Jul18.122729.26174@mailer.cc.fsu.edu>
  6. Date: 23 Jul 92 04:29:18 GMT
  7. References: <1992Jul17.185526.26121@leela.cs.orst.edu> <1992Jul17.210332.2105@cs.umn.edu>
  8. Reply-To: rose@fsu1.cc.fsu.edu
  9. Organization: Florida State University
  10. Lines: 47
  11. News-Software: VAX/VMS VNEWS 1.3-4
  12.  
  13. In article <1992Jul17.210332.2105@cs.umn.edu>, pires@cs.umn.edu (Luiz S. Pires) writes...
  14. > 
  15. >  ....
  16. > 
  17. >  Given an arbitrary number a and an odd prime p, I am trying to write a 
  18. > subroutine that decides whether a is a quadratic residue mod p.
  19. > 
  20. > ....
  21.  
  22. >  For example, if we have, say, a=31123 and p=45667, then I am not clear on
  23. > how to proceed. I thought of using Euler's lemma (or whatever it is called)
  24. > and calculate a^((p-1)/2) (mod p). That, however, would seem to have very poor
  25. > worst case performance. 
  26. > 
  27. >   Does anyone have an efficient algorithm for determining this? Am I missing
  28. > something obvious here? Any help would be most welcome!
  29. > 
  30. >  Thanks in advance.
  31. > 
  32. >    Luiz.
  33. >    (pires@cs.umn.edu)
  34.  
  35. Actually, you can calculate a(([p-1]/2) (mod p) very efficiently.  Example, 
  36.  
  37. a^3 = a^2 a^1
  38. a^4= (a^2)^2
  39. a^5 = (a^2)^2  a^1
  40. a^6 = (  (a^2 a^1)  )^2
  41. a^7 = ( (a^2 a^1) )^2   a^1
  42.  
  43. etc.   
  44. simply think of k = [p-1]/2 in base 2.
  45.  
  46. k = a_m 2^m + a_(m-1) 2 ^(m-1) + ... + a_1 2 + a_0
  47.  
  48. k = ((((( ....  a_m 2+a_[m-1] )2 +...   )2 + a_1   2)+ a_0
  49.  
  50. b_0 = b^k
  51. b_m = b^a_m
  52. b_[m-1] = b_m^2  b^a_m-1
  53. ..
  54. b_1 = b_2 ^2  b^a_1
  55. b_0 = b_1 ^2  b^a_0
  56.  
  57. rose@fsu1.cc.fsu.edu          To be sure I see your response, use e-mail.
  58. -----------------------------------------------------------------------
  59. Be of good cheer, for it is much more fun than being depressed.
  60.