home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9401 < prev    next >
Encoding:
Text File  |  1992-07-22  |  5.0 KB  |  130 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!darwin.sura.net!Sirius.dfn.de!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.711802292@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>
  10. Date: 22 Jul 92 10:51:32 GMT
  11. Lines: 117
  12.  
  13. In his article of 17-Jul-92 pires@cs.umn.edu (Luiz S. Pires) writes:
  14.  
  15.     Please forgive me if this is a trivial question. I am not a
  16.     mathematician, but I am trying to learn some number theory.
  17.  
  18.     Given an arbitrary number a and an odd prime p, I am trying to write a 
  19.     subroutine that decides whether a is a quadratic residue mod p.
  20.  
  21.     I am familiar with a few of the rules available for manipulating the
  22.     "Legendre Symbol", including the law of quadratic reciprocity. However I 
  23.     can't think of an efficient way for handling this problem in the general
  24.     case.
  25.  
  26. There is an extension of the Legendre symbol, called the Jacobi-Kronecker
  27. symbol, which  does  not  require the denominator  to  be a  prime.   The
  28. precise definition is as follows.  Suppose that $m = p_1 p_2 ...  p_k$ as
  29. a product of primes, not necessarily different.  Then  for $n$ relatively
  30. prime  to  $m$ the  Jacobi-Kronecker  symbol  is  defined  by  $J(n/m)  =
  31. L'(n/p_1)  L'(n/p_2) ...  L'(n/p_k)$,  where  $L'(n/p)$  is the  Legendre
  32. symbol  $L(n/p)$   if  $p$  is  an   odd   prime  $L'(n,2)  =  L'(2,n)  =
  33. (-1)^{(n^2-1)/8}$.  Usually $J(n/m)$ is defined as  0, if $n$ and $m$ are
  34. not relatively prime.
  35.  
  36. The nice thing  is that the Jacobi-Kronecker symbol satisfies almost  the
  37. same  equalities  as  the  Legendre  symbol.  It is multiplicative in the
  38. numerator and  the *denominator*,  and  if $n, m$ are  relative prime odd
  39. positive integers then $J(n/m) = J(m/n) (-1)^{(n-1)*(m-1)/4}$.  So we can
  40. use those equalities to compute the value of the Jacobi-Kronecker symbol.
  41.  
  42. Note however that the equality $L( n / m ) = L( (n mod m) / m )$ does not
  43. carry  over  to  the Jacobi-Kronecker  symbol,  unless $m$  is odd.   For
  44. example $1  = J(1/2)  <>  J(3/2)  = -1$.   This  makes writing  a correct
  45. implementation  of a  function that  computes the Jacobi-Kronecker symbol
  46. somewhat tricky.
  47.  
  48. Here is a function that computes the Jacobi-Kronecker symbol.
  49.  
  50.     Jacobi := function ( n, m )
  51.         local  jac, t;
  52.  
  53.         # check the argument
  54.         if m <= 0  then Error("<m> must be positive");  fi;
  55.  
  56.         # compute the jacobi symbol similar to euclids algorithm
  57.         jac := 1;
  58.         while m <> 1  do
  59.  
  60.             # if the gcd of $n$ and $m$ is $>1$ Jacobi returns $0$
  61.             if n = 0 or (n mod 2 = 0 and m mod 2 = 0)  then
  62.                 jac := 0;  m := 1;
  63.  
  64.             # $J(n,2*m) = J(n,m) * J(n,2) = J(n,m) * (-1)^{(n^2-1)/8}$
  65.             elif m mod 2 = 0  then
  66.                 if n mod 8 = 3  or  n mod 8 = 5  then jac := -jac;  fi;
  67.                 m := m / 2;
  68.  
  69.             # $J(2*n,m) = J(n,m) * J(2,m) = J(n,m) * (-1)^{(m^2-1)/8}$
  70.             elif n mod 2 = 0  then
  71.                 if m mod 8 = 3  or  m mod 8 = 5  then jac := -jac;  fi;
  72.                 n := n / 2;
  73.  
  74.             # $J(-n,m) = J(n,m) * J(-1,m) = J(n,m) * (-1)^{(m-1)/2}$
  75.             elif n < 0  then
  76.                 if m mod 4 = 3  then jac := -jac;  fi;
  77.                 n := -n;
  78.  
  79.             # $J(n,m) = J(m,n) * (-1)^{(n-1)*(m-1)/4}$ (quadratic reciprocity)
  80.             else
  81.                 if n mod 4 = 3  and m mod 4 = 3  then jac := -jac;  fi;
  82.                 t := n;  n := m mod n;  m := t;
  83.  
  84.             fi;
  85.         od;
  86.  
  87.         return jac;
  88.     end;
  89.  
  90. You continue:
  91.  
  92.     For example, if we have, say, a=31123 and p=45667, then I am not
  93.     clear on how to proceed.
  94.  
  95. Applying the above function gives.
  96.  
  97.         J(31123/45667)      (QR)
  98.     = - J(14544/31123)      (J(2/31123) = -1)
  99.     =   J(7272/31123)       (J(2/31123) = -1)
  100.     = - J(3636/31123)       (J(2/31123) = -1)
  101.     =   J(1818/31123)       (J(2/31123) = -1)
  102.     = - J(909/31123)        (QR)
  103.     = - J(217/909)          (QR)
  104.     = - J(41/217)           (QR)
  105.     = - J(12/41)            (J(2/41) = 1)
  106.     = - J(6/41)             (J(2/41) = 1)
  107.     = - J(3/41)             (QR)
  108.     = - J(2/3)
  109.     =   J(1/3)
  110.     =   J(0/1)
  111.     =   1
  112.  
  113. You continue:
  114.  
  115.     I thought of using Euler's lemma (or whatever it is called) and
  116.     calculate a^((p-1)/2) (mod p). That, however, would seem to have
  117.     very poor worst case performance. 
  118.  
  119. This is true.  Applying Euler's lemma needs about $ln(m)$ multiplications
  120. and  modulo operations, whereas the above  function runs about as fast as
  121. one  Gcd  computation  (it  is  quite  similar  to   Euclid's  algorithm,
  122. especially  the binary variations), which in  turn  should take about the
  123. same amount of time as a few (2-3) multiplications.
  124.  
  125. Martin.
  126.  
  127. --
  128. Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,  +49 241 804551
  129. Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany
  130.