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
In general, if the prime factorization of n is p1*p2*...*pt, then the system of equations (x mod pi) = ai, where i = 1, 2,..., t has a unique solution, x, where x is less than n. (Note that some primes can appear more than once. For example, p1 might be equal to p2 .) In other words, a number (less than the product of some primes) is uniquely identified by its residues mod those primes. For example, use 3 and 5 as primes, and 14 as the number. 14 mod 3 = 2, and 14 mod 5 = 4. There is only one number less than 3*5 = 15 which has those residues: 14. The two residues uniquely determine the number. So, for an arbitrary a < p and b < q (where p and q are prime), there exists a unique x, where x is less than pq, such that x ≡ a (mod p), and x ≡ b (mod q) To find this x, first use Euclid’s algorithm to find u, such that u*q ≡ 1 (mod p) Then compute: x = (((a - b)*u) mod p)*q + b Here is the Chinese remainder theorem in C:
        /* r is the number of elements in arrays m and u;
        m is the array of (pairwise relatively prime) moduli
        u is the array of coefficients
        return value is n such than n == u[k]%m[k] (k=0..r-1) and
        	n < m[0]*m[1]*...*m[r-1]
        */

        /* totient() is left as an exercise to the reader. */
        int chinese_remainder (size_t r, int *m, int *u)
        {
            size_t i;
            int modulus;
            int n;
            modulus = 1;
            for (i=0; i<r; ++i)
        	modulus *= m[i];

            n = 0;
            for (i=0; i<r; ++i) {
        	n += u[i] * modexp(modulus / m[i], totient(m[i]),
            m[i]);
        	n %= modulus;
            }

            return n;
        }
The converse of the Chinese remainder theorem can also be used to find the solution to the problem: if p and q are primes, and p is less than q, then there exists a unique x less than pq, such that a ≡ x (mod p), and b ≡ x (mod q) If a ≥ b mod p, then x = (((a - (b mod p))*u) mod p)*q + b If a < b mod p, then x = (((a + p - (b mod p))*u) mod p)*q + b Quadratic Residues If p is prime, and a is greater than 0 and less than p, then a is a quadratic residue mod p if x2 ≡ a (mod p), for some x Not all values of a satisfy this property. For a to be a quadratic residue modulo n, it must be a quadratic residue modulo all the prime factors of n. For example, if p = 7, the quadratic residues are 1, 2, and 4: 12 = 1 ≡ 1 (mod 7) 22 = 4 ≡ 4 (mod 7) 32 = 9 ≡ 2 (mod 7) 42 = 16 ≡ 2 (mod 7) 52 = 25 ≡ 4 (mod 7) 62 = 36 ≡ 1 (mod 7) Note that each quadratic residue appears twice on this list. There are no values of x which satisfy any of these equations: x2 ≡ 3 (mod 7) x2 ≡ 5 (mod 7) x2 ≡ 6 (mod 7) The quadratic nonresidues modulo 7, the numbers that are not quadratic residues, are 3, 5, and 6. Although I will not do so here, it is easy to prove that, when p is odd, there are exactly (p- 1)/2 quadratic residues mod p and the same number of quadratic nonresidues mod p. Also, if a is a quadratic residue mod p, then a has exactly two square roots, one of them between 0 and (p- 1)/2, and the other between (p- 1)/2 and (p- 1). One of these square roots is also a quadratic residue mod p; this is called the principal square root. If n is the product of two primes, p and q, there are exactly (p- 1)(q- 1)/4 quadratic residues mod n. A quadratic residue mod n is a perfect square modulo n. This is because to be a square mod n, the residue must be a square mod p and a square mod q. For example, there are 11 quadratic residues mod 35: 1, 4, 9, 11, 14, 15, 16, 21, 25, 29, and 30. Each quadratic residue has exactly four square roots. Legendre Symbol The Legendre symbol, written L(a,p), is defined when a is any integer and p is a prime greater than 2. It is equal to 0, 1, or -1. L(a,p) = 0 if a is divisible by p. L(a,p) = 1 if a is a quadratic residue mod p. L(a,p) = - 1 is a is a quadratic nonresidue mod p. One way to calculate L(a,p) is: L(a,p) = a(p- 1)/2 mod p Or you can use the following algorithm: 1. If a = 1, then L(a,p) = 1 2. If a is even, then L(a,p) = L(a /2,p)*(- 1)(p2- 1)/8 3. If a is odd (and ≠ 1), then L(a,p) = L(p mod a,a)*(- 1)(a- 1)*(p- 1)/4 Note that this is also an efficient way to determine whether a is a quadratic residue mod p (when p is prime).
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.