/*
  Author:  Pate Williams (c) 1997

  Left-to-right k-ary exponentiation. See "Handbook
  of Applied Cryptography" by Alfred J. Menezes et
  al 14.6.1 Section pages 614 - 616.
*/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "lip.h"

#define DEBUG

void radix_representation(long b, long *a, long *t, verylong za)
{
  long i = 0;
  verylong zb = 0, zq = 0, zr = 0, zx = 0;

  zintoz(b, &zb);
  zcopy(za, &zx);
  do {
    zdiv(zx, zb, &zq, &zr);
    a[i++] = ztoint(zr);
    zcopy(zq, &zx);
  } while (zscompare(zq, 0l) != 0);
  *t = i;
  zfree(&zb);
  zfree(&zq);
  zfree(&zr);
  zfree(&zx);
}

void ltr_k_ary(long b, verylong ze, verylong zg, verylong *zA)
{
  long e[8192], i, t;
  verylong za = 0, *zg1;

  radix_representation(b, e, &t, ze);
  #ifdef DEBUG
  for (i = t - 1; i >= 0; i--)
    printf("%d", e[i]);
  printf("\n");
  #endif
  zg1 = calloc(b, sizeof(verylong));
  zone(&zg1[0]);
  for (i = 1; i < b; i++)
    zmul(zg1[i - 1], zg, &zg1[i]);
  zone(zA);
  for (i = t - 1; i >= 0; i--) {
    zsexp(*zA, b, &za);
    zmul(za, zg1[e[i]], zA);
  }
  free(zg1);
  zfree(&za);
}

int main(void)
{
  long b, e = 127l, k = 1l;
  verylong zA = 0, za = 0, ze = 0, zg = 0;

  b = pow(2, k);
  zintoz(2l, &zg);
  zintoz(e, &ze);
  ltr_k_ary(b, ze, zg, &zA);
  zwriteln(zA);
  zexp(zg, ze, &za);
  zwriteln(za);
  zfree(&zA);
  zfree(&za);
  zfree(&ze);
  zfree(&zg);
  return 0;
}