/*
  Author:  Pate Williams (c) 1997

  "Algorithm 1.2.1 (Right-Left Binary). Given
  g in G and n in Z, this algorithm computes
  g ^ n in G. We write 1 for the unit element
  in G." -Henri Cohen- See "A Course in Compu-
  tational Algebraic Number Theory" by Henri
  Cohen page 8. We specialize the code to the
  field Zp where p is of course prime.
*/

#include <ctype.h>
#include <stdio.h>
#include "lip.h"

void right_left_binary(verylong zg, long n,
                       verylong zp, verylong *zy)
{
  long N;
  verylong za = 0, zz = 0;

  zone(zy);
  if (n == 0) return;
  if (n < 0) {
    N = - n;
    zinvmod(zg, zp, &zz);
  }
  else {
    N = n;
    zcopy(zg, &zz);
  }
  while (N != 0) {
    if (N & 1) {
      zmulmod(zz, *zy, zp, &za);
      zcopy(za, zy);
    }
    N >>= 1;
    if (N != 0) {
      zmulmod(zz, zz, zp, &za);
      zcopy(za, &zz);
    }
  }
  zfree(&za);
  zfree(&zz);
}

long get_number(void)
{
  int c, sign = 1;
  long number;

  while ((c = getchar()) <= ' ');
  if (c == '+') {
    sign = 1;
    c = getchar();
  }
  else if (c == '-') {
    sign = - 1;
    c = getchar();
  }
  number = c - '0';
  while ((c = getchar()) != '\n')
    number = 10 * number + c - '0';
  return sign * number;
}

int main(void)
{
  char answer[256];
  long n;
  verylong zg = 0, zp = 0, zy = 0, zz = 0;

  do {
    printf("g = "); zread(&zg);
    printf("n = "); n = get_number();
    do {
      printf("p = "); zread(&zp);
    } while (!zprobprime(zp, 5l));
    right_left_binary(zg, n, zp, &zy);
    printf("y = g ^ n = "); zwriteln(zy);
    zsexpmod(zg, n, zp, &zz);
    printf("z = g ^ n = "); zwriteln(zz);
    if (zcompare(zy, zz) != 0)
      printf("error - in calculation\n");
    printf("another calculation (n or y) ? ");
    scanf("%s", answer);
  } while (tolower(answer[0]) == 'y');
  zfree(&zg);
  zfree(&zp);
  zfree(&zy);
  zfree(&zz);
  return 0;
}