From: martin@math.rwth-aachen.de (  Martin Schoenert)
Subject: Re: Quadratic Residue Question
Organization: Rechnerbetrieb Informatik  /  RWTH Aachen
Date: 22 Jul 92 10:51:32 GMT

In his article of 17-Jul-92 pires@cs.umn.edu (Luiz S. Pires) writes:

    Please forgive me if this is a trivial question. I am not a
    mathematician, but I am trying to learn some number theory.

    Given an arbitrary number a and an odd prime p, I am trying to write a 
    subroutine that decides whether a is a quadratic residue mod p.

    I am familiar with a few of the rules available for manipulating the
    "Legendre Symbol", including the law of quadratic reciprocity. However I 
    can't think of an efficient way for handling this problem in the general
    case.

There is an extension of the Legendre symbol, called the Jacobi-Kronecker
symbol, which  does  not  require the denominator  to  be a  prime.   The
precise definition is as follows.  Suppose that $m = p_1 p_2 ...  p_k$ as
a product of primes, not necessarily different.  Then  for $n$ relatively
prime  to  $m$ the  Jacobi-Kronecker  symbol  is  defined  by  $J(n/m)  =
L'(n/p_1)  L'(n/p_2) ...  L'(n/p_k)$,  where  $L'(n/p)$  is the  Legendre
symbol  $L(n/p)$   if  $p$  is  an   odd   prime  $L'(n,2)  =  L'(2,n)  =
(-1)^{(n^2-1)/8}$.  Usually $J(n/m)$ is defined as  0, if $n$ and $m$ are
not relatively prime.

The nice thing  is that the Jacobi-Kronecker symbol satisfies almost  the
same  equalities  as  the  Legendre  symbol.  It is multiplicative in the
numerator and  the *denominator*,  and  if $n, m$ are  relative prime odd
positive integers then $J(n/m) = J(m/n) (-1)^{(n-1)*(m-1)/4}$.  So we can
use those equalities to compute the value of the Jacobi-Kronecker symbol.

Note however that the equality $L( n / m ) = L( (n mod m) / m )$ does not
carry  over  to  the Jacobi-Kronecker  symbol,  unless $m$  is odd.   For
example $1  = J(1/2)  <>  J(3/2)  = -1$.   This  makes writing  a correct
implementation  of a  function that  computes the Jacobi-Kronecker symbol
somewhat tricky.

Here is a function that computes the Jacobi-Kronecker symbol.

    Jacobi := function ( n, m )
        local  jac, t;

        # check the argument
        if m <= 0  then Error("<m> must be positive");  fi;

        # compute the jacobi symbol similar to euclids algorithm
        jac := 1;
        while m <> 1  do

            # if the gcd of $n$ and $m$ is $>1$ Jacobi returns $0$
            if n = 0 or (n mod 2 = 0 and m mod 2 = 0)  then
                jac := 0;  m := 1;

            # $J(n,2*m) = J(n,m) * J(n,2) = J(n,m) * (-1)^{(n^2-1)/8}$
            elif m mod 2 = 0  then
                if n mod 8 = 3  or  n mod 8 = 5  then jac := -jac;  fi;
                m := m / 2;

            # $J(2*n,m) = J(n,m) * J(2,m) = J(n,m) * (-1)^{(m^2-1)/8}$
            elif n mod 2 = 0  then
                if m mod 8 = 3  or  m mod 8 = 5  then jac := -jac;  fi;
                n := n / 2;

            # $J(-n,m) = J(n,m) * J(-1,m) = J(n,m) * (-1)^{(m-1)/2}$
            elif n < 0  then
                if m mod 4 = 3  then jac := -jac;  fi;
                n := -n;

            # $J(n,m) = J(m,n) * (-1)^{(n-1)*(m-1)/4}$ (quadratic reciprocity)
            else
                if n mod 4 = 3  and m mod 4 = 3  then jac := -jac;  fi;
                t := n;  n := m mod n;  m := t;

            fi;
        od;

        return jac;
    end;

You continue:

    For example, if we have, say, a=31123 and p=45667, then I am not
    clear on how to proceed.

Applying the above function gives.

        J(31123/45667)      (QR)
    = - J(14544/31123)      (J(2/31123) = -1)
    =   J(7272/31123)       (J(2/31123) = -1)
    = - J(3636/31123)       (J(2/31123) = -1)
    =   J(1818/31123)       (J(2/31123) = -1)
    = - J(909/31123)        (QR)
    = - J(217/909)          (QR)
    = - J(41/217)           (QR)
    = - J(12/41)            (J(2/41) = 1)
    = - J(6/41)             (J(2/41) = 1)
    = - J(3/41)             (QR)
    = - J(2/3)
    =   J(1/3)
    =   J(0/1)
    =   1

You continue:

    I thought of using Euler's lemma (or whatever it is called) and
    calculate a^((p-1)/2) (mod p). That, however, would seem to have
    very poor worst case performance. 

This is true.  Applying Euler's lemma needs about $ln(m)$ multiplications
and  modulo operations, whereas the above  function runs about as fast as
one  Gcd  computation  (it  is  quite  similar  to   Euclid's  algorithm,
especially  the binary variations), which in  turn  should take about the
same amount of time as a few (2-3) multiplications.

Martin.

--
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,  +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany
Newsgroups: sci.math,misc.books.technical