NTTL Function - Jacobi

Description: Compute the Jacobi symbol of a number.

Signature: template< class TNUM, class TMOD >
short
Jacobi( const TNUM &N, const TMOD &Modulus )

Parameters

Name	Type	Description
N	TNUM	The number for which to evaluate the Jacobi symbol.
Modulus	TMOD	The modulus.

Returns: ( short ) The value of the Jacobi symbol of N mod Modulus.

Example

#include <nttl/jacobi.h>
...
long x = 12381273;
short m = 13;
if( Jacobi( x, m ) == 1 )
    cout << "x is QR mod m" << endl;

Algorithm

This is basically the ordinary algorithm. It makes use of the following identities (from [Flath]):

(-1/m) = (-1)^(m-1)/2 = /  1 if m==1 mod 4
                        \ -1 if m==3 mod 4

(2/m)  = (-1)^(m^2-1)/8 = /  1 if m==+-1 mod 8
                          \ -1 if m==+-3 mod 8

(n/m)  = (-1)^(m-1)(n-1)/2

       = /  (m/n) if m==1 or n==1 mod 4
         \ -(m/n) if m==n==3 mod 4

Notes: A faster algorithm has been implemented, and should be installed.

References: [Knuth2], exercise 4.5.4.23.
[Shallit]
[Flath]