fieldquadratic.c

这是一个C的源代码

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
#include "pbc_field.h"
#include "pbc_fieldquadratic.h"
#include "pbc_utils.h"
#include "pbc_memory.h"

static inline element_ptr fq_nqr(field_ptr f)
{
    return ((field_ptr) f->data)->nqr;
}

static void fq_init(element_ptr e)
{
    fq_data_ptr p = e->data = pbc_malloc(sizeof(fq_data_t));
    field_ptr f = e->field->data;
    element_init(p->x, f);
    element_init(p->y, f);
}

static void fq_clear(element_ptr e)
{
    fq_data_ptr 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)
{
    fq_data_ptr p = e->data;
    element_set_si(p->x, i);
    element_set0(p->y);
}

static void fq_set_mpz(element_ptr e, mpz_t z)
{
    fq_data_ptr 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)
{
    fq_data_ptr p = e->data;
    element_to_mpz(z, p->x);
}

static void fq_set0(element_ptr e)
{
    fq_data_ptr p = e->data;
    element_set0(p->x);
    element_set0(p->y);
}

static void fq_set1(element_ptr e)
{
    fq_data_ptr p = e->data;
    element_set1(p->x);
    element_set0(p->y);
}

static int fq_is0(element_ptr e)
{
    fq_data_ptr p = e->data;
    return element_is0(p->x) && element_is0(p->y);
}

static int fq_is1(element_ptr e)
{
    fq_data_ptr 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;
    fq_data_ptr 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)
{
    fq_data_ptr p = e->data;
    size_t result = 0, left;
    int status;

    void clip_sub(void)
    {
	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;
}

static int fq_set_str(element_ptr e, char *s, int base)
{
    char *cp = s;
    element_set0(e);
    while (*cp && isspace(*cp)) cp++;
    if (*cp++ != '[') return 0;
    fq_data_ptr 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;
    fq_data_ptr 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)
{
    fq_data_ptr p = a->data;
    fq_data_ptr q = b->data;
    fq_data_ptr 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)
{
    fq_data_ptr p = a->data;
    fq_data_ptr 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)
{
    fq_data_ptr p = a->data;
    fq_data_ptr q = b->data;
    fq_data_ptr 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)
{
    fq_data_ptr p = a->data;
    fq_data_ptr 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)
{
    fq_data_ptr p = a->data;
    fq_data_ptr q = b->data;
    fq_data_ptr 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)
{
    fq_data_ptr p = a->data;
    fq_data_ptr 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)
{
    fq_data_ptr p = a->data;
    fq_data_ptr 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)
{
    fq_data_ptr p = a->data;
    fq_data_ptr 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)
{
    fq_data_ptr p = a->data;
    fq_data_ptr r = n->data;
    element_neg(r->x, p->x);
    element_neg(r->y, p->y);
}

static void fq_random(element_ptr e)
{
    fq_data_ptr p = e->data;
    element_random(p->x);
    element_random(p->y);
}

static int fq_cmp(element_ptr a, element_ptr b)
{
    fq_data_ptr p = a->data;
    fq_data_ptr 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)
{
    fq_data_ptr p = a->data;
    fq_data_ptr 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)
{
    fq_data_ptr 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)
{
    fq_data_ptr 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)
{
    fq_data_ptr 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)
{
    fq_data_ptr 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)