/*
  Author:  Pate Williams (c) 1997

  Exercise
  "5.1 Implement Shanks's algorithm for finding
  discrete logarithms in Z_p, where p is prime
  and alpha is a primitive element. Use your
  program to find log(106, 12375) in Z_24691
  and log(6, 248388) in Z_458009."
  -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 200.
*/

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

struct data {long j, alpha_j;};

int fcmp(const void *d1, const void *d2)
{
  struct data *data1 = (struct data *) d1;
  struct data *data2 = (struct data *) d2;

  if (data1->alpha_j < data2->alpha_j) return - 1;
  if (data1->alpha_j > data2->alpha_j) return + 1;
  return 0;
}

long Shanks(long alpha, long beta, long p)
/* returns log(alpha, beta) in Z_p where
   alpha is a generator and beta is in Z_p */
{
  int found = 0;
  long i, log, m = ceil(sqrt(p - 1));
  struct data *table1 = calloc(m, sizeof(struct data));
  struct data *table2 = calloc(m, sizeof(struct data));
  struct data *d, key;
  verylong za = 0, zb = 0, zc = 0, zp = 0;
  verylong zalpha = 0, zalpha_i = 0;
  verylong zbeta = 0, zp1 = 0;

  if (!table1 || !table2) {
    fprintf(stderr, "*error*\nin sufficient memory\n");
    fprintf(stderr, "from Shanks\n");
    exit(1);
  }
  /* create a logarithm table */
  zintoz(alpha, &zalpha);
  zintoz(beta, &zbeta);
  zintoz(p, &zp);
  zintoz(p - 1, &zp1);
  zsexpmod(zalpha, m, zp, &zalpha_i);
  for (i = 0; i < m; i++) {
    table1[i].j = i;
    zsexpmod(zalpha_i, i, zp, &za);
    table1[i].alpha_j = ztoint(za);
  }
  zinvmod(zalpha, zp, &zalpha_i);
  for (i = 0; i < m; i++) {
    table2[i].j = i;
    zsexpmod(zalpha_i, i, zp, &za);
    zmulmod(zbeta, za, zp, &zb);
    table2[i].alpha_j = ztoint(zb);
  }
  /* sort the tables by second data item */
  qsort(table1, m, sizeof(struct data), fcmp);
  qsort(table2, m, sizeof(struct data), fcmp);
  for (i = 0; !found && i < m; i++) {
    key.j = table1[i].j;
    key.alpha_j = table1[i].alpha_j;
    d = bsearch(&key, table2, m, sizeof(struct data), fcmp);
    if (d) {
      zintoz(key.j, &za);
      zintoz(m, &zb);
      zmulmod(za, zb, zp1, &zc);
      zintoz(d->j, &za);
      zaddmod(za, zc, zp1, &zb);
      log = ztoint(zb);
      zsexpmod(zalpha, log, zp, &za);
      found = zcompare(za, zbeta) == 0;
    }
  }
  if (!found) log = 0;
  zfree(&za);
  zfree(&zb);
  zfree(&zc);
  zfree(&zp);
  zfree(&zalpha);
  zfree(&zalpha_i);
  zfree(&zbeta);
  zfree(&zp1);
  return log;
}

int main(void)
{
  long alpha[2] = {106l, 6l};
  long beta[2] = {12375l, 248388l};
  long p[2] = {24691l, 458009l};
  long i, log;

  for (i = 0; i < 2; i++) {
    log = Shanks(alpha[i], beta[i], p[i]);
    if (log != 0)
      printf("log(%6ld, %6ld) = %6ld in Z_%6ld\n",
             alpha[i], beta[i], log, p[i]);
    else
      printf("log(%6ld, %6ld) in Z_%6ld does not exist\n",
             alpha[i], beta[i], p[i]);
  }
  return 0;
}