Discrete exponential function

We define a ≡ b (mod c) if (a - b)/c is an integer. Define the function f(x, y, z) ≡ x^y (mod z), such that f ∈ {0, 1, ... , z - 1}. Then w = f(x, y, z) can be computed efficiently, even when x, y, z > 10³⁰⁰ by the following recursive algorithm (we assume that the integers x > 0, y > -1, and z > 0):

1. if y = 0, return 1.
2. if y is even, put u = f(x, y/2, z) and return (u*u) mod z
3. return {x*f(x, y - 1, z}} mod z

• Analysis
• The numbers computed are always less than z², and the final answer is less than z.
• The method of computing w as x^y and then reducing w modulo z is not feasible for large numbers. For example, computing f(10, 10³⁰⁰, 17) in this way, would involve computing a number w consisting of a 1 followed by 10³⁰⁰ zeros. If one atom were used to write each zero, then the observable universe would not contain enough atoms to write out w, since the observable universe contains at most 10⁸² atoms. The final answer, in any case is less than 17, and the above algorithm for the discrete exponential would compute it in fewer than 2400 steps, since 10³⁰⁰ < 16³⁰⁰ < 2¹²⁰⁰, and every two steps cut the exponent in half.

Applications

The discrete exponential function is essential to a number of important protocols in public-key cryptography, including:

• RSA (cryptosystem)
• Diffie-Hellman key exchange
• ElGamal encryption

C++ Program

Here is a C++ program for the iterative version of the discrete exponential function, which is more efficient than the recursive version.

1. Arbint f(Arbint a, Arbint x, Arbint n)
2. {
3. //finds a^x mod n.
4. Arbint e=1;
5. while(x!=0)
   1. {
   2. if(x%2==1){e=(e*a)%n; x=x -1;}
   3. a=(a*a)%n;
   4. x=x/2;
   5. }
   6. return e;
6. }

• Remarks
• Arbint is a user defined data type of an arbitrary precision integer with the overloaded operations +, -, *, /, and % defined for the class.