Click Here! |

Brief Full Advanced Search Search Tips
|  |  | To access the contents, click the chapter and section titles. Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth) (Publisher: John Wiley & Sons, Inc.) Author(s): Bruce Schneier ISBN: 0471128457 Publication Date: 01/01/96 Search this book:
Previous | Table of Contents | Next
Jacobi Symbol The Jacobi symbol, written J(a,n), is a generalization of the Legendre symbol to composite moduli; it is defined for any integer a and any odd integer n. The function shows up in primality testing. The Jacobi symbol is a function on the set of reduced residues of the divisors of n and can be calculated by several formulas [1412]. This is one method: Definition 1: J(a,n) is only defined if n is odd. Definition 2: J(0,n) = 0. Definition 3: If n is prime, then the Jacobi symbol J(a,n) = 0 if n divides a. Definition 4: If n is prime, then the Jacobi symbol J(a,n) = 1 if a is a quadratic residue modulo n. Definition 5: If n is prime, then the Jacobi symbol J(a,n) = - 1 if a is a quadratic nonresidue modulo n. Definition 6: If n is composite, then the Jacobi symbol J(a,n) = J(a,p1) *...* J(a,pm), where p1...pm is the prime factorization of n. The following algorithm computes the Jacobi symbol recursively: Rule 1: J(1,n) = 1 Rule 2: J(a*b,n) = J(a,n)*J(b,n) Rule 3: J(2,n) = 1 if (n2 - 1)/8 is even, and - 1 otherwise Rule 4: J(a,n) = J((a mod n),n) Rule 5: J(a,b1*b2) = J(a,b1)*J(a,b2) Rule 6: If the greatest common divisor of a and b = 1, and a and b are odd: Rule 6a: J(a,b) = J(b,a) if (a - 1)(b - 1)/4 is even Rule 6b: J(a,b) = - J(b,a) if (a-1)(b-1)/4 is odd Here is the algorithm in C:
        /* This algorithm computes the Jacobi symbol recursively */
        int jacobi(int a, int b)
        {
        int g;
            assert(odd(b));
            if (a >= b) a %= b;       /* by Rule 4 */
            if (a == 0) return 0;       /* by Definition 2 */
            if (a == 1) return 1;       /* by Rule 1 */
            if (a < 0)
        	if (((b-1)/2 % 2 == 0)
        	    return jacobi(-a,b);
        	else
        	    return -jacobi(-a,b);
            if (a % 2 == 0) /* a is even */
        	if (((b*b - 1)/8) % 2 == 0)
        	    return +jacobi(a/2, b)
        	else
        	    return -jacobi(a/2, b) /* by Rule 3 and Rule 2 */
            g = gcd(a,b);
            assert(odd(a)); /* this is guaranteed by the (a % 2 == 0)
        test */
            if (g == a) /* a exactly divides b */
        	return 0; /* by Rules 5 and 4, and Definition 2 */
            else if (g != 1)
        	return jacobi(g,b) * jacobi(a/g, b); /* by Rule 2 */
            else if (((a-1)*(b-1)/4) % 2 == 0)
        	return +jacobi(b,a);    /* by Rule 6a */
            else
        	return -jacobi(b,a);    /* by Rule 6b */
        }
If n is known to be prime beforehand, simply compute a((n-1)/2) mod n instead of running the previous algorithm; in this case J(a,n) is equivalent to the Legendre symbol. The Jacobi symbol cannot be used to determine whether a is a quadratic residue mod n (unless n is prime, of course). Note that, if J(a,n) = 1 and n is composite, it is not necessarily true that a is a quadratic residue modulo n. For example: J(7, 143) = J(7, 11)*J(7, 13) = (- 1)(- 1) = 1 However, there is no integer x such that x2 ≡ 7 (mod 143). Blum Integers If p and q are two primes, and both are congruent to 3 modulo 4, then n = pq is sometimes called a Blum integer. If n is a Blum integer, each quadratic residue has exactly four square roots, one of which is also a square; this is the principal square root. For example, the principal square root of 139 mod 437 is 24. The other three square roots are 185, 252, and 413. Generators If p is a prime, and g is less than p, then g is a generator mod p if for each b from 1 to p - 1, there exists some a where ga ≡ b (mod p). Another way of saying this is that g is primitive with respect to p. For example, if p = 11, 2 is a generator mod 11: 210 = 1024 ≡ 1 (mod 11) 21 = 2 ≡ 2 (mod 11) 28 = 256 ≡ 3 (mod 11) 22 = 4 ≡ 4 (mod 11) 24 = 16 ≡ 5 (mod 11) 29 = 512 ≡ 6 (mod 11) 27 = 128 ≡ 7 (mod 11) 23 = 8 ≡ 8 (mod 11) 26 = 64 ≡ 9 (mod 11) 25 = 32 ≡ 10 (mod 11) Every number from 1 to 10 can be expressed as 2a (mod p). For p = 11, the generators are 2, 6, 7, and 8. The other numbers are not generators. For example, 3 is not a generator because there is no solution to 3a = 2 (mod 11) In general, testing whether a given number is a generator is not an easy problem. It is easy, however, if you know the factorization of p - 1. Let q1, q2,..., qn be the distinct prime factors of p - 1. To test whether a number g is a generator mod p, calculate g(p- 1)/q mod p for all values of q = q1, q2,..., qn. If that number equals 1 for some value of q, then g is not a generator. If that value does not equal 1 for any values of q, then g is a generator. For example, let p = 11. The prime factors of p - 1 = 10 are 2 and 5. To test whether 2 is a generator: 2(11- 1)/5 (mod 11) = 4 2(11- 1)/2 (mod 11) = 10
Previous | Table of Contents | Next
[an error occurred while processing this directive]

| Products | Contact Us | About Us | Privacy | Ad Info | Home Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc. All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.