/*

  Author:  Pate Williams (c) 1997



  Addition chain exponentiation. See "Handbook of

  Applied Cryptography" by Alfred J. Menezes et al

  14.6.2 Section pages 620 - 623.

*/



#include <assert.h>

#include <stdio.h>

#include <stdlib.h>

#include "lip.h"



#define DEBUG



void long_to_binary(long a, long *e, long *t)

{

  long i;



  *t = z2logs(a);

  for (i = 0; i < *t; i++) {

    e[i] = a & 1;

    a >>= 1;

  }

}



void addition_chain(long exp, verylong zg, verylong *zge)

{

  int found;

  long I[65][2], d[32], e[32], i, j, k, s, t, u[65];

  verylong *zg1;



  long_to_binary(exp, e, &t);

  for (i = 0, j = t - 1; j >= 0; i++, j--) d[i] = e[j];

  u[0] = 1, u[1] = 2 * d[0], u[2] = u[1] + d[1];

  for (s = 3, j = 2; j < t; s += 2, j++)

    u[s] = 2 * u[s - 1], u[s + 1] = u[s] + d[j];

  zg1 = calloc(s, sizeof(verylong));

  assert(zg1 != 0);

  for (i = 1; i < s; i++) {

    found = 0;

    for (j = 0; !found && j < i; j++)

      for (k = 0; !found && k < i; k++)

        if (u[i] == u[j] + u[k])

          found = 1, I[i][0] = j, I[i][1] = k;

  }

  #ifdef DEBUG

  for (i = 0; i < s; i++)

    printf("%ld ", u[i]);

  printf("\n");

  for (i = 1; i < s; i++)

    printf("%ld %ld %ld\n", i, I[i][0], I[i][1]);

  #endif

  zcopy(zg, &zg1[0]);

  for (i = 1; i < s; i++)

    zmul(zg1[I[i][0]], zg1[I[i][1]], &zg1[i]);

  zcopy(zg1[s - 1], zge);

  free(zg1);

}



void main(void)

{

  long exp = 143l;

  verylong za = 0, zg = 0, zge = 0;



  zintoz(2l, &zg);

  addition_chain(exp, zg, &zge);

  zwriteln(zge);

  zsexp(zg, exp, &za);

  zwriteln(za);

  zfree(&za);

  zfree(&zg);

  zfree(&zge);

}