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
So far, so good. Now, how do you go about finding the inverse of a modulo n? There are a couple of ways. Euclid’s algorithm can also compute the inverse of a number modulo n. Sometimes this is called the extended Euclidean algorithm. Here’s the algorithm in C++:
        #define isEven(x)   ((x & 0x01) == 0)
        #define isOdd(x)    (x & 0x01)
        #define swap(x,y)   (x ^= y, y ^= x, x ^= y)

        void ExtBinEuclid(int *u, int *v, int *u1, int *u2, int *u3)
        {
            // warning: u and v will be swapped if u < v
            int k, t1, t2, t3;

            if (*u < *v) swap(*u,*v);
            for (k = 0; isEven(*u) && isEven(*v); ++k) {
        	*u >>= 1; *v >>= 1;
            }
            *u1 = 1; *u2 = 0; *u3 = *u; t1 = *v; t2 = *u-1; t3 = *v;
            do {
        	do {
        	    if (isEven(*u3)) {
        		if (isOdd(*u1) || isOdd(*u2)) {
        		    *u1 += *v; *u2 += *u;
        		}
        		*u1 >>= 1; *u2 >>= 1; *u3 >>= 1;
        	    }
        	    if (isEven(t3) || *u3 < t3) {
        		swap(*u1,t1); swap(*u2,t2); swap(*u3,t3);
        	    }
        	} while (isEven(*u3));
        	while (*u1 < t1 || *u2 < t2) {
        	    *u1 += *v; *u2 += *u;
        	}
        	*u1 -= t1; *u2 -= t2; *u3 -= t3;
            } while (t3 > 0);
            while (*u1 >= *v && *u2 >= *u) {
        	*u1 -= *v; *u2 -= *u;
            }
            *u1 <<= k; *u2 <<= k; *u3 <<= k;
        }

        main(int argc, char **argv) {
            int a, b, gcd;

            if (argc < 3) {
        	cerr << "Usage: xeuclid u v" << endl;
        	return -1;
            }
            int u = atoi(argv[1]);
            int v = atoi(argv[2]);
            if (u <= 0 || v <= 0) {
        	cerr << "Arguments must be positive!" << endl;
        	return -2;
            }
            // warning: u and v will be swapped if u < v
            ExtBinEuclid(&u, &v, &a, &b, &gcd);
            cout << a << " * " << u << " + (-"
        	<< b << ") * " << v << " = " << gcd << endl;
            if (gcd == 1)
        	cout << "the inverse of " << v << " mod " << u << " is: "
        	    << u - b << endl;
            return 0;
        }
I’m not going to prove that it works or give the theory behind it. Details can be found in [863], or in any of the number theory texts previously listed. The algorithm is iterative and can be slow for large numbers. Knuth showed that the average number of divisions performed by the algorithm is: .843*log2(n) + 1.47 Solving for Coefficients Euclid’s algorithm can be used to solve this class of problems: Given an array of m variables x1, x2,...xm, find an array of m coefficients, u1, u2...um, such that u1*x1 + ...+ um*xm = 1 Fermat’s Little Theorem If m is a prime, and a is not a multiple of m, then Fermat’s little theorem says am -1 ≡ 1 (mod m) (Pierre de Fermat, pronounced “Fair-ma, ” was a French mathematician who lived from 1601 to 1665. This theorem has nothing to do with his last theorem.) The Euler Totient Function There is another method for calculating the inverse modulo n, but it’s not always possible to use it. The reduced set of residues mod n is the subset of the complete set of residues that is relatively prime to n. For example, the reduced set of residues mod 12 is {1, 5, 7, 11}. If n is prime, then the reduced set of residues mod n is the set of all numbers from 1 to n- 1. The number 0 is never part of the reduced set of residues for any n not equal to 1. The Euler totient function, also called the Euler phi function and written as φ(n), is the number of elements in the reduced set of residues modulo n. In other words, φ(n) is the number of positive integers less than n that are relatively prime to n (for any n greater than 1). (Leonhard Euler, pronounced “Oiler, ” was a Swiss mathematician who lived from 1707 to 1783.) If n is prime, then φ(n) = n- 1. If n = pq, where p and q are prime, then φ(n) = (p- 1)(q- 1). These numbers appear in some public-key algorithms; this is why. According to Euler’s generalization of Fermat’s little theorem, if gcd(a,n) = 1, then aφ(n) mod n = 1 Now it is easy to compute a-1 mod n: x = aφ(n)-1 mod n For example, what is the inverse of 5, modulo 7? Since 7 is prime, φ(7) = 7- 1 = 6. So, the inverse of 5, modulo 7, is 56-1 mod 7 = 55 mod 7 = 3 Both methods for calculating inverses can be extended to solve for x in the general problem (if gcd(a,n) = 1): (a*x) mod n = b Using Euler’s generalization, solve x = (b*a φ(n)-1) mod n Using Euclid’s algorithm, solve x = (b*(a-1 mod n)) mod n In general, Euclid’s algorithm is faster than Euler’s generalization for calculating inverses, especially for numbers in the 500-bit range. If gcd(a,n) ≠ 1, all is not lost. In this general case, (a*x) mod n = b, can have multiple solutions or no solution. Chinese Remainder Theorem If you know the prime factorization of n, then you can use something called the Chinese remainder theorem to solve a whole system of equations. The basic version of this theorem was discovered by the first-century Chinese mathematician, Sun Tse.
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.