//This is the Algorithm 1.2.1 (Right-Left Binary) used in the 'Henry Cohen' , "A course in basic algebraic number theory" 1996.
//Used in the Henry Cohen, Prime Number Method, pp 31 - 36. For methods to solve x^2 = D(mod p), p a prime.
//Which in turn, is listed as one of the possible class methods, used in the PQa LMM.
//Should be: " The number of Multiplication steps is equal to the number of Binary
//Digits of |n| plus the number of ones in the binary representation of |n| minus 1." H.Cohen
//Have replaced [Halve N] with [shift right >>= 1]as per Alg 1.2.1.
//Warren
#include
using namespace std;
int Right_Left_Binary(long long n, long long g)
{
long long resy = 1;
long long N1b = 0;
long long Z1a = 0;
if (n == 0) { return resy; }
if (n < 0) { N1b = -n, Z1a = pow(g, -1); }
else { N1b = n, Z1a = g; }
while (N1b > 0) {
if ((N1b % 2) == 1)//if (N1b & 1)
resy = resy * Z1a;
Z1a = Z1a * Z1a;
N1b >>= 1;
}
return resy;
}
int main() {
int n;
int g;
cout << " Enter g an element of G. (So as to compute g^n in G) " << endl;
cin >> g;
cout << " Enter n an element of Z. " << endl;
cin >> n;
cout << " g^n in G == " << Right_Left_Binary(n, g) <