aboutsummaryrefslogtreecommitdiffstats
path: root/moon-abe/pbc-0.5.14/guru
diff options
context:
space:
mode:
Diffstat (limited to 'moon-abe/pbc-0.5.14/guru')
-rw-r--r--moon-abe/pbc-0.5.14/guru/19.c373
-rw-r--r--moon-abe/pbc-0.5.14/guru/59.c783
-rw-r--r--moon-abe/pbc-0.5.14/guru/checkfp.c334
-rw-r--r--moon-abe/pbc-0.5.14/guru/eta_T_3_test.c130
-rw-r--r--moon-abe/pbc-0.5.14/guru/exp_test.c88
-rw-r--r--moon-abe/pbc-0.5.14/guru/fp_test.c95
-rw-r--r--moon-abe/pbc-0.5.14/guru/indexcalculus.c869
-rw-r--r--moon-abe/pbc-0.5.14/guru/param_parse_test.c26
-rw-r--r--moon-abe/pbc-0.5.14/guru/poly_test.c136
-rw-r--r--moon-abe/pbc-0.5.14/guru/prodpairing_test.c44
-rw-r--r--moon-abe/pbc-0.5.14/guru/quadratic_test.c62
-rw-r--r--moon-abe/pbc-0.5.14/guru/sing.c263
-rw-r--r--moon-abe/pbc-0.5.14/guru/ternary_extension_field_test.c240
-rw-r--r--moon-abe/pbc-0.5.14/guru/testindexcalculus.c29
-rw-r--r--moon-abe/pbc-0.5.14/guru/timefp.c98
15 files changed, 3570 insertions, 0 deletions
diff --git a/moon-abe/pbc-0.5.14/guru/19.c b/moon-abe/pbc-0.5.14/guru/19.c
new file mode 100644
index 00000000..5e225565
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/19.c
@@ -0,0 +1,373 @@
+/*
+ * Toy example of a field where the Tate pairing can be used
+ * but the Weil pairing cannot.
+ *
+ * Consider the curve E: y^2 = x^3 + x + 6 over F_19:
+ * E(F_19) is a cyclic group of order 18.
+ * Thus E[3] is not contained in F_19
+ * (it turns out E[3] is contained in F_19^3).
+ *
+ * Hence the Weil pairing cannot be defined over F_19
+ * However, F_19 contains the cube roots of unity
+ * so we can compute the Tate pairing
+ */
+
+/*
+ * P = (12,13) generates a group of order 3:
+ * <(12,13)> = {(12,13), (12,6), O}
+ * e(P,P) = 7, so we have the isomorphism
+ * <(12,13)> = <7> (in F_19^*)
+ *
+ * Similarly P = (4, 6) generates a group of order 9, and we find
+ * <(4,6)> = <4>
+ *
+ * P = (0, 5) generates all of E(F_19)
+ * Miller's algorithm will not allow us to calculate e(P, P) without
+ * first extending F_19.
+ * Instead of extending, we could manipulate rational functions since
+ * 19 is small enough that an explicit expression of f_P can be found.
+ */
+
+#include "pbc.h"
+#include "pbc_fp.h"
+#include "pbc_fieldquadratic.h"
+
+static void miller(element_t res, element_t P, element_ptr QR, element_ptr R, int n) {
+ // Collate divisions.
+ int m;
+ element_t v, vd;
+ element_t Z;
+ element_t a, b, c;
+ const element_ptr cca = curve_a_coeff(P);
+ const element_ptr Px = curve_x_coord(P);
+ const element_ptr Py = curve_y_coord(P);
+ element_t e0, e1;
+ mpz_t q;
+ element_ptr Zx, Zy;
+ const element_ptr numx = curve_x_coord(QR);
+ const element_ptr numy = curve_y_coord(QR);
+ const element_ptr denomx = curve_x_coord(R);
+ const element_ptr denomy = curve_y_coord(R);
+
+ void do_vertical(element_t e, element_t edenom)
+ {
+ element_sub(e0, numx, Zx);
+ element_mul(e, e, e0);
+
+ element_sub(e0, denomx, Zx);
+ element_mul(edenom, edenom, e0);
+ }
+
+ void do_tangent(element_t e, element_t edenom)
+ {
+ //a = -slope_tangent(A.x, A.y);
+ //b = 1;
+ //c = -(A.y + a * A.x);
+ //but we multiply by 2*A.y to avoid division
+
+ //a = -Ax * (Ax + Ax + Ax + twicea_2) - a_4;
+ //Common curves: a2 = 0 (and cc->a is a_4), so
+ //a = -(3 Ax^2 + cc->a)
+ //b = 2 * Ay
+ //c = -(2 Ay^2 + a Ax);
+
+ if (element_is0(Zy)) {
+ do_vertical(e, edenom);
+ return;
+ }
+ element_square(a, Zx);
+ element_mul_si(a, a, 3);
+ element_add(a, a, cca);
+ element_neg(a, a);
+
+ element_add(b, Zy, Zy);
+
+ element_mul(e0, b, Zy);
+ element_mul(c, a, Zx);
+ element_add(c, c, e0);
+ element_neg(c, c);
+
+ element_mul(e0, a, numx);
+ element_mul(e1, b, numy);
+ element_add(e0, e0, e1);
+ element_add(e0, e0, c);
+ element_mul(e, e, e0);
+
+ element_mul(e0, a, denomx);
+ element_mul(e1, b, denomy);
+ element_add(e0, e0, e1);
+ element_add(e0, e0, c);
+ element_mul(edenom, edenom, e0);
+ }
+
+ void do_line(element_ptr e, element_ptr edenom)
+ {
+ if (!element_cmp(Zx, Px)) {
+ if (!element_cmp(Zy, Py)) {
+ do_tangent(e, edenom);
+ } else {
+ do_vertical(e, edenom);
+ }
+ return;
+ }
+
+ element_sub(b, Px, Zx);
+ element_sub(a, Zy, Py);
+ element_mul(c, Zx, Py);
+ element_mul(e0, Zy, Px);
+ element_sub(c, c, e0);
+
+ element_mul(e0, a, numx);
+ element_mul(e1, b, numy);
+ element_add(e0, e0, e1);
+ element_add(e0, e0, c);
+ element_mul(e, e, e0);
+
+ element_mul(e0, a, denomx);
+ element_mul(e1, b, denomy);
+ element_add(e0, e0, e1);
+ element_add(e0, e0, c);
+ element_mul(edenom, edenom, e0);
+ }
+
+ element_init(a, res->field);
+ element_init(b, res->field);
+ element_init(c, res->field);
+ element_init(e0, res->field);
+ element_init(e1, res->field);
+
+ element_init(v, res->field);
+ element_init(vd, res->field);
+ element_init(Z, P->field);
+
+ element_set(Z, P);
+ Zx = curve_x_coord(Z);
+ Zy = curve_y_coord(Z);
+
+ element_set1(v);
+ element_set1(vd);
+
+ mpz_init(q);
+ mpz_set_ui(q, n);
+ m = mpz_sizeinbase(q, 2) - 2;
+
+ while(m >= 0) {
+ element_square(v, v);
+ element_square(vd, vd);
+ do_tangent(v, vd);
+ element_double(Z, Z);
+ do_vertical(vd, v);
+
+ if (mpz_tstbit(q, m)) {
+ do_line(v, vd);
+ element_add(Z, Z, P);
+ if (m) {
+ do_vertical(vd, v);
+ }
+ }
+ m--;
+ }
+
+ mpz_clear(q);
+
+ element_invert(vd, vd);
+ element_mul(res, v, vd);
+
+ element_clear(v);
+ element_clear(vd);
+ element_clear(Z);
+ element_clear(a);
+ element_clear(b);
+ element_clear(c);
+ element_clear(e0);
+ element_clear(e1);
+}
+
+static void tate_3(element_ptr out, element_ptr P, element_ptr Q, element_ptr R) {
+ mpz_t six;
+
+ mpz_init(six);
+ mpz_set_ui(six, 6);
+ element_t QR;
+ element_t e0;
+
+ element_init(QR, P->field);
+ element_init(e0, out->field);
+
+ element_add(QR, Q, R);
+
+ //for subgroup size 3, -2P = P, hence
+ //the tangent line at P has divisor 3(P) - 3(O)
+
+ miller(out, P, QR, R, 3);
+
+ element_pow_mpz(out, out, six);
+ element_clear(QR);
+ element_clear(e0);
+ mpz_clear(six);
+}
+
+static void tate_9(element_ptr out, element_ptr P, element_ptr Q, element_ptr R) {
+ element_t QR;
+ element_init(QR, P->field);
+
+ element_add(QR, Q, R);
+
+ miller(out, P, QR, R, 9);
+
+ element_square(out, out);
+
+ element_clear(QR);
+}
+
+static void tate_18(element_ptr out, element_ptr P, element_ptr Q, element_ptr R, element_ptr S) {
+ mpz_t pow;
+ element_t PR;
+ element_t QS;
+ element_init(PR, P->field);
+ element_init(QS, P->field);
+ element_t outd;
+
+ element_init(outd, out->field);
+
+ mpz_init(pow);
+ mpz_set_ui(pow, (19*19-1)/18);
+
+ element_add(PR, P, R);
+ element_add(QS, Q, S);
+
+ if (element_is0(QS)) {
+ element_t S2;
+ element_init(S2, P->field);
+ element_double(S2, S);
+ miller(out, PR, S, S2, 18);
+ miller(outd, R, S, S2, 18);
+ element_clear(S2);
+ } else {
+ miller(out, PR, QS, S, 18);
+ miller(outd, R, QS, S, 18);
+ }
+
+ element_clear(PR);
+ element_clear(QS);
+
+ element_invert(outd, outd);
+ element_mul(out, out, outd);
+ element_pow_mpz(out, out, pow);
+
+ element_clear(outd);
+ mpz_clear(pow);
+}
+
+int main(void) {
+ field_t c;
+ field_t Z19;
+ element_t P, Q, R;
+ mpz_t q, z;
+ element_t a, b;
+ int i;
+
+ field_t Z19_2;
+ field_t c2;
+ element_t P2, Q2, R2;
+ element_t a2;
+
+ mpz_init(q);
+ mpz_init(z);
+
+ mpz_set_ui(q, 19);
+
+ field_init_fp(Z19, q);
+ element_init(a, Z19);
+ element_init(b, Z19);
+
+ element_set_si(a, 1);
+ element_set_si(b, 6);
+
+ mpz_set_ui(q, 18);
+ field_init_curve_ab(c, a, b, q, NULL);
+ element_init(P, c);
+ element_init(Q, c);
+ element_init(R, c);
+
+ printf("Y^2 = X^3 + X + 6 over F_19\n");
+ //(0,+/-5) is a generator
+ element_set0(a);
+ curve_from_x(R, a);
+
+ for (i=1; i<19; i++) {
+ mpz_set_si(z, i);
+ element_mul_mpz(Q, R, z);
+ element_printf("%dR = %B\n", i, Q);
+ }
+
+ mpz_set_ui(z, 6);
+ element_mul_mpz(P, R, z);
+ //P has order 3
+ element_printf("P = %B\n", P);
+
+ for (i=1; i<=3; i++) {
+ mpz_set_si(z, i);
+ element_mul_mpz(Q, R, z);
+ tate_3(a, P, Q, R);
+ element_printf("e_3(P,%dR) = %B\n", i, a);
+ }
+
+ element_double(P, R);
+ //P has order 9
+ element_printf("P = %B\n", P);
+ for (i=1; i<=9; i++) {
+ mpz_set_si(z, i);
+ //we're supposed to use multiples of R
+ //but 2R works just as well and it allows us
+ //to use R as the offset every time
+ element_mul_mpz(Q, P, z);
+ tate_9(a, P, Q, R);
+ element_printf("e_9(P,%dP) = %B\n", i, a);
+ }
+
+ //to do the pairing on all of E(F_19) we need to move to F_19^2
+ //or compute the rational function explicitly
+ printf("moving to F_19^2\n");
+ field_init_fi(Z19_2, Z19);
+
+ //don't need to tell it the real order
+ field_init_curve_ab_map(c2, c, element_field_to_fi, Z19_2, q, NULL);
+ element_init(P2, c2);
+ element_init(Q2, c2);
+ element_init(R2, c2);
+
+ element_init(a2, Z19_2);
+ element_set0(a2);
+ curve_from_x(P2, a2);
+
+ element_random(R2);
+
+ element_printf("P = %B\n", P2);
+
+ for (i=1; i<=18; i++) {
+ mpz_set_si(z, i);
+ element_mul_mpz(Q2, P2, z);
+ tate_18(a2, P2, Q2, R2, P2);
+ element_printf("e_18(P,%dP) = %B\n", i, a2);
+ }
+
+ element_clear(P2);
+ element_clear(Q2);
+ element_clear(R2);
+ element_clear(a2);
+ field_clear(c2);
+ field_clear(Z19_2);
+
+ field_clear(c);
+ element_clear(a);
+ element_clear(b);
+ element_clear(P);
+ element_clear(Q);
+ element_clear(R);
+ field_clear(Z19);
+
+ mpz_clear(q);
+ mpz_clear(z);
+ return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/59.c b/moon-abe/pbc-0.5.14/guru/59.c
new file mode 100644
index 00000000..d543a757
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/59.c
@@ -0,0 +1,783 @@
+// Step-by-step Weil and Tate pairings.
+// For my thesis.
+#include <string.h>
+#include "pbc.h"
+#include "pbc_fp.h"
+#include "pbc_fieldquadratic.h"
+
+static field_t Fq, Fq2, E, E2;
+static mpz_t order;
+
+static void do_vert(element_ptr z, element_ptr V, element_ptr Q)
+{
+ element_ptr Vx = curve_x_coord(V);
+ element_ptr Qx = curve_x_coord(Q);
+ element_ptr Qy = curve_y_coord(Q);
+
+ element_t a, b, c;
+ element_init_same_as(a, Vx);
+ element_init_same_as(b, Vx);
+ element_init_same_as(c, Vx);
+
+ //a = 1
+ //b = 0;
+ //c = -Vx
+ element_set1(a);
+ element_set0(b);
+ element_neg(c, Vx);
+
+ element_printf("vert at %B: %B %B %B\n", Vx, a, b, c);
+ element_mul(a, a, Qx);
+ element_mul(b, b, Qy);
+ element_add(c, c, a);
+ element_add(z, c, b);
+ element_printf("vert eval = %B\n", z);
+ element_clear(a);
+ element_clear(b);
+ element_clear(c);
+}
+
+static void do_tangent(element_ptr z, element_ptr V, element_ptr Q)
+{
+ element_ptr Vx = curve_x_coord(V);
+ element_ptr Vy = curve_y_coord(V);
+ element_ptr Qx = curve_x_coord(Q);
+ element_ptr Qy = curve_y_coord(Q);
+
+ element_t a, b, c;
+ element_init_same_as(a, Vx);
+ element_init_same_as(b, Vx);
+ element_init_same_as(c, Vx);
+
+ //a = -slope_tangent(V.x, V.y);
+ //b = 1;
+ //c = -(V.y + aV.x);
+ /*
+ //we could multiply by -2*V.y to avoid division so:
+ //a = -(3 Vx^2 + cc->a)
+ //b = 2 * Vy
+ //c = -(2 Vy^2 + a Vx);
+ //
+ //actually no, since fasterweil won't work if we do this
+ */
+ element_square(a, Vx);
+ //element_mul_si(a, a, 3);
+ element_add(b, a, a);
+ element_add(a, b, a);
+ element_set1(b);
+ element_add(a, a, b);
+ element_neg(a, a);
+ element_double(b, Vy);
+ element_div(a, a, b);
+ element_set1(b);
+ element_mul(c, a, Vx);
+ element_add(c, c, Vy);
+ element_neg(c, c);
+
+ element_printf("tan at %B: %B %B %B\n", V, a, b, c);
+
+ element_mul(a, a, Qx);
+ element_mul(b, b, Qy);
+ element_add(c, c, a);
+ element_add(z, c, b);
+ element_printf("tan eval = %B\n", z);
+ element_clear(a);
+ element_clear(b);
+ element_clear(c);
+}
+
+static void do_line(element_ptr z, element_ptr V, element_ptr P, element_ptr Q)
+{
+ element_ptr Vx = curve_x_coord(V);
+ element_ptr Vy = curve_y_coord(V);
+ element_ptr Px = curve_x_coord(P);
+ element_ptr Py = curve_y_coord(P);
+ element_ptr Qx = curve_x_coord(Q);
+ element_ptr Qy = curve_y_coord(Q);
+
+ element_t a, b, c, e0;
+ element_init_same_as(a, Vx);
+ element_init_same_as(b, Vx);
+ element_init_same_as(c, Vx);
+ element_init_same_as(e0, Vx);
+
+ //a = -(B.y - A.y) / (B.x - A.x);
+ //b = 1;
+ //c = -(A.y + a * A.x);
+
+ element_sub(a, Py, Vy);
+ element_sub(b, Vx, Px);
+ element_div(a, a, b);
+ element_set1(b);
+ element_mul(c, a, Vx);
+ element_add(c, c, Vy);
+ element_neg(c, c);
+
+ /*
+ //but we could multiply by B.x - A.x to avoid division, so
+ //a = -(By - Ay)
+ //b = Bx - Ax
+ //c = -(Ay b + a Ax);
+ element_sub(a, Vy, Py);
+ element_sub(b, Px, Vx);
+ element_mul(c, Vx, Py);
+ element_mul(e0, Vy, Px);
+ element_sub(c, c, e0);
+ //
+ //actually no, since fasterweil won't work if we do this
+ */
+
+ element_printf("line at %B: %B %B %B\n", V, a, b, c);
+ element_mul(a, a, Qx);
+ element_mul(b, b, Qy);
+ element_add(c, c, a);
+ element_add(z, c, b);
+ element_printf(" = %B\n", z);
+
+ element_clear(a);
+ element_clear(b);
+ element_clear(c);
+ element_clear(e0);
+}
+
+void millertate(element_t z, element_t P, element_t Q)
+{
+ element_t Z;
+ element_t z0;
+
+ element_init_same_as(Z, P);
+ element_init_same_as(z0, z);
+
+ element_set(Z, P);
+
+ do_tangent(z, Z, Q);
+
+ element_double(Z, Z);
+
+ do_vert(z0, Z, Q);
+ element_div(z, z, z0);
+
+ element_printf("presquare: z = %B\n", z);
+
+ element_square(z, z);
+
+ element_printf("square: z = %B\n", z);
+
+ do_tangent(z0, Z, Q);
+ element_mul(z, z, z0);
+
+ element_clear(z0);
+ element_clear(Z);
+}
+
+void tate(element_t z, element_t P, element_t Q)
+{
+ mpz_t q1r;
+
+ mpz_init(q1r);
+ mpz_set_ui(q1r, 696);
+
+ /*
+ millertate(z, P, Q);
+ element_printf("prepow: z = %B\n", z);
+ element_pow_mpz(z, z, q1r);
+ */
+ {
+ element_t R, QR;
+ element_t z0;
+
+ element_init_same_as(R, P);
+ element_init_same_as(QR, P);
+ element_init_same_as(z0, z);
+
+ element_random(R);
+ element_add(QR, Q, R);
+
+ millertate(z, P, QR);
+ millertate(z0, P, R);
+ element_div(z, z, z0);
+ element_pow_mpz(z, z, q1r);
+ element_clear(R);
+ element_clear(QR);
+ }
+
+ mpz_clear(q1r);
+}
+
+void shipseystange(element_t z, element_t P, element_t Q)
+{
+ mpz_t q1r;
+
+ mpz_init(q1r);
+ mpz_set_ui(q1r, 696);
+
+ element_ptr x = curve_x_coord(P);
+ element_ptr y = curve_y_coord(P);
+
+ element_ptr x2 = curve_x_coord(Q);
+ element_ptr y2 = curve_y_coord(Q);
+
+ element_t v0m1, v0m2, v0m3;
+ element_t v00, v01, v02, v03, v04;
+ element_t v1m1, v10, v11;
+ element_t t0, t1, t2;
+ element_t W20inv;
+ element_t Wm11inv;
+ element_t W2m1inv;
+ element_t sm2, sm1, s0, s1, s2, s3;
+ element_t pm2, pm1, p0, p1, p2, p3;
+
+ element_init_same_as(sm2, z);
+ element_init_same_as(sm1, z);
+ element_init_same_as(s0, z);
+ element_init_same_as(s1, z);
+ element_init_same_as(s2, z);
+ element_init_same_as(s3, z);
+
+ element_init_same_as(pm2, z);
+ element_init_same_as(pm1, z);
+ element_init_same_as(p0, z);
+ element_init_same_as(p1, z);
+ element_init_same_as(p2, z);
+ element_init_same_as(p3, z);
+
+ element_init_same_as(v0m3, z);
+ element_init_same_as(v0m2, z);
+ element_init_same_as(v0m1, z);
+ element_init_same_as(v00, z);
+ element_init_same_as(v01, z);
+ element_init_same_as(v02, z);
+ element_init_same_as(v03, z);
+ element_init_same_as(v04, z);
+
+ element_init_same_as(v1m1, z);
+ element_init_same_as(v10, z);
+ element_init_same_as(v11, z);
+
+ element_init_same_as(W20inv, z);
+ element_init_same_as(Wm11inv, z);
+ element_init_same_as(W2m1inv, z);
+
+ element_init_same_as(t0, z);
+ element_init_same_as(t1, z);
+ element_init_same_as(t2, z);
+
+ element_set0(v0m1);
+ element_set1(v00);
+ element_neg(v0m2, v00);
+ element_double(v01, y);
+
+ element_neg(v0m3, v01);
+
+ element_invert(W20inv, v01);
+
+ element_sub(Wm11inv, x, x2);
+ element_square(t1, Wm11inv);
+ element_invert(Wm11inv, Wm11inv);
+ element_double(t0, x);
+ element_add(t0, t0, x2);
+ element_mul(t1, t0, t1);
+ element_add(t0, y, y2);
+ element_square(t0, t0);
+ element_sub(t0, t0, t1);
+ element_invert(W2m1inv, t0);
+
+ /* Let P=(x,y) since A=1, B=0 we have:
+ * W(3,0) = 3x^4 + 6x^2 - 1
+ * W(4,0) = 4y(x^6 + 5x^4 - 5x^2 - 1)
+ */
+
+ //t0 = x^2
+ element_square(t0, x);
+
+ //t1 = x^4
+ element_square(t1, t0);
+
+ //t2 = x^4 + 2 x^2
+ element_double(t2, t0);
+ element_add(t2, t2, t1);
+
+ //v02 = W(3,0)
+ element_double(v02, t2);
+ element_add(v02, v02, t2);
+ element_add(v02, v02, v0m2);
+
+ //t2 = x^4 - x^2
+ element_sub(t2, t1, t0);
+
+ //v03 = 5(x^4 - x^2)
+ element_double(v03, t2);
+ element_double(v03, v03);
+ element_add(v03, v03, t2);
+
+ //t2 = x^6
+ element_mul(t2, t0, t1);
+
+ //v03 = W(4,0)
+ element_add(v03, v03, t2);
+ element_add(v03, v03, v0m2);
+ element_double(v03, v03);
+ element_double(v03, v03);
+ element_mul(v03, v03, y);
+
+ //v04 = W(5,0) = W(2,0)^3 W(4,0) - W(3,0)^3
+ element_square(t0, v01);
+ element_mul(t0, t0, v01);
+ element_mul(v04, t0, v03);
+ element_square(t0, v02);
+ element_mul(t0, t0, v02);
+ element_sub(v04, v04, t0);
+
+ element_set1(v1m1);
+ element_set1(v10);
+
+ element_printf("x y: %B %B\n", x, y);
+ element_printf("x2 y2: %B %B\n", x2, y2);
+ element_sub(t0, x2, x);
+ element_sub(t1, y2, y);
+ element_div(t0, t1, t0);
+ element_square(t0, t0);
+ element_double(v11, x);
+ element_add(v11, v11, x2);
+ element_sub(v11, v11, t0);
+
+ element_printf("VEC1: %B %B %B\n", v1m1, v10, v11);
+ element_printf("VEC0: %B %B %B %B %B %B %B %B\n",
+ v0m3, v0m2, v0m1, v00, v01, v02, v03, v04);
+
+ //Double
+ element_square(sm2, v0m2);
+ element_square(sm1, v0m1);
+ element_square(s0, v00);
+ element_square(s1, v01);
+ element_square(s2, v02);
+ element_square(s3, v03);
+
+ element_mul(pm2, v0m3, v0m1);
+ element_mul(pm1, v0m2, v00);
+ element_mul(p0, v0m1, v01);
+ element_mul(p1, v00, v02);
+ element_mul(p2, v01, v03);
+ element_mul(p3, v02, v04);
+
+ element_mul(t0, pm1, sm2);
+ element_mul(t1, pm2, sm1);
+ element_sub(v0m3, t0, t1);
+
+ element_mul(t1, pm2, s0);
+ element_mul(t0, p0, sm2);
+ element_sub(v0m2, t0, t1);
+ element_mul(v0m2, v0m2, W20inv);
+
+ element_mul(t0, p0, sm1);
+ element_mul(t1, pm1, s0);
+ element_sub(v0m1, t0, t1);
+
+ element_mul(t1, pm1, s1);
+ element_mul(t0, p1, sm1);
+ element_sub(v00, t0, t1);
+ element_mul(v00, v00, W20inv);
+
+ element_mul(t0, p1, s0);
+ element_mul(t1, p0, s1);
+ element_sub(v01, t0, t1);
+
+ element_mul(t1, p0, s2);
+ element_mul(t0, p2, s0);
+ element_sub(v02, t0, t1);
+ element_mul(v02, v02, W20inv);
+
+ element_mul(t0, p2, s1);
+ element_mul(t1, p1, s2);
+ element_sub(v03, t0, t1);
+
+ element_mul(t1, p1, s3);
+ element_mul(t0, p3, s1);
+ element_sub(v04, t0, t1);
+ element_mul(v04, v04, W20inv);
+
+ element_square(t0, v10);
+ element_mul(t1, v1m1, v11);
+
+ element_mul(t2, pm1, t0);
+ element_mul(v1m1, t1, sm1);
+ element_sub(v1m1, v1m1, t2);
+
+ element_mul(t2, p0, t0);
+ element_mul(v10, t1, s0);
+ element_sub(v10, v10, t2);
+
+ element_mul(t2, p1, t0);
+ element_mul(v11, t1, s1);
+ element_sub(v11, v11, t2);
+ element_mul(v11, v11, Wm11inv);
+
+ element_printf("VEC1: %B %B %B\n", v1m1, v10, v11);
+ element_printf("VEC0: %B %B %B %B %B %B %B %B\n",
+ v0m3, v0m2, v0m1, v00, v01, v02, v03, v04);
+
+ //DoubleAdd
+ element_square(sm2, v0m2);
+ element_square(sm1, v0m1);
+ element_square(s0, v00);
+ element_square(s1, v01);
+ element_square(s2, v02);
+ element_square(s3, v03);
+
+ element_mul(pm2, v0m3, v0m1);
+ element_mul(pm1, v0m2, v00);
+ element_mul(p0, v0m1, v01);
+ element_mul(p1, v00, v02);
+ element_mul(p2, v01, v03);
+ element_mul(p3, v02, v04);
+
+ element_mul(t1, pm2, s0);
+ element_mul(t0, p0, sm2);
+ element_sub(v0m3, t0, t1);
+ element_mul(v0m3, v0m3, W20inv);
+
+ element_mul(t0, p0, sm1);
+ element_mul(t1, pm1, s0);
+ element_sub(v0m2, t0, t1);
+
+ element_mul(t1, pm1, s1);
+ element_mul(t0, p1, sm1);
+ element_sub(v0m1, t0, t1);
+ element_mul(v0m1, v0m1, W20inv);
+
+ element_mul(t0, p1, s0);
+ element_mul(t1, p0, s1);
+ element_sub(v00, t0, t1);
+
+ element_mul(t1, p0, s2);
+ element_mul(t0, p2, s0);
+ element_sub(v01, t0, t1);
+ element_mul(v01, v01, W20inv);
+
+ element_mul(t0, p2, s1);
+ element_mul(t1, p1, s2);
+ element_sub(v02, t0, t1);
+
+ element_mul(t1, p1, s3);
+ element_mul(t0, p3, s1);
+ element_sub(v03, t0, t1);
+ element_mul(v03, v03, W20inv);
+
+ element_mul(t0, p3, s2);
+ element_mul(t1, p2, s3);
+ element_sub(v04, t0, t1);
+
+ element_square(t0, v10);
+ element_mul(t1, v1m1, v11);
+
+ element_mul(t2, p0, t0);
+ element_mul(v1m1, t1, s0);
+ element_sub(v1m1, v1m1, t2);
+
+ element_mul(t2, p1, t0);
+ element_mul(v10, t1, s1);
+ element_sub(v10, v10, t2);
+ element_mul(v10, v10, Wm11inv);
+
+ element_mul(t2, t1, s2);
+ element_mul(v11, p2, t0);
+ element_sub(v11, v11, t2);
+ element_mul(v11, v11, W2m1inv);
+
+ element_printf("VEC1: %B %B %B\n", v1m1, v10, v11);
+ element_printf("VEC0: %B %B %B %B %B %B %B %B\n",
+ v0m3, v0m2, v0m1, v00, v01, v02, v03, v04);
+ element_div(z, v11, v01);
+ element_printf("prepow: %B\n", z);
+
+ element_pow_mpz(z, z, q1r);
+
+ mpz_clear(q1r);
+}
+
+void miller(element_t z, element_t PR, element_t R, element_t P, element_t Q)
+{
+ int m = mpz_sizeinbase(order, 2) - 2;
+
+ element_t Z;
+ element_t z1;
+ element_t x1;
+ element_init_same_as(Z, PR);
+
+ element_set(Z, P);
+ element_set1(z);
+ element_init_same_as(z1, z);
+ element_init_same_as(x1, z);
+
+ do_vert(x1, PR, Q);
+ element_printf("vert(P+R) %B\n", x1);
+ do_line(z1, P, R, Q);
+ element_printf("line(P,R) %B\n", z1);
+ element_div(x1, x1, z1);
+ element_printf("x1 %B\n", x1);
+ element_set(z, x1);
+
+ for (;;) {
+ printf("iteration %d: %d\n", m, mpz_tstbit(order,m));
+ element_square(z, z);
+ element_printf("squared: %B\n", z);
+ do_tangent(z1, Z, Q);
+ element_mul(z, z, z1);
+
+ element_double(Z, Z);
+ do_vert(z1, Z, Q);
+ element_div(z, z, z1);
+ element_printf("pre-if: %B\n", z);
+
+ if (mpz_tstbit(order, m)) {
+ element_mul(z, z, x1);
+ do_vert(z1, P, Q);
+ element_mul(z, z, z1);
+ element_printf("done %B\n", z);
+ /*
+ do_line(z1, Z, P, Q);
+ element_mul(z, z, z1);
+ element_add(Z, Z, P);
+ do_vert(z1, Z, Q);
+ element_div(z, z, z1);
+ */
+ }
+ if (!m) break;
+ m--;
+ }
+
+ element_clear(x1);
+ element_clear(z1);
+}
+/*
+*/
+
+void weil(element_t w, element_t g, element_t h)
+{
+ element_t gr;
+ element_t hs;
+ element_t r;
+ element_t s;
+ element_t z, z0, z1;
+
+ element_init(z, Fq2);
+ element_init(z0, Fq2);
+ element_init(z1, Fq2);
+
+ element_init_same_as(gr, g);
+ element_init_same_as(hs, h);
+ element_init_same_as(r, g);
+ element_init_same_as(s, h);
+
+ element_random(r);
+ element_random(s);
+ //point_random always takes the same square root
+ //why not take the other one for once?
+ element_neg(r, r);
+ element_set_str(r, "[[40,0],[54,0]]", 0);
+ element_set_str(s, "[[48,55],[28,51]]", 0);
+
+ element_printf("chose R = %B\n", r);
+ element_printf("chose S = %B\n", s);
+ element_add(gr, g, r);
+ element_add(hs, h, s);
+
+ element_printf("P+R = %B\n", gr);
+ element_printf("Q+S = %B\n", hs);
+ miller(z, gr, r, g, hs);
+ miller(z0, gr, r, g, s);
+ element_div(z1, z, z0);
+ element_printf("num: %B\n", z1);
+
+ miller(z, hs, s, h, gr);
+ miller(z0, hs, s, h, r);
+ element_div(w, z, z0);
+ element_printf("denom: %B\n", w);
+
+ element_div(w, z1, w);
+
+ element_clear(gr);
+ element_clear(r);
+ element_clear(hs);
+ element_clear(s);
+ element_clear(z);
+ element_clear(z0);
+ element_clear(z1);
+}
+
+void fasterweil(element_t w, element_t g, element_t h)
+{
+ element_t hs;
+ element_t s;
+ element_t z, z0, z1;
+
+ element_init(z, Fq2);
+ element_init(z0, Fq2);
+ element_init(z1, Fq2);
+
+ element_init_same_as(hs, h);
+ element_init_same_as(s, h);
+
+ element_random(s);
+ //point_random always takes the same square root
+ //why not take the other one for once?
+ element_set_str(s, "[[48,55],[28,51]]", 0);
+
+ element_printf("chose S = %B\n", s);
+ element_add(hs, h, s);
+
+ element_printf("Q+S = %B\n", hs);
+
+ millertate(z, g, hs);
+ millertate(z0, g, s);
+ element_div(z1, z, z0);
+ element_printf("num: %B\n", z1);
+
+ miller(w, hs, s, h, g);
+ element_printf("denom: %B\n", w);
+
+ element_div(w, z1, w);
+
+ element_clear(z);
+ element_clear(z0);
+ element_clear(z1);
+ element_clear(hs);
+ element_clear(s);
+}
+
+void fasterweil2(element_t w, element_t g, element_t h)
+{
+ element_t gr;
+ element_t r;
+ element_t z, z0, z1;
+
+ element_init(z, Fq2);
+ element_init(z0, Fq2);
+ element_init(z1, Fq2);
+
+ element_init_same_as(gr, g);
+ element_init_same_as(r, g);
+
+ element_random(r);
+ //point_random always takes the same square root
+ //why not take the other one for once?
+ element_set_str(r, "[[48,55],[28,51]]", 0);
+
+ element_printf("chose R = %B\n", r);
+ element_add(gr, g, r);
+
+ element_printf("P+R = %B\n", gr);
+
+ miller(w, gr, r, g, h);
+ element_printf("num: %B\n", w);
+
+ millertate(z, h, gr);
+ millertate(z0, h, r);
+ element_div(z1, z, z0);
+ element_printf("denom: %B\n", z1);
+
+ element_div(w, w, z1);
+
+ element_clear(z);
+ element_clear(z0);
+ element_clear(z1);
+ element_clear(gr);
+ element_clear(r);
+}
+
+int main(void)
+{
+ int i;
+ element_t g, h;
+ element_t w0, w1;
+ element_t a, b;
+ mpz_t prime, cofac;
+
+ mpz_init(prime);
+ mpz_init(order);
+ mpz_init(cofac);
+ mpz_set_ui(prime, 59);
+
+ field_init_fp(Fq, prime);
+
+ element_init(a, Fq);
+ element_init(b, Fq);
+
+ field_init_fi(Fq2, Fq);
+
+ element_set1(a);
+ element_set0(b);
+ mpz_set_ui(order, 5);
+ mpz_set_ui(cofac, 12);
+
+ field_init_curve_ab(E, a, b, order, cofac);
+
+ element_clear(a);
+ element_clear(b);
+ element_init(a, Fq2);
+ element_init(b, Fq2);
+ element_set1(a);
+ element_set0(b);
+
+ mpz_mul(cofac, cofac, cofac);
+ field_init_curve_ab(E2, a, b, order, NULL);
+
+ element_init(g, E2);
+ element_init(h, E2);
+
+ element_init(w0, Fq2);
+ element_init(w1, Fq2);
+
+ /*
+ do {
+ element_random(g);
+ } while (element_is1(g));
+ for (i=1; i<5; i++) {
+ element_mul(h, h, g);
+ element_printf("%d: %B\n", i, h);
+ element_printf("tangent = ");
+ do_tangent(h);
+ }
+ */
+ element_set_str(g, "[[25,0],[30,0]", 0);
+ element_set_str(h, "[[34,0],[0,30]", 0);
+ weil(w0, g, h);
+ element_printf("weil: %B\n", w0);
+
+ element_set1(w1);
+ for (i=1; i<6; i++) {
+ element_mul(w1, w1, w0);
+ element_printf("%d: %B\n", i, w1);
+ }
+
+ fasterweil(w0, g, h);
+ element_printf("fasterweil: %B\n", w0);
+
+ element_set1(w1);
+ for (i=1; i<6; i++) {
+ element_mul(w1, w1, w0);
+ element_printf("%d: %B\n", i, w1);
+ }
+
+ fasterweil2(w0, g, h);
+ element_printf("fasterweil2: %B\n", w0);
+
+ tate(w0, g, h);
+ element_printf("tate: %B\n", w0);
+
+ element_set1(w1);
+ for (i=1; i<6; i++) {
+ element_mul(w1, w1, w0);
+ element_printf("%d: %B\n", i, w1);
+ }
+
+ shipseystange(w0, g, h);
+ element_printf("ss-tate: %B\n", w0);
+
+ element_set1(w1);
+ for (i=1; i<6; i++) {
+ element_mul(w1, w1, w0);
+ element_printf("%d: %B\n", i, w1);
+ }
+ return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/checkfp.c b/moon-abe/pbc-0.5.14/guru/checkfp.c
new file mode 100644
index 00000000..98b9a701
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/checkfp.c
@@ -0,0 +1,334 @@
+// Compares two implementations of Fp.
+
+#include <string.h>
+#include "pbc.h"
+#include "pbc_fp.h"
+#include "pbc_fieldquadratic.h"
+
+static mpz_t prime;
+
+enum { VERBOSE = 0 };
+
+static void check_p(int value, char *s) {
+ if (!value) {
+ printf("BUG: %s predicate wrong\n", s);
+ exit(1);
+ }
+
+ if (VERBOSE) {
+ printf("checking %s\n", s);
+ }
+}
+
+static void check_match_int(int i1, int i2, char *s) {
+ void bug(void)
+ {
+ printf("BUG: %s mismatch\n", s);
+ element_printf("i1: %d\n", i1);
+ element_printf("i2: %d\n", i2);
+ exit(1);
+ }
+
+ if (VERBOSE) {
+ printf("checking %s\n", s);
+ element_printf("i1: %d\n", i1);
+ element_printf("i2: %d\n", i2);
+ }
+
+ if (i1 != i2) bug();
+}
+
+static void check_match(element_t e1, element_t e2, char *s) {
+ unsigned char *buf1, *buf2;
+ int len;
+ void bug(void)
+ {
+ printf("BUG: %s mismatch\n", s);
+ element_printf("e1: %B\n", e1);
+ element_printf("e2: %B\n", e2);
+ exit(1);
+ }
+
+ if (VERBOSE) {
+ printf("checking %s\n", s);
+ element_printf("e1: %B\n", e1);
+ element_printf("e2: %B\n", e2);
+ }
+ len = element_length_in_bytes(e1);
+ if (len != element_length_in_bytes(e2)) {
+ bug();
+ }
+
+ buf1 = pbc_malloc(len);
+ buf2 = pbc_malloc(len);
+ element_to_bytes(buf1, e1);
+ element_to_bytes(buf2, e2);
+
+ if (memcmp(buf1, buf2, len)) {
+ bug();
+ }
+
+ pbc_free(buf1);
+ pbc_free(buf2);
+}
+
+static void run_check(field_ptr f1, field_ptr f2) {
+ mpz_t t1, t2;
+ element_t x1, y1, z1;
+ element_t x2, y2, z2;
+ char s2[80];
+
+ void convertset(element_t out, element_t in)
+ {
+ unsigned char *buf;
+ int len;
+
+ len = element_length_in_bytes(in);
+ buf = pbc_malloc(len);
+ element_to_bytes(buf, in);
+ element_from_bytes(out, buf);
+ pbc_free(buf);
+ check_match(in, out, "conversion");
+ }
+
+ void randxy(void)
+ {
+
+ element_random(x1);
+ element_random(y1);
+ convertset(x2, x1);
+ convertset(y2, y1);
+ }
+
+ void check_onearg(void (*fn)(element_ptr), char *s)
+ {
+ fn(x1);
+ fn(x2);
+ check_match(x1, x2, s);
+ }
+
+ void check_twoarg(void (*fn)(element_ptr, element_ptr), char *s)
+ {
+ randxy();
+ fn(z1, x1);
+ fn(z2, x2);
+ check_match(z1, z2, s);
+
+ strncpy(s2, s, 32);
+ strcat(s2, " (in place)");
+ fn(y1, y1);
+ fn(y2, y2);
+ check_match(y1, y2, s2);
+ }
+
+ void check_threearg(void (*fn)(element_ptr, element_ptr, element_ptr), char *s)
+ {
+ randxy();
+ fn(z1, x1, y1);
+ fn(z2, x2, y2);
+ check_match(z1, z2, s);
+
+ strncpy(s2, s, 32);
+ strcat(s2, " (first arg in place)");
+ element_set(z1, x1);
+ element_set(z2, x2);
+ fn(z1, z1, y1);
+ fn(z2, z2, y2);
+ check_match(z1, z2, s2);
+
+ strncpy(s2, s, 32);
+ strcat(s2, " (second arg in place)");
+ element_set(z1, y1);
+ element_set(z2, y2);
+ fn(z1, x1, z1);
+ fn(z2, x2, z2);
+ check_match(z1, z2, s2);
+
+ strncpy(s2, s, 32);
+ strcat(s2, " (both args in place)");
+ element_set(z1, y1);
+ element_set(z2, y2);
+ fn(x1, x1, x1);
+ fn(x2, x2, x2);
+ check_match(x1, x2, s2);
+ }
+
+ mpz_init(t1);
+ mpz_init(t2);
+ element_init(x1, f1);
+ element_init(y1, f1);
+ element_init(z1, f1);
+ element_init(x2, f2);
+ element_init(y2, f2);
+ element_init(z2, f2);
+
+ check_p(!element_cmp(x1, y1), "cmp0-1");
+ check_p(!element_cmp(x2, y2), "cmp0-2");
+ check_match(z1, z2, "init");
+ check_onearg(element_set0, "set0");
+ check_onearg(element_set1, "set1");
+ check_twoarg(element_set, "set");
+ check_match_int(element_sgn(z1), element_sgn(z2), "sgn");
+
+ check_threearg(element_add, "add");
+ check_twoarg(element_neg, "neg");
+ check_threearg(element_sub, "sub");
+ check_twoarg(element_double, "double");
+ check_twoarg(element_halve, "halve");
+
+ check_twoarg(element_invert, "invert");
+ check_twoarg(element_square, "square");
+ check_threearg(element_mul, "mul");
+
+ randxy();
+ element_neg(y1, x1);
+ element_neg(y2, x2);
+ element_add(z1, x1, y1);
+ element_add(z2, x2, y2);
+ check_match(z1, z2, "add (to zero)");
+ check_p(!element_sgn(z1), "sgn");
+ check_p(!element_sgn(z1), "sgn");
+ check_p(element_is0(z2), "is0");
+ check_p(element_is0(z2), "is0");
+
+ randxy();
+ element_invert(y1, x1);
+ element_invert(y2, x2);
+ element_mul(z1, x1, y1);
+ element_mul(z2, x2, y2);
+ check_match(z1, z2, "mul (to one)");
+ check_p(element_is1(z1), "is1");
+ check_p(element_is1(z2), "is1");
+
+ randxy();
+ check_p(!(!!element_cmp(x1, y1) ^ !!element_cmp(x2, y2)), "cmp");
+ element_set(x1, y1);
+ element_set(x2, y2);
+ check_p(!element_cmp(x1, y1), "cmp");
+ check_p(!element_cmp(x2, y2), "cmp");
+ check_p(!element_cmp(x1, x1), "cmp (in place)");
+ check_p(!element_cmp(x2, x2), "cmp (in place)");
+
+ for (;;) {
+ int flag;
+ randxy();
+ flag = element_is_sqr(x1);
+ check_match_int(flag, element_is_sqr(x2), "is_sqr");
+ if (flag) break;
+ }
+ convertset(x2, x1);
+ element_sqrt(z1, x1);
+ element_sqrt(z2, x2);
+ //can't compare these because sqrt is nondeterministic
+ //and there's no way easy way to preserve random state yet
+ element_square(z1, z1);
+ element_square(z2, z2);
+ check_match(z1, z2, "sqrt");
+
+ pbc_mpz_random(t1, f1->order);
+ pbc_mpz_random(t2, f2->order);
+ element_to_mpz(t1, y1);
+ element_to_mpz(t2, y2);
+ element_set_mpz(y1, t1);
+ element_set_mpz(y2, t2);
+ check_match(y1, y2, "set_mpz");
+ element_mul_mpz(z1, x1, t1);
+ element_mul_mpz(z2, x2, t2);
+ check_match(z1, z2, "mul_mpz");
+ element_pow_mpz(z1, x1, t1);
+ element_pow_mpz(z2, x2, t2);
+ check_match(z1, z2, "pow_mpz");
+ element_mul_si(z1, x1, mpz_get_ui(t1));
+ element_mul_si(z2, x2, mpz_get_ui(t2));
+ check_match(z1, z2, "mul_si");
+ element_set_si(z1, mpz_get_ui(t1));
+ element_set_si(z2, mpz_get_ui(t2));
+ check_match(z1, z2, "set_si");
+
+ element_clear(x1);
+ element_clear(y1);
+ element_clear(z1);
+ element_clear(x2);
+ element_clear(y2);
+ element_clear(z2);
+
+ mpz_clear(t1);
+ mpz_clear(t2);
+}
+
+int main(void) {
+ field_t f1, f2;
+ field_t f1i, f2i;
+ field_t f1x, f2x;
+ field_t f1p, f2p;
+ int i, n;
+ element_ptr n1;
+ element_t n2;
+ element_t irred1, irred2;
+ mpz_t z;
+
+ n = 10;
+
+ mpz_init(z);
+ mpz_init(prime);
+ mpz_set_ui(prime, 1234);
+ mpz_setbit(prime, 160);
+ mpz_nextprime(prime, prime);
+
+ element_printf("prime = %Zd\n", prime);
+
+ field_init_naive_fp(f1, prime);
+ field_init_fp(f2, prime);
+
+ printf("Field 1:\n");
+ field_out_info(stdout, f1);
+ printf("Field 2:\n");
+ field_out_info(stdout, f2);
+
+ printf("checking base fields\n");
+ for (i=0; i<n; i++) run_check(f1, f2);
+
+ element_init(n2, f2);
+
+ n1 = field_get_nqr(f1);
+ element_to_mpz(z, n1);
+ element_set_mpz(n2, z);
+ field_set_nqr(f2, n2);
+
+ field_init_fi(f1i, f1);
+ field_init_fi(f2i, f2);
+
+ printf("checking quadratic field extensions\n");
+ for (i=0; i<n; i++) run_check(f1i, f2i);
+
+ field_clear(f1i);
+ field_clear(f2i);
+ field_init_quadratic(f1i, f1);
+ field_init_quadratic(f2i, f2);
+ for (i=0; i<n; i++) run_check(f1i, f2i);
+
+ printf("checking degree 3 extension\n");
+ field_init_poly(f1x, f1);
+ field_init_poly(f2x, f2);
+ element_init(irred1, f1x);
+ element_init(irred2, f2x);
+ do {
+ poly_random_monic(irred1, 3);
+ } while (!poly_is_irred(irred1));
+
+ field_init_polymod(f1p, irred1);
+ {
+ unsigned char *buf;
+ int len;
+ len = element_length_in_bytes(irred1);
+ buf = pbc_malloc(len);
+ element_to_bytes(buf, irred1);
+ element_from_bytes(irred2, buf);
+ pbc_free(buf);
+ }
+ field_init_polymod(f2p, irred2);
+
+ for (i=0; i<n; i++) run_check(f1p, f2p);
+
+ return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/eta_T_3_test.c b/moon-abe/pbc-0.5.14/guru/eta_T_3_test.c
new file mode 100644
index 00000000..69cce7de
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/eta_T_3_test.c
@@ -0,0 +1,130 @@
+/* Test eta_T pairing over ternary extension fields.
+ Outputing nothing if everything is good. */
+
+#include <stddef.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <gmp.h>
+#include "pbc.h"
+#include "pbc_ternary_extension_field.h"
+#include "pbc_test.h"
+
+static pairing_t pairing;
+static element_t a1, a2, b1, b2, c1, c2;
+static mpz_t order;
+
+static void setup(void) {
+ mpz_init(order);
+ mpz_set_str(order, "2726865189058261010774960798134976187171462721", 10);
+ const char *param = "type i\n" "m 97\n" "t 12\n" "n2 7\n"
+ "n 2726865189058261010774960798134976187171462721\n";
+ EXPECT(pairing_init_set_str(pairing, param) == 0);
+ element_init_G1(a1, pairing);
+ element_init_G1(a2, pairing);
+ element_init_G2(b1, pairing);
+ element_init_G2(b2, pairing);
+ element_init_GT(c1, pairing);
+ element_init_GT(c2, pairing);
+}
+
+static void test_set_mpz(void) {
+ mpz_t a;
+ mpz_init(a);
+ int i;
+ for(i = 0; i < 2; i ++) {
+ mpz_set_si(a, i);
+ element_set_mpz(a1, a);
+ EXPECT(element_is0(a1) && element_is1(a1));
+ element_set_mpz(b1, a);
+ EXPECT(element_is0(b1) && element_is1(b1));
+ element_set_mpz(c1, a);
+ EXPECT(element_is0(c1) && element_is1(c1));
+ }
+ mpz_clear(a);
+}
+
+static void test_order(void) {
+ EXPECT(mpz_cmp(pairing->G1->order, order) == 0);
+ EXPECT(mpz_cmp(pairing->G2->order, order) == 0);
+ EXPECT(mpz_cmp(pairing->GT->order, order) == 0);
+ int i;
+ for (i=0; i<10; i++) {
+ element_random(a1);
+ EXPECT(element_is0(a1) == 0);
+ element_pow_mpz(a1, a1, order);
+ EXPECT(element_is0(a1));
+ element_random(c1);
+ EXPECT(element_is0(c1) == 0);
+ element_pow_mpz(c1, c1, order);
+ EXPECT(element_is0(c1));
+ }
+}
+
+static void test_bilinear_with_zero(void) {
+ element_set0(a1);
+ element_random(b1);
+ element_pairing(c1, a1, b1);
+ EXPECT(element_is0(c1) && element_is1(c1));
+ element_random(a1);
+ element_set0(b1);
+ element_pairing(c1, a1, b1);
+ EXPECT(element_is0(c1) && element_is1(c1));
+ element_set0(a1);
+ element_set0(b1);
+ element_pairing(c1, a1, b1);
+ EXPECT(element_is0(c1) && element_is1(c1));
+}
+
+static void test_bilinear(void) {
+ element_random(a1);
+ element_mul_si(a2, a1, 33);
+ element_random(b1);
+ element_mul_si(b2, b1, 33);
+ element_pairing(c1, a1, b2);
+ element_pairing(c2, a2, b1);
+ EXPECT(element_cmp(c1, c2) == 0);
+ element_mul_mpz(c1, c1, order);
+ EXPECT(element_is0(c1));
+}
+
+static void test_gen_param(void) {
+ typedef struct {
+ unsigned int len;
+ int m;
+ int t;
+ element_ptr p;
+ mpz_t n;
+ mpz_t n2;
+ } params;
+
+ pbc_param_t par;
+ pbc_param_init_i_gen(par, 150);
+ params *p = par->data;
+ EXPECT(p->m == 97);
+ EXPECT(p->t == 12);
+ EXPECT(!mpz_cmp(p->n, order));
+ EXPECT(!mpz_cmp_ui(p->n2, 7));
+ pbc_param_clear(par);
+}
+
+static void tear_down(void) {
+ element_clear(a1);
+ element_clear(a2);
+ element_clear(b1);
+ element_clear(b2);
+ element_clear(c1);
+ element_clear(c2);
+ pairing_clear(pairing);
+ mpz_clear(order);
+}
+
+int main(void) {
+ setup();
+ test_set_mpz();
+ test_order();
+ test_bilinear_with_zero();
+ test_bilinear();
+ test_gen_param();
+ tear_down();
+ return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/exp_test.c b/moon-abe/pbc-0.5.14/guru/exp_test.c
new file mode 100644
index 00000000..02ccfaba
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/exp_test.c
@@ -0,0 +1,88 @@
+// Mutliexponentiation benchmark and test.
+
+#include <string.h>
+#include "pbc.h"
+#include "pbc_test.h"
+
+int main(int argc, char **argv) {
+ pairing_t pairing;
+ element_t g1, u1, up1, g2, u2, up2, r;
+ mpz_t r_mpz;
+ element_pp_t g1_pp, g2_pp;
+ double t0, t1;
+ int i, n;
+
+ printf("reading pairing from stdin...\n");
+ pbc_demo_pairing_init(pairing, argc, argv);
+
+ element_init(r, pairing->Zr);
+ element_init(g1, pairing->G1);
+ element_init(u1, pairing->G1);
+ element_init(up1, pairing->G1);
+ element_init(g2, pairing->G2);
+ element_init(u2, pairing->G2);
+ element_init(up2, pairing->G2);
+
+ element_random(r);
+ element_random(g1);
+ element_random(g2);
+
+ mpz_init(r_mpz);
+ element_to_mpz(r_mpz, r);
+
+ element_pp_init(g1_pp, g1);
+ element_pp_init(g2_pp, g2);
+
+ n = 100;
+ t0 = pbc_get_time();
+ for (i=0; i<n; i++) {
+ element_pow_mpz(u1, g1, r_mpz);
+ }
+ t1 = pbc_get_time();
+ printf("G1 exp:\t\t%fs\n", t1 - t0);
+
+ n = 100;
+ t0 = pbc_get_time();
+ for (i=0; i<n; i++) {
+ element_pow_mpz(u2, g2, r_mpz);
+ }
+ t1 = pbc_get_time();
+ printf("G2 exp:\t\t%fs\n", t1 - t0);
+
+ n = 100;
+ t0 = pbc_get_time();
+ for (i=0; i<n; i++) {
+ element_pp_pow(up1, r_mpz, g1_pp);
+ }
+ t1 = pbc_get_time();
+ printf("G1 pp exp:\t%fs\n", t1 - t0);
+
+ n = 100;
+ t0 = pbc_get_time();
+ for (i=0; i<n; i++) {
+ element_pp_pow(up2, r_mpz, g2_pp);
+ }
+ t1 = pbc_get_time();
+ printf("G2 pp exp:\t%fs\n", t1 - t0);
+
+ if (element_cmp(u1, up1)) {
+ printf("Oops 1!\n");
+ }
+ if (element_cmp(u2, up2)) {
+ printf("Oops 2!\n");
+ }
+
+ mpz_clear(r_mpz);
+ element_clear(g1);
+ element_clear(u1);
+ element_clear(up1);
+ element_clear(g2);
+ element_clear(u2);
+ element_clear(up2);
+ element_clear(r);
+ element_pp_clear(g1_pp);
+ element_pp_clear(g2_pp);
+ pairing_clear(pairing);
+
+ return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/fp_test.c b/moon-abe/pbc-0.5.14/guru/fp_test.c
new file mode 100644
index 00000000..613b4af7
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/fp_test.c
@@ -0,0 +1,95 @@
+// Test F_p.
+
+#include "pbc.h"
+#include "pbc_fp.h"
+#include "pbc_test.h"
+
+int main(void) {
+ field_t fp;
+ mpz_t prime;
+ mpz_t m, n;
+
+ mpz_init(prime);
+ mpz_init(n);
+ mpz_init(m);
+ mpz_set_ui(prime, 100000);
+ mpz_setbit(prime, 33);
+ mpz_nextprime(prime, prime);
+
+ field_init_fp(fp, prime);
+
+ element_t x, y, z;
+ element_init(x, fp);
+ element_init(y, fp);
+ element_init(z, fp);
+
+ long a = 123, b = 456;
+
+ // Conversion to and from signed long.
+ EXPECT(0 == element_to_si(z));
+ element_set1(z);
+ EXPECT(1 == element_to_si(z));
+ element_set0(z);
+ EXPECT(0 == element_to_si(z));
+ element_set_si(x, a);
+ EXPECT(a == element_to_si(x));
+ element_set_si(y, b);
+ EXPECT(b == element_to_si(y));
+ // Assignment, comparison.
+ EXPECT(!element_cmp(x, x));
+ EXPECT(element_cmp(x, y));
+ EXPECT(element_cmp(z, x));
+ element_set(z, x);
+ EXPECT(!element_cmp(z, x));
+ // Arithmetic operations.
+ element_add(z, x, y);
+ EXPECT(a + b == element_to_si(z));
+ element_mul(z, x, y);
+ EXPECT(a * b == element_to_si(z));
+ element_sub(z, y, x);
+ EXPECT(b - a == element_to_si(z));
+ element_set_mpz(z, prime);
+ EXPECT(!element_to_si(z));
+ element_sub(z, z, x);
+ element_to_mpz(n, z);
+ mpz_add_ui(n, n, a);
+ EXPECT(!mpz_cmp(n, prime));
+ element_invert(z, x);
+ element_to_mpz(m, z);
+ mpz_set_ui(n, a);
+ mpz_invert(n, n, prime);
+ EXPECT(!mpz_cmp(m, n));
+ element_invert(z, z);
+ EXPECT(!element_cmp(x, z));
+ element_div(z, y, x);
+ element_to_mpz(m, z);
+ mpz_mul_ui(n, n, b);
+ mpz_mod(n, n, prime);
+ EXPECT(!mpz_cmp(m, n));
+ // Exponentiation.
+ element_pow_zn(z, x, y);
+ element_to_mpz(m, z);
+ mpz_set_si(n, a);
+ mpz_powm_ui(n, n, b, prime);
+ EXPECT(!mpz_cmp(m, n));
+ // Preprocessed exponentiation.
+ element_pp_t p;
+ element_pp_init(p, x);
+ element_pp_pow_zn(z, y, p);
+ element_pp_clear(p);
+ element_to_mpz(m, z);
+ EXPECT(!mpz_cmp(m, n));
+
+ element_from_hash(z, NULL, 0);
+ element_from_hash(x, NULL, 0);
+ EXPECT(!element_cmp(z, x));
+
+ element_clear(x);
+ element_clear(y);
+ element_clear(z);
+ field_clear(fp);
+ mpz_clear(prime);
+ mpz_clear(m);
+ mpz_clear(n);
+ return pbc_err_count;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/indexcalculus.c b/moon-abe/pbc-0.5.14/guru/indexcalculus.c
new file mode 100644
index 00000000..4ef5e4ea
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/indexcalculus.c
@@ -0,0 +1,869 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h> // for intptr_t
+#include <string.h>
+#include <math.h>
+#include <gmp.h>
+#include "pbc.h"
+#include "pbc_utils.h"
+
+struct cell_s {
+ int ind;
+ mpz_t data;
+};
+typedef struct cell_s *cell_ptr;
+
+static cell_ptr newcell(void)
+{
+ cell_ptr res;
+ res = pbc_malloc(sizeof(struct cell_s));
+ //res->data = pbc_malloc(sizeof(mpz_t));
+ //mpz_init(res->data);
+ mpz_init(res->data);
+ return res;
+}
+
+static void delcell(void *p)
+{
+ cell_ptr cp = p;
+ mpz_clear(cp->data);
+ pbc_free(p);
+}
+
+static int is_gen(mpz_t x, mpz_t q, darray_ptr fac, darray_ptr mul) {
+ int result = 1;
+ mpz_t z;
+ mpz_t q1;
+ int i;
+ UNUSED_VAR(mul);
+
+ mpz_init(z);
+ mpz_init(q1);
+
+ mpz_sub_ui(q1, q, 1);
+ for (i=0; i<fac->count; i++) {
+ mpz_divexact(z, q1, fac->item[i]);
+ mpz_powm(z, x, z, q);
+ if (!mpz_cmp_ui(z, 1)) {
+ result = 0;
+ break;
+ }
+ }
+
+ mpz_clear(q1);
+ mpz_clear(z);
+ return result;
+}
+
+// Garner's Algorithm.
+// See Algorithm 14.71, Handbook of Cryptography.
+static void CRT(mpz_t x, mpz_ptr *v, mpz_ptr *m, int t) {
+ mpz_t u;
+ mpz_t C[t];
+ int i, j;
+
+ mpz_init(u);
+ for (i=1; i<t; i++) {
+ mpz_init(C[i]);
+ mpz_set_ui(C[i], 1);
+ for (j=0; j<i; j++) {
+ mpz_invert(u, m[j], m[i]);
+ mpz_mul(C[i], C[i], u);
+ mpz_mod(C[i], C[i], m[i]);
+ }
+ }
+ mpz_set(u, v[0]);
+ mpz_set(x, u);
+ for (i=1; i<t; i++) {
+ mpz_sub(u, v[i], x);
+ mpz_mul(u, u, C[i]);
+ mpz_mod(u, u, m[i]);
+ for (j=0; j<i; j++) {
+ mpz_mul(u, u, m[j]);
+ }
+ mpz_add(x, x, u);
+ }
+
+ for (i=1; i<t; i++) mpz_clear(C[i]);
+ mpz_clear(u);
+}
+
+//TODO: http://www.cecm.sfu.ca/CAG/abstracts/aaron27Jan06.pdf
+//TODO: don't need to store last element of list in row[i]
+//TODO: linked lists might be better than dynamic arrays (avoids memmove())
+//TODO: allow holes in the table
+//(if drought lasts too long)
+void index_calculus_step1(mpz_t *ind, int r, mpz_t g, mpz_t q,
+ darray_ptr fac, darray_ptr mul) {
+ int count = 0;
+ int i, j;
+ mpz_t z, z0, z1;
+ int relcount;
+ unsigned int *prime = pbc_malloc(sizeof(unsigned int) * r);
+ int bundlecount = (r - 10 + 19) / 20;
+ mpz_t *bundle = pbc_malloc(sizeof(mpz_t) * bundlecount);
+ int faci;
+ mpz_t k, km;
+
+ cell_ptr *rel = pbc_malloc(sizeof(cell_ptr) * r);
+ cell_ptr *relm = pbc_malloc(sizeof(cell_ptr) * r);
+ //''matrix'' is actually a list of matrices
+ //(we solve over different moduli and combine using CRT)
+ //darray_t **matrix = pbc_malloc(sizeof(darray_t *) * fac->count);
+ darray_t *matrix[fac->count];
+ int minfound[fac->count];
+
+ for (i=0; i<r; i++) {
+ rel[i] = newcell();
+ relm[i] = newcell();
+ }
+ for (i=0; i<fac->count; i++) {
+ //similarly ''row'' refers to a list of rows
+ darray_t *row = pbc_malloc(sizeof(darray_t) * r);
+ for (j=0; j<r; j++) {
+ darray_init(row[j]);
+ }
+ matrix[i] = row;
+ minfound[i] = 0;
+ }
+
+ mpz_init(k);
+ mpz_init(km);
+ mpz_init(z);
+ mpz_init(z1);
+ mpz_init(z0);
+
+ printf("building prime table...\n");
+ prime[0] = 2;
+ mpz_set_ui(z, 2);
+ for (i=1; i<r; i++) {
+ mpz_nextprime(z, z);
+ prime[i] = mpz_get_ui(z);
+ }
+
+ for (i=0; i<bundlecount; i++) {
+ mpz_init(bundle[i]);
+ mpz_set_ui(bundle[i], 1);
+ for (j=0; j<20; j++) {
+ int jj = 10 + 20 * i + j;
+ if (jj >= r) break;
+ mpz_mul_ui(bundle[i], bundle[i], prime[jj]);
+ }
+ element_printf("bundle %d: %Zd\n", i, bundle[i]);
+ }
+ printf("searching for r-smooth numbers\n");
+
+ mpz_set_ui(z, 1);
+ mpz_init(k);
+ int try = 0;
+ do {
+ mpz_mul(z, z, g);
+ mpz_mod(z, z, q);
+ mpz_add_ui(k, k, 1);
+
+ /*
+ pbc_mpz_random(k, q);
+ mpz_powm(z, g, k, q);
+ */
+
+ try++;
+
+ mpz_set(z1, z);
+ relcount = 0;
+ for (i=0; i<10; i++) {
+ if (i >= r) break;
+ j = 0;
+ while (mpz_divisible_ui_p(z1, prime[i])) {
+ mpz_divexact_ui(z1, z1, prime[i]);
+ j++;
+ }
+ if (j) {
+ rel[relcount]->ind = i;
+ mpz_set_ui(rel[relcount]->data, j);
+ relcount++;
+ if (!mpz_cmp_ui(z1, 1)) goto found;
+ }
+ }
+ for (i=0; i<bundlecount; i++) {
+ mpz_gcd(z0, bundle[i], z1);
+ if (mpz_cmp_ui(z0, 1)) {
+ int ii;
+ for (ii = 0; ii < 20; ii++) {
+ int jj = 10 + i * 20 + ii;
+ if (jj >= r) break;
+ j = 0;
+ while (mpz_divisible_ui_p(z1, prime[jj])) {
+ mpz_divexact_ui(z1, z1, prime[jj]);
+ j++;
+ }
+ if (j) {
+ rel[relcount]->ind = jj;
+ mpz_set_ui(rel[relcount]->data, j);
+ relcount++;
+ if (!mpz_cmp_ui(z1, 1)) goto found;
+ }
+ }
+ }
+ }
+ continue;
+found:
+
+/*
+ printf("found r-smooth number after %d tries\n", try);
+
+ gmp_printf("g^%Zd = %Zd:", k, z);
+ for (i=0; i<relcount; i++) {
+ gmp_printf(" %u:%Zd", rel[i]->ind, rel[i]->data);
+ }
+ printf("\n");
+*/
+ try = 0;
+
+ for (faci=0; faci<fac->count; faci++) {
+ darray_t *row = matrix[faci];
+ mpz_ptr order = fac->item[faci];
+ int relmcount = 0;
+ mpz_mod(km, k, order);
+
+ //gmp_printf("mod %Zd\n", order);
+ for (i=0; i<relcount; i++) {
+ mpz_mod(z0, rel[i]->data, order);
+ if (mpz_sgn(z0)) {
+ mpz_set(relm[relmcount]->data, z0);
+ relm[relmcount]->ind = rel[i]->ind;
+ relmcount++;
+ }
+ }
+
+ while (relmcount) {
+ //start from the sparse end
+ int rind = relm[relmcount - 1]->ind;
+ darray_ptr rp = row[rind];
+
+ if (rind < minfound[faci]) break;
+
+ mpz_set(z0, relm[relmcount - 1]->data);
+ if (!rp->count) {
+ mpz_invert(z0, z0, order);
+ cell_ptr cnew = newcell();
+ cnew->ind = -1;
+ mpz_mul(z1, km, z0);
+ mpz_mod(cnew->data, z1, order);
+ darray_append(rp, cnew);
+ for (j=0; j<relmcount; j++) {
+ cnew = newcell();
+ cnew->ind = relm[j]->ind;
+ mpz_mul(z1, relm[j]->data, z0);
+ mpz_mod(cnew->data, z1, order);
+ darray_append(rp, cnew);
+ }
+ count++;
+printf("%d / %d\n", count, r * fac->count);
+/*
+for (i=1; i<rp->count; i++) {
+ cnew = rp->item[i];
+ gmp_printf(" %u:%Zd", cnew->ind, cnew->data);
+}
+cnew = rp->item[0];
+gmp_printf(" %Zd\n", cnew->data);
+*/
+
+ if (rind == minfound[faci]) {
+ do {
+ if (!minfound[faci]) {
+ printf("found log p_%d\n", minfound[faci]);
+ cnew = rp->item[0];
+ gmp_printf("km = %Zd mod %Zd\n", cnew->data, order);
+ }
+ minfound[faci]++;
+ if (minfound[faci] >= r) break;
+ rp = row[minfound[faci]];
+ } while (rp->count);
+ }
+ break;
+
+ }
+
+/*
+{
+//gmp_printf("mod = %Zd\n", order);
+printf("before:");
+for (i=0; i<relmcount; i++) {
+ gmp_printf(" %u:%Zd", relm[i]->ind, relm[i]->data);
+}
+gmp_printf(" %Zd\n", km);
+cell_ptr cp;
+printf("sub %d:", rind);
+for (i=1; i<rp->count; i++) {
+ cp = rp->item[i];
+ gmp_printf(" %u:%Zd", cp->ind, cp->data);
+}
+cp = rp->item[0];
+gmp_printf(" %Zd\n", cp->data);
+}
+*/
+ cell_ptr cpi, cpj;
+ relmcount--;
+ i=0; j=1;
+ while (i<relmcount && j<rp->count - 1) {
+ cpi = relm[i];
+ cpj = rp->item[j];
+ if (cpi->ind == cpj->ind) {
+ mpz_mul(z1, z0, cpj->data);
+ mpz_mod(z1, z1, order);
+ int res = mpz_cmp(z1, cpi->data);
+ if (!res) {
+ memmove(&relm[i], &relm[i + 1], (relmcount - i - 1) * sizeof(cell_ptr));
+ relm[relmcount - 1] = cpi;
+ relmcount--;
+ j++;
+ } else if (res > 0) {
+ mpz_sub(z1, order, z1);
+ mpz_add(cpi->data, cpi->data, z1);
+ i++;
+ j++;
+ } else {
+ mpz_sub(cpi->data, cpi->data, z1);
+ i++;
+ j++;
+ }
+ } else if (cpi->ind > cpj->ind) {
+ cpi = relm[relmcount];
+ memmove(&relm[i + 1], &relm[i], (relmcount - i) * sizeof(cell_ptr));
+ relm[i] = cpi;
+ relmcount++;
+
+ cpi->ind = cpj->ind;
+ mpz_mul(z1, z0, cpj->data);
+ mpz_mod(z1, z1, order);
+ mpz_sub(cpi->data, order, z1);
+ //cpi->data = order - ((u0 * cpj->data) % order);
+ i++;
+ j++;
+ } else {
+ i++;
+ }
+ }
+
+ if (i == relmcount) {
+ while (j < rp->count - 1) {
+ cpi = relm[relmcount];
+ cpj = rp->item[j];
+ cpi->ind = cpj->ind;
+ mpz_mul(z1, z0, cpj->data);
+ mpz_mod(z1, z1, order);
+ mpz_sub(cpi->data, order, z1);
+ //cpi->data = order - ((u0 * cpj->data) % order);
+ relmcount++;
+ j++;
+ }
+ }
+
+ cpj = rp->item[0];
+ mpz_mul(z1, z0, cpj->data);
+ mpz_mod(z1, z1, order);
+ //u1 = (u0 * cpj->data) % order;
+ if (mpz_cmp(km, z1) >= 0) {
+ mpz_sub(km, km, z1);
+ } else {
+ mpz_sub(z1, order, z1);
+ mpz_add(km, km, z1);
+ }
+
+/*
+printf("after:");
+for (i=0; i<relmcount; i++) {
+ gmp_printf(" %u:%Zd", relm[i]->ind, relm[i]->data);
+}
+gmp_printf(" %Zd\n", km);
+*/
+ }
+ }
+
+ } while (count < r * fac->count);
+
+ for (faci=0; faci<fac->count; faci++) {
+ darray_t *row = matrix[faci];
+ mpz_ptr order = fac->item[faci];
+ for (i=1; i<r; i++) {
+ darray_ptr rp = row[i];
+ cell_ptr c0 = rp->item[0];
+ for (j=1; j<rp->count-1; j++) {
+ cell_ptr cp = rp->item[j];
+ darray_ptr r2 = row[cp->ind];
+ cell_ptr c2 = r2->item[0];
+ mpz_mul(z0, cp->data, c2->data);
+ mpz_sub(c0->data, c0->data, z0);
+ mpz_mod(c0->data, c0->data, order);
+ }
+ }
+ }
+
+ mpz_ptr *tmp = pbc_malloc(sizeof(mpz_ptr) * fac->count);
+ for (i=0; i<fac->count; i++) {
+ tmp[i] = pbc_malloc(sizeof(mpz_t));
+ mpz_init(tmp[i]);
+ mpz_pow_ui(fac->item[i], fac->item[i], (unsigned int) mul->item[i]);
+ }
+
+ for (i=0; i<r; i++) {
+ for (faci=0; faci<fac->count; faci++) {
+ darray_t *row = matrix[faci];
+ cell_ptr cp = row[i]->item[0];
+ mpz_set(tmp[faci], cp->data);
+ }
+ CRT(ind[i], tmp, (mpz_ptr *) fac->item, fac->count);
+ }
+
+ for (i=0; i<fac->count; i++) {
+ mpz_clear(tmp[i]);
+ }
+ pbc_free(tmp);
+
+ for (faci=0; i<fac->count; faci++) {
+ //similarly ''row'' refers to a list of rows
+ darray_t *row = matrix[faci];
+ for (j=0; j<r; j++) {
+ darray_forall(row[j], delcell);
+ darray_clear(row[j]);
+ }
+ pbc_free(matrix[faci]);
+ }
+
+ for (i=0; i<r; i++) {
+ delcell(rel[i]);
+ delcell(relm[i]);
+ }
+
+ pbc_free(prime);
+ pbc_free(rel);
+ pbc_free(relm);
+ mpz_clear(k);
+ mpz_clear(km);
+ mpz_clear(z);
+ mpz_clear(z0);
+ mpz_clear(z1);
+}
+
+// Brute-force: does not use the fact that matrices are sparse.
+void slow_index_calculus_step1(mpz_t *ind, int r, mpz_t g, mpz_t q,
+ darray_ptr fac, darray_ptr mul) {
+ int count = 0;
+ int i, j;
+ mpz_t z, z0, z1;
+ //mpz_t rel[r + 1];
+ //mpz_t relm[r + 1];
+ mpz_t *rel = pbc_malloc(sizeof(mpz_t) * (r + 1));
+ mpz_t *relm = pbc_malloc(sizeof(mpz_t) * (r + 1));
+ unsigned int *prime = pbc_malloc(sizeof(unsigned int) * r);
+ darray_t matrix;
+ int faci;
+ mpz_t k;
+ int minfound[fac->count];
+
+ for (i=0; i<r+1; i++) mpz_init(rel[i]);
+ for (i=0; i<r+1; i++) mpz_init(relm[i]);
+
+ mpz_init(k);
+ mpz_init(z);
+ mpz_init(z1);
+ mpz_init(z0);
+
+ darray_init(matrix);
+
+ for (i=0; i<fac->count; i++) {
+ darray_append(matrix, pbc_malloc(r * sizeof(mpz_t *)));
+ minfound[i] = 0;
+ }
+
+ for (j=0; j<fac->count; j++) {
+ mpz_t **row = matrix->item[j];
+ for (i=0; i<r; i++) row[i] = NULL;
+ }
+
+ printf("building prime table...\n");
+ prime[0] = 2;
+ mpz_set_ui(z, 2);
+ for (i=1; i<r; i++) {
+ mpz_nextprime(z, z);
+ prime[i] = mpz_get_ui(z);
+ }
+ printf("searching for r-smooth numbers\n");
+
+ mpz_set_ui(z, 1);
+ mpz_init(k);
+ int try = 0;
+ do {
+ mpz_mul(z, z, g);
+ mpz_mod(z, z, q);
+
+ mpz_add_ui(k, k, 1);
+ /*
+ pbc_mpz_random(k, q);
+ mpz_powm(z, g, k, q);
+ */
+
+ try++;
+
+ mpz_set(z1, z);
+ for (i=0; i<r; i++) {
+ mpz_set_ui(rel[i], 0);
+ while (mpz_divisible_ui_p(z1, prime[i])) {
+ mpz_add_ui(rel[i], rel[i], 1);
+ mpz_divexact_ui(z1, z1, prime[i]);
+ }
+ }
+ if (mpz_cmp_ui(z1, 1)) {
+ continue;
+ }
+ mpz_set(rel[r], k);
+
+/*
+ printf("found r-smooth number after %d tries\n", try);
+ gmp_printf("g^%Zd = %Zd:", rel[r], z);
+ for (i=0; i<r; i++) {
+ if (mpz_sgn(rel[i])) {
+ gmp_printf(" %u:%Zd", i, rel[i]);
+ }
+ }
+ printf("\n");
+*/
+
+ try = 0;
+
+ for (faci=0; faci<fac->count; faci++) {
+ mpz_t **row = matrix->item[faci];
+ mpz_ptr order = fac->item[faci];
+ //gmp_printf("mod %Zd\n", order);
+ for (i=0; i<r+1; i++) {
+ mpz_mod(relm[i], rel[i], order);
+ }
+
+ for (;;) {
+ /*
+ for (i=0; i<r && !mpz_sgn(relm[i]); i++);
+ if (i == r) {
+ //printf("redundant relation\n");
+ break;
+ }
+ */
+ for (i=r-1; i>=0 && !mpz_sgn(relm[i]); i--);
+ if (i < 0) {
+ //printf("redundant relation\n");
+ break;
+ }
+ if (i < minfound[faci]) {
+ break;
+ }
+ mpz_set(z0, relm[i]);
+ if (!row[i]) {
+ row[i] = pbc_malloc(sizeof(mpz_t) * (r + 1));
+ mpz_invert(z1, z0, order);
+ for (j=0; j<r+1; j++) {
+ mpz_init(row[i][j]);
+ mpz_mul(row[i][j], z1, relm[j]);
+ mpz_mod(row[i][j], row[i][j], order);
+ }
+ count++;
+printf("%d / %d\n", count, r * fac->count);
+/*
+for (j=0; j<r; j++) {
+ if (mpz_sgn(row[i][j])) {
+ gmp_printf(" %d:%Zd", j, row[i][j]);
+ }
+}
+gmp_printf(" %Zd\n", row[i][j]);
+*/
+
+ if (i == minfound[faci]) {
+ do {
+ if (!minfound[faci]) {
+ printf("found log p_%d\n", minfound[faci]);
+ gmp_printf("km = %Zd mod %Zd\n", row[i][r], order);
+ }
+ minfound[faci]++;
+ if (minfound[faci] >= r) break;
+ } while (row[minfound[faci]]);
+ }
+ break;
+ }
+
+ /*
+ printf("before:");
+ for (j=0; j<r; j++) {
+ if (mpz_sgn(relm[j])) {
+ gmp_printf(" %d:%Zd", j, relm[j]);
+ }
+ }
+ gmp_printf(" %Zd\n", relm[j]);
+
+ printf("sub %d:", i);
+ for (j=0; j<r; j++) {
+ if (mpz_sgn(row[i][j])) {
+ gmp_printf(" %d:%Zd", j, row[i][j]);
+ }
+ }
+ gmp_printf(" %Zd\n", row[i][j]);
+ */
+
+ for (j=0; j<r+1; j++) {
+ mpz_mul(z1, z0, row[i][j]);
+ mpz_sub(relm[j], relm[j], z1);
+ mpz_mod(relm[j], relm[j], order);
+ }
+
+ /*
+ printf("after:");
+ for (j=0; j<r; j++) {
+ if (mpz_sgn(relm[j])) {
+ gmp_printf(" %d:%Zd", j, relm[j]);
+ }
+ }
+ gmp_printf(" %Zd\n", relm[j]);
+ */
+ }
+ }
+
+ } while (count < r * fac->count);
+
+ for (faci=0; faci<fac->count; faci++) {
+ mpz_t **row = matrix->item[faci];
+ mpz_ptr order = fac->item[faci];
+ /*
+ gmp_printf("mod %Zd:\n", order);
+ for (i=0; i<r; i++) {
+ for (j=0; j<r+1; j++) {
+ gmp_printf(" %Zd", row[i][j]);
+ }
+ printf("\n");
+ }
+ printf("\n");
+ */
+
+ for (i=1; i<r; i++) {
+ for (j=0; j<i; j++) {
+ if (mpz_sgn(row[i][j])) {
+ mpz_mul(z0, row[i][j], row[j][r]);
+ mpz_sub(row[i][r], row[i][r], z0);
+ mpz_mod(row[i][r], row[i][r], order);
+ }
+ }
+ }
+ /*
+ for (i=r-2; i>=0; i--) {
+ for (j=i+1; j<r; j++) {
+ if (mpz_sgn(row[i][j])) {
+ mpz_mul(z0, row[i][j], row[j][r]);
+ mpz_sub(row[i][r], row[i][r], z0);
+ mpz_mod(row[i][r], row[i][r], order);
+ }
+ }
+ }
+ */
+
+ /*
+ for (i=0; i<r; i++) {
+ mpz_set(rel[i], row[i][r]);
+ gmp_printf(" %Zd", row[i][r]);
+ printf("\n");
+ }
+ */
+ }
+
+ mpz_ptr *tmp = pbc_malloc(sizeof(mpz_ptr) * fac->count);
+ for (i=0; i<fac->count; i++) {
+ tmp[i] = pbc_malloc(sizeof(mpz_t));
+ mpz_init(tmp[i]);
+ mpz_pow_ui(fac->item[i], fac->item[i], (unsigned int) mul->item[i]);
+ }
+
+ for (i=0; i<r; i++) {
+ for (faci=0; faci<fac->count; faci++) {
+ mpz_t **row = matrix->item[faci];
+ mpz_set(tmp[faci], row[i][r]);
+ }
+ CRT(ind[i], tmp, (mpz_ptr *) fac->item, fac->count);
+ }
+
+ for (i=0; i<fac->count; i++) {
+ mpz_clear(tmp[i]);
+ }
+ pbc_free(tmp);
+
+ for (faci=0; faci<matrix->count; faci++) {
+ mpz_t **row = matrix->item[faci];
+ for (j=0; j<r; j++) {
+ for (i=0; i<r+1; i++) {
+ mpz_clear(row[j][i]);
+ }
+ pbc_free(row[j]);
+ }
+ pbc_free(row);
+ }
+ darray_clear(matrix);
+ for (i=0; i<r+1; i++) mpz_clear(rel[i]);
+ for (i=0; i<r+1; i++) mpz_clear(relm[i]);
+ pbc_free(prime);
+ pbc_free(rel);
+ pbc_free(relm);
+ mpz_clear(k);
+ mpz_clear(z);
+ mpz_clear(z0);
+ mpz_clear(z1);
+
+ printf("step 1 completed\n");
+ for (i=0; i<r; i++) element_printf(" %Zd", ind[i]);
+ printf("\n");
+}
+
+static void index_calculus_step2(mpz_t x, mpz_t *ind, int r,
+ mpz_t g, mpz_t h, mpz_t q) {
+ mpz_t prime;
+ mpz_t s;
+ mpz_t z, z1;
+ mpz_t rel[r];
+ int i;
+
+ mpz_init(z);
+ mpz_init(z1);
+ mpz_init(s);
+ mpz_init(prime);
+ for (i=0; i<r; i++) mpz_init(rel[i]);
+
+ mpz_set(z, h);
+
+ for (;;) {
+ mpz_mul(z, z, g);
+ mpz_mod(z, z, q);
+ mpz_add_ui(s, s, 1);
+
+ mpz_set(z1, z);
+ mpz_set_ui(prime, 1);
+ for (i=0; i<r; i++) {
+ mpz_set_ui(rel[i], 0);
+ mpz_nextprime(prime, prime);
+ while (mpz_divisible_p(z1, prime)) {
+ mpz_add_ui(rel[i], rel[i], 1);
+ mpz_divexact(z1, z1, prime);
+ }
+ }
+ if (mpz_cmp_ui(z1, 1)) continue;
+ element_printf("found r-smooth number on try #%Zd\n", s);
+ mpz_set_ui(x, 0);
+ for (i=0; i<r; i++) {
+ mpz_mul(z, rel[i], ind[i]);
+ mpz_add(x, x, z);
+ }
+ mpz_sub(x, x, s);
+ mpz_sub_ui(z, q, 1);
+ mpz_mod(x, x, z);
+ break;
+ }
+}
+
+static void mpzclear(void *p) {
+ mpz_clear(p);
+ pbc_free(p);
+}
+
+struct addfm_scope_var {
+ darray_ptr fac, mul;
+};
+
+static int addfm(mpz_t f, unsigned int m, struct addfm_scope_var *v) {
+ darray_append(v->fac, f);
+ darray_append(v->mul, int_to_voidp(m));
+ return 0;
+}
+
+void pbc_mpz_index_calculus(mpz_t x, mpz_t g, mpz_t h, mpz_t q) {
+ int i, r;
+ mpz_t q1, z0;
+
+ mpz_init(q1);
+ mpz_init(z0);
+
+ mpz_sub_ui(q1, q, 1);
+ mpz_setbit(z0, 6);
+
+ darray_t fac, mul;
+ darray_init(fac);
+ darray_init(mul);
+ struct addfm_scope_var v = {.fac = fac, .mul = mul};
+ pbc_trial_divide((int(*)(mpz_t,unsigned,void*))addfm, &v, q1, z0);
+
+ for (i=0; i<mul->count; i++) {
+ unsigned int m = (unsigned int) mul->item[i];
+ if (m != 1) {
+ //TODO
+ printf("p-adics not implemented yet\n");
+ return;
+ }
+ }
+
+ {
+ double dq = mpz_get_d(q);
+ //r = exp(sqrt(log(dq)*log(log(dq))));
+ //printf("r = %d\n", r);
+ r = exp(1.2 * sqrt(log(dq)));
+ printf("r = %d\n", r);
+ }
+ mpz_t *ind = pbc_malloc(sizeof(mpz_t) * r);
+ for (i=0; i<r; i++) mpz_init(ind[i]);
+
+ if (is_gen(g, q, fac, mul)) {
+
+ index_calculus_step1(ind, r, g, q, fac, mul);
+
+ index_calculus_step2(x, ind, r, g, h, q);
+ } else {
+ mpz_t y, z;
+ mpz_t d;
+
+ mpz_init(d);
+ mpz_init(y);
+ mpz_init(z);
+ do {
+ pbc_mpz_random(z, q);
+ } while (!is_gen(z, q, fac, mul));
+
+ gmp_printf("new gen: %Zd\n", z);
+
+ index_calculus_step1(ind, r, z, q, fac, mul);
+ //slow_index_calculus_step1(ind, r, z, q, fac, mul);
+
+ index_calculus_step2(x, ind, r, z, g, q);
+ index_calculus_step2(y, ind, r, z, h, q);
+ //want y / x mod q-1
+ mpz_gcd(d, x, q1);
+ mpz_divexact(q1, q1, d);
+ mpz_divexact(x, x, d);
+ //if y not divisible by d there is no solution
+ mpz_divexact(y, y, d);
+ mpz_invert(x, x, q1);
+ mpz_mul(x, y, x);
+ mpz_mod(x, x, q1);
+
+ do {
+ mpz_powm(z0, g, x, q);
+ if (!mpz_cmp(z0, h)) {
+ break;
+ }
+ mpz_add(x, x, q1);
+ mpz_sub_ui(d, d, 1);
+ } while (mpz_sgn(d));
+
+ mpz_clear(d);
+ mpz_clear(y);
+ mpz_clear(z);
+ }
+
+ for (i=0; i<r; i++) mpz_clear(ind[i]);
+ pbc_free(ind);
+
+ darray_forall(fac, mpzclear);
+ darray_clear(mul);
+ darray_clear(fac);
+ mpz_clear(q1);
+ mpz_clear(z0);
+}
diff --git a/moon-abe/pbc-0.5.14/guru/param_parse_test.c b/moon-abe/pbc-0.5.14/guru/param_parse_test.c
new file mode 100644
index 00000000..a345e2c1
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/param_parse_test.c
@@ -0,0 +1,26 @@
+// Exercises a bug reported by Michael Adjedj.
+//
+// In ecc/param.c, token_get() would increment a pointer past a terminating
+// NUL, so the parser would keep attempting to read key/value pairs for a
+// symbol table. If the memory after the string contains a duplicate key,
+// then we have a memory leak because we strdup the value and misc/symtab.c
+// overwrites existing elements during insert.
+//
+// Run with valgrind to spot the bug.
+#include "pbc.h"
+
+int main(void) {
+ pairing_t p;
+ pairing_init_set_str(p,
+"type a\n"
+"q 8780710799663312522437781984754049815806883199414208211028653399266475630880222957078625179422662221423155858769582317459277713367317481324925129998224791\n"
+"h 12016012264891146079388821366740534204802954401251311822919615131047207289359704531102844802183906537786776\n"
+"r 730750818665451621361119245571504901405976559617\n"
+"exp2 159\n"
+"exp1 107\n"
+"sign1 1\n"
+"sign0 1\0a b a b\n"
+ );
+ pairing_clear(p);
+ return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/poly_test.c b/moon-abe/pbc-0.5.14/guru/poly_test.c
new file mode 100644
index 00000000..08ff597f
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/poly_test.c
@@ -0,0 +1,136 @@
+// Test polynomials.
+#include "pbc.h"
+#include "pbc_fp.h"
+#include "pbc_poly.h"
+#include "pbc_test.h"
+#include "misc/darray.h"
+
+static void elfree(void *data) {
+ element_clear(data);
+ pbc_free(data);
+}
+
+static void inner(void *data2, element_ptr f, field_t fx, darray_t prodlist) {
+ element_ptr g = data2;
+ if (!poly_degree(f) || !poly_degree(g)) return;
+ if (poly_degree(f) + poly_degree(g) > 3) return;
+ element_ptr h = pbc_malloc(sizeof(*h));
+ element_init(h, fx);
+ element_mul(h, f, g);
+ darray_append(prodlist, h);
+ EXPECT(!poly_is_irred(h));
+}
+
+static void outer(void *data, darray_t list, field_t fx, darray_t prodlist) {
+ element_ptr f = data;
+ darray_forall4(list, (void(*)(void*,void*,void*,void*))inner, f, fx, prodlist);
+}
+
+int isf(void *data, element_ptr f) {
+ element_ptr f1 = data;
+ return !element_cmp(f, f1);
+}
+
+int main(void) {
+ field_t fp, fx;
+ mpz_t prime;
+ darray_t list;
+ int p = 7;
+
+ // Exercise poly_is_irred() with a sieve of Erastosthenes for polynomials.
+ darray_init(list);
+ mpz_init(prime);
+ mpz_set_ui(prime, p);
+ field_init_fp(fp, prime);
+ field_init_poly(fx, fp);
+ element_t e;
+ element_init(e, fp);
+ // Enumerate polynomials in F_p[x] up to degree 2.
+ int a[3], d;
+ a[0] = a[1] = a[2] = 0;
+ for(;;) {
+ element_ptr f = pbc_malloc(sizeof(*f));
+ element_init(f, fx);
+ int j;
+ for(j = 0; j < 3; j++) {
+ element_set_si(e, a[j]);
+ poly_set_coeff(f, e, j);
+ }
+
+ // Test poly_degree().
+ for(j = 2; j >= 0 && !a[j]; j--);
+ EXPECT(poly_degree(f) == j);
+
+ // Add monic polynomials to the list.
+ if (j >= 0 && a[j] == 1) darray_append(list, f);
+ else {
+ element_clear(f);
+ pbc_free(f);
+ }
+
+ // Next!
+ d = 0;
+ for(;;) {
+ a[d]++;
+ if (a[d] >= p) {
+ a[d] = 0;
+ d++;
+ if (d > 2) goto break2;
+ } else break;
+ }
+ }
+break2: ;
+
+ // Find all composite monic polynomials of degree 3 or less.
+ darray_t prodlist;
+ darray_init(prodlist);
+
+ darray_forall4(list, (void(*)(void*,void*,void*,void*))outer, list, fx, prodlist);
+
+ // Enumerate all monic polynomials in F_p[x] up to degree 3.
+ a[0] = a[1] = a[2] = 0;
+ for(;;) {
+ element_t f;
+ element_init(f, fx);
+ int j;
+ for(j = 0; j < 3; j++) {
+ element_set_si(e, a[j]);
+ poly_set_coeff(f, e, j);
+ }
+ for(j = 2; j >= 0 && !a[j]; j--);
+ element_set1(e);
+ poly_set_coeff(f, e, j + 1);
+
+ // Check f is a unit or appears on the list of composites if and only if
+ // poly_is_irred() returns 0.
+ if (poly_is_irred(f)) {
+ EXPECT(!darray_at_test(prodlist, (int(*)(void*,void*))isf, f));
+ } else if (poly_degree(f)) {
+ EXPECT(darray_at_test(prodlist, (int(*)(void*,void*))isf, f));
+ }
+ element_clear(f);
+
+ // Next!
+ d = 0;
+ for(;;) {
+ a[d]++;
+ if (a[d] >= p) {
+ a[d] = 0;
+ d++;
+ if (d > 2) goto break3;
+ } else break;
+ }
+ }
+break3: ;
+
+ darray_forall(list, elfree);
+ darray_forall(prodlist, elfree);
+ darray_clear(prodlist);
+ darray_clear(list);
+ mpz_clear(prime);
+ field_clear(fx);
+ field_clear(fp);
+ element_clear(e);
+
+ return pbc_err_count;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/prodpairing_test.c b/moon-abe/pbc-0.5.14/guru/prodpairing_test.c
new file mode 100644
index 00000000..083f4a66
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/prodpairing_test.c
@@ -0,0 +1,44 @@
+// Check product of pairings works for F pairings when initialized via
+// pairing_init_pbc_param().
+//
+// By Michael Adjedj, Ben Lynn.
+#include "pbc.h"
+#include "pbc_test.h"
+
+int main(void) {
+ pbc_param_t param;
+
+ pbc_param_init_f_gen(param, 200);
+ pairing_t pairing;
+ pairing_init_pbc_param(pairing, param);
+
+ element_t P[2], Q[2], res, tmp, tmp2;
+
+ element_init_G1(P[0], pairing); element_random(P[0]);
+ element_init_G1(P[1], pairing); element_random(P[1]);
+
+ element_init_G2(Q[0], pairing); element_random(Q[0]);
+ element_init_G2(Q[1], pairing); element_random(Q[1]);
+
+ element_init_GT(res, pairing);
+ element_init_GT(tmp, pairing);
+ element_init_GT(tmp2, pairing);
+
+ element_prod_pairing(res, P, Q, 2);
+ element_pairing(tmp, P[0], Q[0]);
+ element_pairing(tmp2, P[1], Q[1]);
+ element_mul(tmp, tmp, tmp2);
+ EXPECT(!element_cmp(res, tmp));
+
+ element_clear(P[0]);
+ element_clear(P[1]);
+ element_clear(Q[0]);
+ element_clear(Q[1]);
+ element_clear(res);
+ element_clear(tmp);
+ element_clear(tmp2);
+
+ pairing_clear(pairing);
+ pbc_param_clear(param);
+ return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/quadratic_test.c b/moon-abe/pbc-0.5.14/guru/quadratic_test.c
new file mode 100644
index 00000000..3f78e95a
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/quadratic_test.c
@@ -0,0 +1,62 @@
+// Test quadratic field extensions.
+
+#include "pbc.h"
+#include "pbc_fp.h"
+#include "pbc_fieldquadratic.h"
+#include "pbc_test.h"
+
+int main(void) {
+ field_t fp, fp2;
+ mpz_t prime;
+ element_t a, b, c;
+
+ mpz_init(prime);
+ // Prime is 3 mod 4 so that -1 is a quadratic nonresidue.
+ // For smaller tests, try the prime 83.
+ mpz_setbit(prime, 256);
+ do {
+ mpz_nextprime(prime, prime);
+ } while (mpz_fdiv_ui(prime, 4) != 3);
+
+ field_init_fp(fp, prime);
+ field_init_fi(fp2, fp);
+ element_init(a, fp2);
+ element_init(b, fp2);
+ element_init(c, fp2);
+
+ element_printf("field: %Z^2\n", prime);
+
+ element_random(a);
+ element_random(b);
+ element_printf("a = %B, b = %B\n", a, b);
+
+ element_add(c, a, b);
+ element_printf("a + b = %B\n", c);
+
+ element_mul(c, a, b);
+ element_printf("a * b = %B\n", c);
+
+ for (;;) {
+ element_random(a);
+ element_printf("new a = %B\n", a);
+
+ if (element_is_sqr(a)) break;
+ printf(" is not a square\n");
+ }
+ element_sqrt(c, a);
+ element_printf("sqrt(a) = %B\n", c);
+ element_mul(c, c, c);
+ element_printf("sqrt(a) * sqrt(a) = %B\n", c);
+ element_invert(c, a);
+ element_printf("1/a = %B\n", c);
+ element_mul(c, c, a);
+ element_printf("1/a * a = %B\n", c);
+
+ element_clear(a);
+ element_clear(b);
+ element_clear(c);
+ field_clear(fp);
+ field_clear(fp2);
+ mpz_clear(prime);
+ return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/sing.c b/moon-abe/pbc-0.5.14/guru/sing.c
new file mode 100644
index 00000000..d29e3ff5
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/sing.c
@@ -0,0 +1,263 @@
+/*
+ * Example of a singular curve, similar to 19.c
+ * but the Tate pairing degenerates
+ *
+ * Consider the curve E: y^2 = x^3 + x^2 over F_19:
+ * E_ns(F_19) is a cyclic group of order 18.
+ */
+
+#include "pbc.h"
+#include "pbc_singular.h"
+#include "pbc_fp.h"
+
+static void miller(element_t res, element_t P, element_t Q, element_t R, int n)
+{
+ //collate divisions
+ int m;
+ element_t v, vd;
+ element_t Z;
+ element_t a, b, c;
+ element_t e0, e1;
+ mpz_t q;
+ element_ptr Zx, Zy;
+ const element_ptr Px = curve_x_coord(P);
+ const element_ptr Py = curve_y_coord(P);
+ const element_ptr numx = curve_x_coord(Q);
+ const element_ptr numy = curve_y_coord(Q);
+ const element_ptr denomx = curve_x_coord(R);
+ const element_ptr denomy = curve_y_coord(R);
+
+ void do_vertical(element_t e, element_t edenom)
+ {
+ element_sub(e0, numx, Zx);
+ element_mul(e, e, e0);
+
+ element_sub(e0, denomx, Zx);
+ element_mul(edenom, edenom, e0);
+ }
+
+ void do_tangent(element_t e, element_t edenom)
+ {
+ //a = -slope_tangent(A.x, A.y);
+ //b = 1;
+ //c = -(A.y + a * A.x);
+ //but we multiply by 2*A.y to avoid division
+
+ //a = -Ax * (Ax + Ax + Ax + twicea_2) - a_4;
+ //This curve is special:
+ //a = -(3 Ax^2 + 2Ax)
+ //b = 2 * Ay
+ //c = -(2 Ay^2 + a Ax);
+
+ if (element_is0(Zy)) {
+ do_vertical(e, edenom);
+ return;
+ }
+ element_square(a, Zx);
+ element_mul_si(a, a, 3);
+ element_add(a, a, Zx);
+ element_add(a, a, Zx);
+ element_neg(a, a);
+
+ element_add(b, Zy, Zy);
+
+ element_mul(e0, b, Zy);
+ element_mul(c, a, Zx);
+ element_add(c, c, e0);
+ element_neg(c, c);
+
+ element_mul(e0, a, numx);
+ element_mul(e1, b, numy);
+ element_add(e0, e0, e1);
+ element_add(e0, e0, c);
+ element_mul(e, e, e0);
+
+ element_mul(e0, a, denomx);
+ element_mul(e1, b, denomy);
+ element_add(e0, e0, e1);
+ element_add(e0, e0, c);
+ element_mul(edenom, edenom, e0);
+ }
+
+ void do_line(element_ptr e, element_ptr edenom)
+ {
+ if (!element_cmp(Zx, Px)) {
+ if (!element_cmp(Zy, Py)) {
+ do_tangent(e, edenom);
+ } else {
+ do_vertical(e, edenom);
+ }
+ return;
+ }
+
+ element_sub(b, Px, Zx);
+ element_sub(a, Zy, Py);
+ element_mul(c, Zx, Py);
+ element_mul(e0, Zy, Px);
+ element_sub(c, c, e0);
+
+ element_mul(e0, a, numx);
+ element_mul(e1, b, numy);
+ element_add(e0, e0, e1);
+ element_add(e0, e0, c);
+ element_mul(e, e, e0);
+
+ element_mul(e0, a, denomx);
+ element_mul(e1, b, denomy);
+ element_add(e0, e0, e1);
+ element_add(e0, e0, c);
+ element_mul(edenom, edenom, e0);
+ }
+
+ element_init(a, res->field);
+ element_init(b, res->field);
+ element_init(c, res->field);
+ element_init(e0, res->field);
+ element_init(e1, res->field);
+
+ element_init(v, res->field);
+ element_init(vd, res->field);
+ element_init(Z, P->field);
+
+ element_set(Z, P);
+ Zx = curve_x_coord(Z);
+ Zy = curve_y_coord(Z);
+
+ element_set1(v);
+ element_set1(vd);
+
+ mpz_init(q);
+ mpz_set_ui(q, n);
+ m = mpz_sizeinbase(q, 2) - 2;
+
+ while(m >= 0) {
+ element_square(v, v);
+ element_square(vd, vd);
+ do_tangent(v, vd);
+ element_double(Z, Z);
+ do_vertical(vd, v);
+
+ if (mpz_tstbit(q, m)) {
+ do_line(v, vd);
+ element_add(Z, Z, P);
+ if (m) {
+ do_vertical(vd, v);
+ }
+ }
+ m--;
+ }
+
+ mpz_clear(q);
+
+ element_invert(vd, vd);
+ element_mul(res, v, vd);
+
+ element_clear(v);
+ element_clear(vd);
+ element_clear(Z);
+ element_clear(a);
+ element_clear(b);
+ element_clear(c);
+ element_clear(e0);
+ element_clear(e1);
+}
+
+static void tate_3(element_ptr out, element_ptr P, element_ptr Q, element_ptr R)
+{
+ mpz_t six;
+
+ mpz_init(six);
+ mpz_set_ui(six, 6);
+ element_t QR;
+ element_t e0;
+
+ element_init(QR, P->field);
+ element_init(e0, out->field);
+
+ element_add(QR, Q, R);
+
+ //for subgroup size 3, -2P = P, hence
+ //the tangent line at P has divisor 3(P) - 3(O)
+
+ miller(out, P, QR, R, 3);
+
+ element_pow_mpz(out, out, six);
+ element_clear(QR);
+ element_clear(e0);
+ mpz_clear(six);
+}
+
+static void tate_9(element_ptr out, element_ptr P, element_ptr Q, element_ptr R)
+{
+ element_t QR;
+ element_init(QR, P->field);
+
+ element_add(QR, Q, R);
+
+ miller(out, P, QR, R, 9);
+
+ element_square(out, out);
+
+ element_clear(QR);
+}
+
+int main(void)
+{
+ field_t c;
+ field_t Z19;
+ element_t P, Q, R;
+ mpz_t q, z;
+ element_t a;
+ int i;
+
+ mpz_init(q);
+ mpz_init(z);
+
+ mpz_set_ui(q, 19);
+
+ field_init_fp(Z19, q);
+ element_init(a, Z19);
+
+ field_init_curve_singular_with_node(c, Z19);
+
+ element_init(P, c);
+ element_init(Q, c);
+ element_init(R, c);
+
+ //(3,+/-6) is a generator
+ //we have an isomorphism from E_ns to F_19^*
+ // (3,6) --> 3
+ //(generally (x,y) --> (y+x)/(y-x)
+
+ curve_set_si(R, 3, 6);
+
+ for (i=1; i<=18; i++) {
+ mpz_set_si(z, i);
+ element_mul_mpz(Q, R, z);
+ element_printf("%dR = %B\n", i, Q);
+ }
+
+ mpz_set_ui(z, 6);
+ element_mul_mpz(P, R, z);
+ //P has order 3
+ element_printf("P = %B\n", P);
+
+ for (i=1; i<=3; i++) {
+ mpz_set_si(z, i);
+ element_mul_mpz(Q, R, z);
+ tate_3(a, P, Q, R);
+ element_printf("e_3(P,%dP) = %B\n", i, a);
+ }
+
+ element_double(P, R);
+ //P has order 9
+ element_printf("P = %B\n", P);
+ for (i=1; i<=9; i++) {
+ mpz_set_si(z, i);
+ element_mul_mpz(Q, P, z);
+ tate_9(a, P, Q, R);
+ element_printf("e_9(P,%dP) = %B\n", i, a);
+ }
+
+ return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/ternary_extension_field_test.c b/moon-abe/pbc-0.5.14/guru/ternary_extension_field_test.c
new file mode 100644
index 00000000..b431e4fa
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/ternary_extension_field_test.c
@@ -0,0 +1,240 @@
+/* test ternary extension fields $GF(3^m)$, $GF(3^{2*m})$, $GF(3^{3*m})$ and $GF(3^{6*m})$
+ Outputing nothing if everything is good. */
+
+#include "pbc.h"
+#include "pbc_ternary_extension_field.h"
+#include "pbc_test.h"
+#include <string.h>
+#include <stdio.h>
+
+typedef struct {
+ unsigned int len;
+ unsigned int m;
+ unsigned int t;
+ element_ptr p;
+} params;
+
+#define data(x) ((unsigned long*)x->data)
+#define params(x) ((params *)x->field->data)
+#define print(e) {printf(#e": "); element_out_str(stdout, 0, e); printf("\n");}
+
+static field_t f97, f97_2, f97_3, f97_6;
+static element_t e0, e1, e2, a, b, a2, b2, a3, b3, a6, b6;
+static unsigned char *data;
+
+static void test_gf3m_param(void) {
+ params *pa = (params *) f97->data;
+ element_to_bytes(data, pa->p);
+ unsigned i;
+ unsigned char w;
+ for (i = 0; i < pa->len * 2 * sizeof(unsigned long); i++) {
+ switch (i) {
+ case 1:
+ w = 1;
+ break; // 2
+ case 2:
+ w = 16;
+ break; // x^12
+ case 24:
+ w = 2;
+ break; // x^97
+ default:
+ w = 0;
+ }
+ EXPECT(data[i] == w);
+ }
+}
+
+static void test_gf3m_to_bytes(void) {
+ element_random(a);
+ element_to_bytes(data, a);
+ element_from_bytes(b, data);
+ EXPECT(0 == element_cmp(a, b));
+}
+
+static void test_gf3m_add(void) {
+ element_random(a);
+ element_add(b, a, a);
+ element_add(b, b, b);
+ element_sub(b, b, a);
+ element_sub(b, b, a);
+ element_sub(b, b, a);
+ EXPECT(!element_cmp(a, b));
+
+ element_add(b, params(a)->p, a);
+ element_sub(b, b, params(a)->p);
+ EXPECT(!element_cmp(a, b));
+}
+
+static void test_gf3m_neg(void) {
+ element_random(a);
+ element_neg(b, a);
+ element_add(b, a, b);
+ EXPECT(!element_cmp(b, e0));
+}
+
+static void test_gf3m_mult(void) {
+ element_random(a);
+ element_mul(a, a, e0);
+ EXPECT(!element_cmp(a, e0));
+
+ element_random(a);
+ element_mul(b, a, e1);
+ EXPECT(!element_cmp(a, b));
+
+ element_random(a);
+ element_mul(b, a, e2);
+ element_add(a, a, b);
+ EXPECT(!element_cmp(a, e0));
+}
+
+static void test_gf3m_cubic(void) {
+ element_random(a);
+ element_mul(b, a, a);
+ element_mul(b, a, b);
+ element_cubic(a, a);
+ EXPECT(!element_cmp(a, b));
+}
+
+static void test_gf3m_cubic2(void) {
+ unsigned long x[] = {1153286547535200267ul, 6715371622ul, 4990694927524257316ul, 210763913ul};
+ unsigned long y[] = {8145587063258678275ul, 6451025920ul, 9976895054123379152ul, 1275593166ul};
+ memcpy(a->data, x, sizeof(x));
+ memcpy(b->data, y, sizeof(y));
+ element_cubic(a, a);
+ EXPECT(!element_cmp(a, b));
+}
+
+static void test_gf3m_inverse(void) {
+ element_set1(a);
+ element_invert(b, a);
+ EXPECT(!element_cmp(b, e1));
+
+ element_set(a, e2);
+ element_invert(b, a);
+ EXPECT(!element_cmp(b, e2));
+
+ element_random(a);
+ element_invert(b, a);
+ element_mul(a, a, b);
+ EXPECT(!element_cmp(a, e1));
+}
+
+static void test_gf3m_sqrt(void) {
+ mpz_t t;
+ mpz_init(t);
+ mpz_sub_ui(t, a->field->order, 1); // t == field_order - 1
+ element_random(a);
+ element_pow_mpz(a, a, t);
+ EXPECT(!element_cmp(a, e1));
+
+ while(1){
+ element_random(a);
+ element_mul(b, a, a);
+ element_sqrt(b, b);
+ if(element_cmp(a, b)) {// a != b
+ element_neg(b, b);
+ if(!element_cmp(a, b)) break;
+ }
+ }
+ mpz_clear(t);
+}
+
+static void test_gf32m_cubic(void) {
+ element_random(a2);
+ element_mul(b2, a2, a2);
+ element_mul(b2, b2, a2);
+ element_cubic(a2, a2);
+ EXPECT(!element_cmp(a2, b2));
+}
+
+static void test_gf33m_cubic(void) {
+ element_random(a3);
+ element_mul(b3, a3, a3);
+ element_mul(b3, b3, a3);
+ element_cubic(a3, a3);
+ EXPECT(!element_cmp(a3, b3));
+}
+
+static void test_gf33m_inverse(void) {
+ element_random(a3);
+ element_invert(b3, a3);
+ element_mul(a3, a3, b3);
+ element_ptr a0 = element_item(a3, 0);
+ EXPECT(!element_cmp(a0, e1));
+}
+
+static void test_gf36m_cubic(void) {
+ element_random(a6);
+ element_mul(b6, a6, a6);
+ element_mul(b6, b6, a6);
+ element_cubic(a6, a6);
+ EXPECT(!element_cmp(a6, b6));
+}
+
+void setup(void) {
+ field_init_gf3m(f97, 97, 12);
+ element_init(a, f97);
+ element_init(b, f97);
+ element_init(e0, f97);
+ element_init(e1, f97);
+ element_init(e2, f97);
+ element_set1(e1);
+ element_neg(e2, e1);
+
+ field_init_gf32m(f97_2, f97);
+ element_init(a2, f97_2);
+ element_init(b2, f97_2);
+
+ field_init_gf33m(f97_3, f97);
+ element_init(a3, f97_3);
+ element_init(b3, f97_3);
+
+ field_init_gf33m(f97_6, f97_2);
+ element_init(a6, f97_6);
+ element_init(b6, f97_6);
+
+ data = pbc_malloc(f97->fixed_length_in_bytes);
+}
+
+void tear_down(void) {
+ pbc_free(data);
+
+ element_clear(e0);
+ element_clear(e1);
+ element_clear(e2);
+ element_clear(a);
+ element_clear(b);
+ element_clear(a2);
+ element_clear(b2);
+ element_clear(a3);
+ element_clear(b3);
+ element_clear(a6);
+ element_clear(b6);
+
+ field_clear(f97_6);
+ field_clear(f97_3);
+ field_clear(f97_2);
+ field_clear(f97);
+}
+
+int main(void) {
+ setup();
+
+ test_gf3m_param();
+ test_gf3m_to_bytes();
+ test_gf3m_add();
+ test_gf3m_neg();
+ test_gf3m_mult();
+ test_gf3m_cubic();
+ test_gf3m_cubic2();
+ test_gf3m_inverse();
+ test_gf3m_sqrt();
+ test_gf32m_cubic();
+ test_gf33m_cubic();
+ test_gf33m_inverse();
+ test_gf36m_cubic();
+
+ tear_down();
+ return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/testindexcalculus.c b/moon-abe/pbc-0.5.14/guru/testindexcalculus.c
new file mode 100644
index 00000000..1bb36146
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/testindexcalculus.c
@@ -0,0 +1,29 @@
+#include <stdio.h>
+#include <gmp.h>
+#include "pbc.h"
+
+int main(int argc, char **argv)
+{
+ mpz_t x;
+ mpz_t g, h, q;
+ mpz_init(x);
+ mpz_init(g);
+ mpz_init(h);
+ mpz_init(q);
+ int bits = 40;
+
+ if (argc == 2) {
+ bits = atoi(argv[1]);
+ }
+ mpz_setbit(q, bits);
+ pbc_mpz_random(q, q);
+ mpz_nextprime(q, q);
+ pbc_mpz_random(g, q);
+ pbc_mpz_random(h, q);
+ mpz_powm(h, g, h, q);
+
+ element_dlog_index_calculus(x, g, h, q);
+ element_printf("%Zd^%Zd %% %Zd = %Zd\n", g, x, q, h);
+
+ return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/guru/timefp.c b/moon-abe/pbc-0.5.14/guru/timefp.c
new file mode 100644
index 00000000..6e308f9a
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/guru/timefp.c
@@ -0,0 +1,98 @@
+#include "pbc.h"
+#include "pbc_fp.h"
+#include "pbc_test.h"
+
+static void timefield(field_t fp) {
+ int i, n;
+ double t0, t1;
+
+ element_t x, y, z;
+ element_init(x, fp);
+ element_init(y, fp);
+ element_init(z, fp);
+
+ element_random(x);
+ element_random(y);
+
+ n = 20000;
+ t0 = pbc_get_time();
+ for (i=0; i<n; i++) {
+ element_mul(z, x, y);
+ element_mul(x, y, z);
+ element_mul(y, z, x);
+ }
+ t1 = pbc_get_time();
+ printf("mul %fs\n", t1 - t0);
+
+ n = 20000;
+ t0 = pbc_get_time();
+ for (i=0; i<n; i++) {
+ element_square(x, x);
+ }
+ t1 = pbc_get_time();
+ printf("square %fs\n", t1 - t0);
+
+ n = 1000;
+ t0 = pbc_get_time();
+ for (i=0; i<n; i++) {
+ element_invert(z, x);
+ element_invert(z, y);
+ }
+ t1 = pbc_get_time();
+ printf("invert %fs\n", t1 - t0);
+
+ n = 40000;
+ t0 = pbc_get_time();
+ for (i=0; i<n; i++) {
+ element_set0(z);
+ }
+ t1 = pbc_get_time();
+ printf("set0 %fs\n", t1 - t0);
+
+ n = 40000;
+ t0 = pbc_get_time();
+ for (i=0; i<n; i++) {
+ element_set(z, x);
+ element_set(z, y);
+ }
+ t1 = pbc_get_time();
+ printf("set %fs\n", t1 - t0);
+
+ n = 400;
+ t0 = pbc_get_time();
+ for (i=0; i<n; i++) {
+ element_pow_zn(x, y, z);
+ }
+ t1 = pbc_get_time();
+ printf("pow_zn %fs\n", t1 - t0);
+
+ element_clear(x);
+ element_clear(y);
+ element_clear(z);
+}
+
+int main(int argc, char **argv) {
+ field_t f1, f2;
+ mpz_t prime;
+
+ mpz_init(prime);
+ if (argc > 1) {
+ mpz_setbit(prime, atoi(argv[1]));
+ } else {
+ mpz_setbit(prime, 201);
+ }
+ mpz_setbit(prime, 70);
+ mpz_nextprime(prime, prime);
+ field_init_mont_fp(f1, prime);
+ field_init_faster_fp(f2, prime);
+
+ printf("montfp.c\n");
+ timefield(f1);
+ printf("fasterfp.c\n");
+ timefield(f2);
+
+ mpz_clear(prime);
+ field_clear(f1);
+ field_clear(f2);
+ return 0;
+}