/* Author:  Pate Williams (c) 1997
            2.149 Algorithm Jacobi symbol (and Legendresymbol) computation
            See "Hanbook of Applied Cryptography" by Alfred J. Menezes et al page 73.
            Modifyed: TrueSupport 
        */
        int Jacobi(int a, int n)
        {
            int s = NULL_INT; // int.MinValue for example
            int a1, b = a, e = 0, m, n1;
            if (a == 0) return 0;
            if (a == 1) return 1;
            while ((b & 1) == 0)
            {
                b >>= 1;
                e++;
            }
            a1 = b;
            m = n % 8;
            if ((e & 1) != 0) s = 1;
            else if (m == 1 || m == 7) s = +1;
            else if (m == 3 || m == 5) s = -1;
            if (n % 4 == 3 && a1 % 4 == 3) s = -s;
            if (a1 != 1) n1 = n % a1; else n1 = 1;
            return s * Jacobi(n1, a1);
        }