Discrete exponential function: Difference between revisions

Revision as of 19:42, 30 September 2014

Revision as of 19:48, 30 September 2014

Line 18:

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

#Arbint f(Arbint a, Arbint x, Arbint n){ //discrete exponentiation

An Iterative Version of the Discrete Exponential Function

#{

Previously, we gave a recursive implementation of f(a,b,c). Here is an iterative one which will run faster:

#//finds a^x mod n.

//==============================================================

#Arbint e=1;

// I T E R A T I V E V E R S I O N O F D I S C R E T E E X P O N E N T I A L

#while(x!=0){

//==============================================================

##{

#include<iostream.h>

## if(x%2==1){e=(e*a)%n; x=x -1;}

#include"arbint.cpp"

## a=(a*a)%n;

#include"arbintmx.cpp"

## x=x/2;

Arbint f(Arbint a, Arbint x, Arbint n){ //discrete exponentiation

## }

//finds a^x mod n.

Arbint##return e=1;

#}

while(x!=0){

*Remarks

if(x%2==1){e=(e*a)%n; x=x -1;}

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

a=(a*a)%n;

x=x/2;

}

return e;

}// end f( )--discrete exponentiation