home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9402 < prev    next >
Encoding:
Text File  |  1992-07-22  |  2.5 KB  |  53 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!mcsun!Germany.EU.net!Urmel.Informatik.RWTH-Aachen.DE!martin
  3. From: martin@math.rwth-aachen.de (  Martin Schoenert)
  4. Subject: Re: Quadratic Residue Question
  5. Message-ID: <martin.711805467@bert>
  6. Sender: news@Urmel.Informatik.RWTH-Aachen.DE (Newsfiles Owner)
  7. Nntp-Posting-Host: bert.math.rwth-aachen.de
  8. Organization: Rechnerbetrieb Informatik  /  RWTH Aachen
  9. References: <1992Jul17.185526.26121@leela.cs.orst.edu> <1992Jul17.210332.2105@cs.umn.edu> <Jul.17.21.03.32.1992.829@no.rutgers.edu>
  10. Date: 22 Jul 92 11:44:27 GMT
  11. Lines: 40
  12.  
  13. In his article of 18-Jul-92 bumby@no.rutgers.edu (Richard Bumby) writes:
  14.  
  15.     Euler's expression for the Legendre symbol, which only makes sense if
  16.     p is prime, can be calculated in O(log p) steps by repeated squaring.
  17.     It is fairly common for textbooks in elementary number theory to note
  18.     that reciprocity leads to a fast computation of Legendre symbols, but
  19.     it turns out not to be significantly faster than Euler's criterion.
  20.  
  21. In  GAP (a system for computational  group  theory, which  supports large
  22. integers) computing the value  of $J(n/m)$  where  $n$  and $m$  are both
  23. about 100 digits long takes roughly  600 ms  on a DECstation  5120.   But
  24. computing $J(n/m)$ using quadratic reciprocity takes only 6 ms.  Thus for
  25. numbers of this size it is already about 100 times faster.
  26.  
  27. This  is to be expected.   As you note Euler's expression can be computed
  28. in $O(log p)$ steps.  However, it is important to note that each of those
  29. steps involves  a  multiplication of two numbers  with $O(log p)$ digits,
  30. and therefore about $O((log p)^2)$ bit operations.  So evaluating Euler's
  31. expressions takes a total of $O((log p)^3)$ bit operations.  On the other
  32. hand the algorithm that  uses quadratic reciprocity also takes $O(log p)$
  33. steps, but the numbers are getting smaller with each step.  The behaviour
  34. is very similar to the Euclidean algorithm, and in fact the total time is
  35. $O((log p)^2)$ (just like the Euclidean algorithm).
  36.  
  37. You continue:
  38.  
  39.     Thus quadratic reciprocity must be important for some other reason :-).
  40.  
  41.     -- 
  42.     R. T. Bumby **  Rutgers Math ||   Amer. Math. Monthly Problems Editor
  43.     bumby@math.rutgers.edu       || P.O. Box 10971 New Brunswick, NJ08906-0971
  44.     bumby@dimacs.rutgers.edu     || Phone: [USA] 908 932 0277 * FAX 908 932 5530
  45.  
  46. Indeed.
  47.  
  48. Martin.
  49.  
  50. --
  51. Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,  +49 241 804551
  52. Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany
  53.