moon-abe cleanup

Change-Id: Ie1259856db03f0b9e80de3e967ec6bd1f03191b3

1 files changed, 0 insertions, 692 deletions

diff --git a/moon-abe/pbc-0.5.14/arith/fieldquadratic.c b/moon-abe/pbc-0.5.14/arith/fieldquadratic.c
deleted file mode 100644
index bfb46027..00000000
--- a/moon-abe/pbc-0.5.14/arith/fieldquadratic.c
+++ /dev/null
@@ -1,692 +0,0 @@
-// Quadratic extension fields.
-//
-// The fq_ functions are for general quadratic extensions.
-// The fi_ functions are faster versions of some of these functions specialized
-// for fields extended by sqrt(-1).
-// TODO: Instead of lazily generating a quadratic nonresidue, in this case
-// we can use sqrt(base field nqr) as the nqr of the extension.
-
-#include <ctype.h>
-#include <stdarg.h>
-#include <stdio.h>
-#include <stdint.h> // for intptr_t
-#include <stdlib.h>
-#include <gmp.h>
-#include "pbc_utils.h"
-#include "pbc_field.h"
-#include "pbc_multiz.h"
-#include "pbc_fieldquadratic.h"
-#include "pbc_memory.h"
-
-// Per-element data.
-typedef struct {
-  // Elements have the form x + ya, where a is the square root of a quadratic
-  // nonresidue in the base field.
-  element_t x;
-  element_t y;
-} *eptr;
-
-// Per-field data: we use ''data'' as a field_ptr to the base field.
-
-// Return the quadratic nonresidue used to build this field.
-// Should only be called from routines used exclusively by the generic quadratic
-// extension code.
-static inline element_ptr fq_nqr(field_ptr f) {
-  return field_get_nqr((field_ptr) f->data);
-}
-
-static void fq_init(element_ptr e) {
-  eptr p = e->data = pbc_malloc(sizeof(*p));
-  field_ptr f = e->field->data;
-  element_init(p->x, f);
-  element_init(p->y, f);
-}
-
-static void fq_clear(element_ptr e) {
-  eptr p = e->data;
-  element_clear(p->x);
-  element_clear(p->y);
-  pbc_free(e->data);
-}
-
-static void fq_set_si(element_ptr e, signed long int i) {
-  eptr p = e->data;
-  element_set_si(p->x, i);
-  element_set0(p->y);
-}
-
-static void fq_set_mpz(element_ptr e, mpz_t z) {
-  eptr p = e->data;
-  element_set_mpz(p->x, z);
-  element_set0(p->y);
-}
-
-// Projection: attempts to convert Re(e) to mpz.
-static void fq_to_mpz(mpz_t z, element_ptr e) {
-  eptr p = e->data;
-  element_to_mpz(z, p->x);
-}
-
-static void fq_set0(element_ptr e) {
-  eptr p = e->data;
-  element_set0(p->x);
-  element_set0(p->y);
-}
-
-static void fq_set1(element_ptr e) {
-  eptr p = e->data;
-  element_set1(p->x);
-  element_set0(p->y);
-}
-
-static int fq_is0(element_ptr e) {
-  eptr p = e->data;
-  return element_is0(p->x) && element_is0(p->y);
-}
-
-static int fq_is1(element_ptr e) {
-  eptr p = e->data;
-  return element_is1(p->x) && element_is0(p->y);
-}
-
-static size_t fq_out_str(FILE *stream, int base, element_ptr e) {
-  size_t result = 4, status;
-  eptr p = e->data;
-  if (EOF == fputc('[', stream)) return 0;
-  result = element_out_str(stream, base, p->x);
-  if (!result) return 0;
-  if (EOF == fputs(", ", stream)) return 0;
-  status = element_out_str(stream, base, p->y);
-  if (!status) return 0;
-  if (EOF == fputc(']', stream)) return 0;
-  return result + status;
-}
-
-static int fq_snprint(char *s, size_t n, element_ptr e) {
-  eptr p = e->data;
-  size_t result = 0, left;
-  int status;
-
-  #define clip_sub() {                   \
-    result += status;                    \
-    left = result >= n ? 0 : n - result; \
-  }
-
-  status = snprintf(s, n, "[");
-  if (status < 0) return status;
-  clip_sub();
-  status = element_snprint(s + result, left, p->x);
-  if (status < 0) return status;
-  clip_sub();
-  status = snprintf(s + result, left, ", ");
-  if (status < 0) return status;
-  clip_sub();
-  status = element_snprint(s + result, left, p->y);
-  if (status < 0) return status;
-  clip_sub();
-  status = snprintf(s + result, left, "]");
-  if (status < 0) return status;
-  return result + status;
-  #undef clip_sub
-}
-
-static void fq_set_multiz(element_ptr e, multiz m) {
-  eptr p = e->data;
-  if (multiz_is_z(m)) {
-    element_set_multiz(p->x, m);
-    element_set0(p->y);
-    return;
-  }
-  element_set_multiz(p->x, multiz_at(m, 0));
-  if (2 > multiz_count(m)) element_set0(p->y);
-  else element_set_multiz(p->y, multiz_at(m, 1));
-}
-
-static int fq_set_str(element_ptr e, const char *s, int base) {
-  const char *cp = s;
-  element_set0(e);
-  while (*cp && isspace(*cp)) cp++;
-  if (*cp++ != '[') return 0;
-  eptr p = e->data;
-  cp += element_set_str(p->x, cp, base);
-  while (*cp && isspace(*cp)) cp++;
-  if (*cp++ != ',') return 0;
-  cp += element_set_str(p->y, cp, base);
-  if (*cp++ != ']') return 0;
-  return cp - s;
-}
-
-static int fq_sign(element_ptr n) {
-  int res;
-  eptr r = n->data;
-  res = element_sign(r->x);
-  if (!res) return element_sign(r->y);
-  return res;
-}
-
-static void fq_add(element_ptr n, element_ptr a, element_ptr b) {
-  eptr p = a->data;
-  eptr q = b->data;
-  eptr r = n->data;
-  element_add(r->x, p->x, q->x);
-  element_add(r->y, p->y, q->y);
-}
-
-static void fq_double(element_ptr n, element_ptr a) {
-  eptr p = a->data;
-  eptr r = n->data;
-  element_double(r->x, p->x);
-  element_double(r->y, p->y);
-}
-
-static void fq_sub(element_ptr n, element_ptr a, element_ptr b) {
-  eptr p = a->data;
-  eptr q = b->data;
-  eptr r = n->data;
-  element_sub(r->x, p->x, q->x);
-  element_sub(r->y, p->y, q->y);
-}
-
-static void fq_set(element_ptr n, element_ptr a) {
-  eptr p = a->data;
-  eptr r = n->data;
-  element_set(r->x, p->x);
-  element_set(r->y, p->y);
-}
-
-static void fq_mul(element_ptr n, element_ptr a, element_ptr b) {
-  eptr p = a->data;
-  eptr q = b->data;
-  eptr r = n->data;
-
-  element_ptr nqr = fq_nqr(n->field);
-  element_t e0, e1, e2;
-
-  element_init(e0, p->x->field);
-  element_init(e1, e0->field);
-  element_init(e2, e0->field);
-  /* naive:
-  element_mul(e0, p->x, q->x);
-  element_mul(e1, p->y, q->y);
-  element_mul(e1, e1, nqr);
-  element_add(e0, e0, e1);
-  element_mul(e1, p->x, q->y);
-  element_mul(e2, p->y, q->x);
-  element_add(e1, e1, e2);
-  element_set(r->x, e0);
-  element_set(r->y, e1);
-  */
-  // Karatsuba:
-  element_add(e0, p->x, p->y);
-  element_add(e1, q->x, q->y);
-  element_mul(e2, e0, e1);
-  element_mul(e0, p->x, q->x);
-  element_mul(e1, p->y, q->y);
-  element_mul(r->x, e1, nqr);
-  element_add(r->x, r->x, e0);
-  element_sub(e2, e2, e0);
-  element_sub(r->y, e2, e1);
-
-  element_clear(e0);
-  element_clear(e1);
-  element_clear(e2);
-}
-
-static void fq_mul_mpz(element_ptr n, element_ptr a, mpz_ptr z) {
-  eptr p = a->data;
-  eptr r = n->data;
-  element_mul_mpz(r->x, p->x, z);
-  element_mul_mpz(r->y, p->y, z);
-}
-
-static void fq_mul_si(element_ptr n, element_ptr a, signed long int z) {
-  eptr p = a->data;
-  eptr r = n->data;
-  element_mul_si(r->x, p->x, z);
-  element_mul_si(r->y, p->y, z);
-}
-
-static void fq_square(element_ptr n, element_ptr a) {
-  eptr p = a->data;
-  eptr r = n->data;
-  element_ptr nqr = fq_nqr(n->field);
-  element_t e0, e1;
-
-  element_init(e0, p->x->field);
-  element_init(e1, e0->field);
-  element_square(e0, p->x);
-  element_square(e1, p->y);
-  element_mul(e1, e1, nqr);
-  element_add(e0, e0, e1);
-  element_mul(e1, p->x, p->y);
-  //TODO: which is faster?
-  //element_add(e1, e1, e1);
-  element_double(e1, e1);
-  element_set(r->x, e0);
-  element_set(r->y, e1);
-  element_clear(e0);
-  element_clear(e1);
-}
-
-static void fq_neg(element_ptr n, element_ptr a) {
-  eptr p = a->data;
-  eptr r = n->data;
-  element_neg(r->x, p->x);
-  element_neg(r->y, p->y);
-}
-
-static void fq_random(element_ptr e) {
-  eptr p = e->data;
-  element_random(p->x);
-  element_random(p->y);
-}
-
-static int fq_cmp(element_ptr a, element_ptr b) {
-  eptr p = a->data;
-  eptr q = b->data;
-  return element_cmp(p->x, q->x) || element_cmp(p->y, q->y);
-}
-
-static void fq_invert(element_ptr n, element_ptr a) {
-  eptr p = a->data;
-  eptr r = n->data;
-  element_ptr nqr = fq_nqr(n->field);
-  element_t e0, e1;
-
-  element_init(e0, p->x->field);
-  element_init(e1, e0->field);
-  element_square(e0, p->x);
-  element_square(e1, p->y);
-  element_mul(e1, e1, nqr);
-  element_sub(e0, e0, e1);
-  element_invert(e0, e0);
-  element_mul(r->x, p->x, e0);
-  element_neg(e0, e0);
-  element_mul(r->y, p->y, e0);
-
-  element_clear(e0);
-  element_clear(e1);
-}
-
-static void fq_from_hash(element_ptr n, void *data, int len) {
-  eptr r = n->data;
-  int k = len / 2;
-  element_from_hash(r->x, data, k);
-  element_from_hash(r->y, (char *)data + k, len - k);
-}
-
-static int fq_length_in_bytes(element_ptr e) {
-  eptr p = e->data;
-  return element_length_in_bytes(p->x) + element_length_in_bytes(p->y);
-}
-
-static int fq_to_bytes(unsigned char *data, element_t e) {
-  eptr p = e->data;
-  int len;
-  len = element_to_bytes(data, p->x);
-  len += element_to_bytes(data + len, p->y);
-  return len;
-}
-
-static int fq_from_bytes(element_t e, unsigned char *data) {
-  eptr p = e->data;
-  int len;
-  len = element_from_bytes(p->x, data);
-  len += element_from_bytes(p->y, data + len);
-  return len;
-}
-
-static int fq_is_sqr(element_ptr e) {
-  //x + y sqrt(nqr) is a square iff x^2 - nqr y^2 is (in the base field)
-  eptr p = e->data;
-  element_t e0, e1;
-  element_ptr nqr = fq_nqr(e->field);
-  int result;
-  element_init(e0, p->x->field);
-  element_init(e1, e0->field);
-  element_square(e0, p->x);
-  element_square(e1, p->y);
-  element_mul(e1, e1, nqr);
-  element_sub(e0, e0, e1);
-  result = element_is_sqr(e0);
-  element_clear(e0);
-  element_clear(e1);
-  return result;
-}
-
-static void fq_sqrt(element_ptr n, element_ptr e) {
-  eptr p = e->data;
-  eptr r = n->data;
-  element_ptr nqr = fq_nqr(n->field);
-  element_t e0, e1, e2;
-
-  //if (a+b sqrt(nqr))^2 = x+y sqrt(nqr) then
-  //2a^2 = x +- sqrt(x^2 - nqr y^2)
-  //(take the sign which allows a to exist)
-  //and 2ab = y
-  element_init(e0, p->x->field);
-  element_init(e1, e0->field);
-  element_init(e2, e0->field);
-  element_square(e0, p->x);
-  element_square(e1, p->y);
-  element_mul(e1, e1, nqr);
-  element_sub(e0, e0, e1);
-  element_sqrt(e0, e0);
-  //e0 = sqrt(x^2 - nqr y^2)
-  element_add(e1, p->x, e0);
-  element_set_si(e2, 2);
-  element_invert(e2, e2);
-  element_mul(e1, e1, e2);
-  //e1 = (x + sqrt(x^2 - nqr y^2))/2
-  if (!element_is_sqr(e1)) {
-    element_sub(e1, e1, e0);
-    //e1 should be a square
-  }
-  element_sqrt(e0, e1);
-  element_add(e1, e0, e0);
-  element_invert(e1, e1);
-  element_mul(r->y, p->y, e1);
-  element_set(r->x, e0);
-  element_clear(e0);
-  element_clear(e1);
-  element_clear(e2);
-}
-
-static int fq_item_count(element_ptr e) {
-  UNUSED_VAR(e);
-  return 2;
-}
-
-static element_ptr fq_item(element_ptr e, int i) {
-  eptr p = e->data;
-  switch(i) {
-    case 0:
-      return p->x;
-    case 1:
-      return p->y;
-    default:
-      return NULL;
-  }
-}
-
-static void field_clear_fq(field_ptr f) {
-  UNUSED_VAR(f);
-  //f->order gets cleared automatically
-}
-
-static void fq_out_info(FILE *out, field_ptr f) {
-  field_ptr fbase = f->data;
-  element_fprintf(out, "extension x^2 + %B, base field: ", fq_nqr(f));
-  field_out_info(out, fbase);
-}
-
-// Specialized versions of some of the above for the case K[i].
-
-static void fi_mul(element_ptr n, element_ptr a, element_ptr b) {
-  eptr p = a->data;
-  eptr q = b->data;
-  eptr r = n->data;
-  element_t e0, e1, e2;
-
-  element_init(e0, p->x->field);
-  element_init(e1, e0->field);
-  element_init(e2, e0->field);
-  /* Naive method:
-  element_mul(e0, p->x, q->x);
-  element_mul(e1, p->y, q->y);
-  element_sub(e0, e0, e1);
-  element_mul(e1, p->x, q->y);
-  element_mul(e2, p->y, q->x);
-  element_add(e1, e1, e2);
-  element_set(r->x, e0);
-  element_set(r->y, e1);
-  */
-  // Karatsuba multiplicaiton:
-  element_add(e0, p->x, p->y);
-  element_add(e1, q->x, q->y);
-  element_mul(e2, e0, e1);
-  element_mul(e0, p->x, q->x);
-  element_sub(e2, e2, e0);
-  element_mul(e1, p->y, q->y);
-  element_sub(r->x, e0, e1);
-  element_sub(r->y, e2, e1);
-
-  element_clear(e0);
-  element_clear(e1);
-  element_clear(e2);
-}
-
-static void fi_square(element_ptr n, element_ptr a) {
-  eptr p = a->data;
-  eptr r = n->data;
-  element_t e0, e1;
-
-  element_init(e0, p->x->field);
-  element_init(e1, e0->field);
-  // Re(n) = x^2 - y^2 = (x+y)(x-y)
-  element_add(e0, p->x, p->y);
-  element_sub(e1, p->x, p->y);
-  element_mul(e0, e0, e1);
-  // Im(n) = 2xy
-  element_mul(e1, p->x, p->y);
-  element_add(e1, e1, e1);
-  element_set(r->x, e0);
-  element_set(r->y, e1);
-  element_clear(e0);
-  element_clear(e1);
-}
-
-static void fi_invert(element_ptr n, element_ptr a) {
-  eptr p = a->data;
-  eptr r = n->data;
-  element_t e0, e1;
-
-  element_init(e0, p->x->field);
-  element_init(e1, e0->field);
-  element_square(e0, p->x);
-  element_square(e1, p->y);
-  element_add(e0, e0, e1);
-  element_invert(e0, e0);
-  element_mul(r->x, p->x, e0);
-  element_neg(e0, e0);
-  element_mul(r->y, p->y, e0);
-
-  element_clear(e0);
-  element_clear(e1);
-}
-
-static int fi_is_sqr(element_ptr e) {
-  // x + yi is a square <=> x^2 + y^2 is (in the base field).
-
-  // Proof: (=>) if x+yi = (a+bi)^2, then a^2 - b^2 = x, 2ab = y,
-  // thus (a^2 + b^2)^2 = (a^2 - b^2)^2 + (2ab)^2 =  x^2 + y^2
-
-  // (<=) Suppose A^2 = x^2 + y^2. If there exist a, b satisfying:
-  //   a^2 = (+-A + x)/2, b^2 = (+-A - x)/2
-  // then (a + bi)^2 = x + yi.
-  //
-  // We show that exactly one of (A + x)/2, (-A + x)/2 is a quadratic residue
-  // (thus a, b do exist). Suppose not. Then the product (x^2 - A^2) / 4 is
-  // some quadratic residue, a contradiction since this would imply x^2 - A^2 =
-  // -y^2 is also a quadratic residue, but we know -1 is not a quadratic
-  // residue. QED.
-  eptr p = e->data;
-  element_t e0, e1;
-  int result;
-  element_init(e0, p->x->field);
-  element_init(e1, e0->field);
-  element_square(e0, p->x);
-  element_square(e1, p->y);
-  element_add(e0, e0, e1);
-  result = element_is_sqr(e0);
-  element_clear(e0);
-  element_clear(e1);
-  return result;
-}
-
-static void fi_sqrt(element_ptr n, element_ptr e) {
-  eptr p = e->data;
-  eptr r = n->data;
-  element_t e0, e1, e2;
-
-  // If (a+bi)^2 = x+yi then 2a^2 = x +- sqrt(x^2 + y^2)
-  // where we choose the sign so that a exists, and 2ab = y.
-  // Thus 2b^2 = - (x -+ sqrt(x^2 + y^2)).
-  element_init(e0, p->x->field);
-  element_init(e1, e0->field);
-  element_init(e2, e0->field);
-  element_square(e0, p->x);
-  element_square(e1, p->y);
-  element_add(e0, e0, e1);
-  element_sqrt(e0, e0);
-  // e0 = sqrt(x^2 + y^2)
-  element_add(e1, p->x, e0);
-  element_set_si(e2, 2);
-  element_invert(e2, e2);
-  element_mul(e1, e1, e2);
-  // e1 = (x + sqrt(x^2 + y^2))/2
-  if (!element_is_sqr(e1)) {
-    element_sub(e1, e1, e0);
-    // e1 should be a square.
-  }
-  element_sqrt(e0, e1);
-  element_add(e1, e0, e0);
-  element_invert(e1, e1);
-  element_mul(r->y, p->y, e1);
-  element_set(r->x, e0);
-  element_clear(e0);
-  element_clear(e1);
-  element_clear(e2);
-}
-
-static void fi_out_info(FILE *out, field_ptr f) {
-  field_ptr fbase = f->data;
-  fprintf(out, "extension x^2 + 1, base field: ");
-  field_out_info(out, fbase);
-}
-
-static void field_clear_fi(field_ptr f) {
-  UNUSED_VAR(f);
-}
-
-// All the above should be static.
-
-void element_field_to_quadratic(element_ptr r, element_ptr a) {
-  eptr p = r->data;
-  element_set(p->x, a);
-  element_set0(p->y);
-}
-
-void element_field_to_fi(element_ptr a, element_ptr b) {
-  element_field_to_quadratic(a, b);
-}
-
-static element_ptr fq_get_x(element_ptr a) {
-  return ((eptr) a->data)->x;
-}
-
-static element_ptr fq_get_y(element_ptr a) {
-  return ((eptr) a->data)->y;
-}
-
-void field_init_quadratic(field_ptr f, field_ptr fbase) {
-  field_init(f);
-
-  f->field_clear = field_clear_fq;
-  f->data = fbase;
-
-  f->init = fq_init;
-  f->clear = fq_clear;
-  f->set_si = fq_set_si;
-  f->set_mpz = fq_set_mpz;
-  f->to_mpz = fq_to_mpz;
-  f->out_str = fq_out_str;
-  f->snprint = fq_snprint;
-  f->set_multiz = fq_set_multiz;
-  f->set_str = fq_set_str;
-  f->sign = fq_sign;
-  f->add = fq_add;
-  f->sub = fq_sub;
-  f->set = fq_set;
-  f->mul = fq_mul;
-  f->mul_mpz = fq_mul_mpz;
-  f->mul_si = fq_mul_si;
-  f->square = fq_square;
-  f->doub = fq_double;
-  f->neg = fq_neg;
-  f->cmp = fq_cmp;
-  f->invert = fq_invert;
-  f->random = fq_random;
-  f->from_hash = fq_from_hash;
-  f->is1 = fq_is1;
-  f->is0 = fq_is0;
-  f->set0 = fq_set0;
-  f->set1 = fq_set1;
-  f->is_sqr = fq_is_sqr;
-  f->sqrt = fq_sqrt;
-  f->to_bytes = fq_to_bytes;
-  f->from_bytes = fq_from_bytes;
-  f->out_info = fq_out_info;
-  f->item_count = fq_item_count;
-  f->item = fq_item;
-  f->get_x = fq_get_x;
-  f->get_y = fq_get_y;
-
-  mpz_mul(f->order, fbase->order, fbase->order);
-  if (fbase->fixed_length_in_bytes < 0) {
-    f->length_in_bytes = fq_length_in_bytes;
-    f->fixed_length_in_bytes = -1;
-  } else {
-    f->fixed_length_in_bytes = 2 * fbase->fixed_length_in_bytes;
-  }
-}
-
-void field_init_fi(field_ptr f, field_ptr fbase) {
-  field_init(f);
-  f->field_clear = field_clear_fi;
-  f->data = fbase;
-  f->init = fq_init;
-  f->clear = fq_clear;
-  f->set_si = fq_set_si;
-  f->set_mpz = fq_set_mpz;
-  f->to_mpz = fq_to_mpz;
-  f->out_str = fq_out_str;
-  f->snprint = fq_snprint;
-  f->set_multiz = fq_set_multiz;
-  f->set_str = fq_set_str;
-  f->sign = fq_sign;
-  f->add = fq_add;
-  f->sub = fq_sub;
-  f->set = fq_set;
-  f->mul = fi_mul;
-  f->mul_mpz = fq_mul_mpz;
-  f->mul_si = fq_mul_si;
-  f->square = fi_square;
-  f->doub = fq_double;
-  f->neg = fq_neg;
-  f->cmp = fq_cmp;
-  f->invert = fi_invert;
-  f->random = fq_random;
-  f->from_hash = fq_from_hash;
-  f->is1 = fq_is1;
-  f->is0 = fq_is0;
-  f->set0 = fq_set0;
-  f->set1 = fq_set1;
-  f->is_sqr = fi_is_sqr;
-  f->sqrt = fi_sqrt;
-  f->to_bytes = fq_to_bytes;
-  f->from_bytes = fq_from_bytes;
-  f->out_info = fi_out_info;
-  f->item_count = fq_item_count;
-  f->item = fq_item;
-  f->get_x = fq_get_x;
-  f->get_y = fq_get_y;
-
-  mpz_mul(f->order, fbase->order, fbase->order);
-  if (fbase->fixed_length_in_bytes < 0) {
-    f->length_in_bytes = fq_length_in_bytes;
-    f->fixed_length_in_bytes = -1;
-  } else {
-    f->fixed_length_in_bytes = 2 * fbase->fixed_length_in_bytes;
-  }
-}