diff options
Diffstat (limited to 'moon-abe/pbc-0.5.14/guru')
28 files changed, 4938 insertions, 0 deletions
diff --git a/moon-abe/pbc-0.5.14/guru/.dirstamp b/moon-abe/pbc-0.5.14/guru/.dirstamp new file mode 100644 index 00000000..e69de29b --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/.dirstamp diff --git a/moon-abe/pbc-0.5.14/guru/.libs/eta_T_3_test b/moon-abe/pbc-0.5.14/guru/.libs/eta_T_3_test Binary files differnew file mode 100755 index 00000000..f3967613 --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/.libs/eta_T_3_test diff --git a/moon-abe/pbc-0.5.14/guru/.libs/fp_test b/moon-abe/pbc-0.5.14/guru/.libs/fp_test Binary files differnew file mode 100755 index 00000000..d66792ff --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/.libs/fp_test diff --git a/moon-abe/pbc-0.5.14/guru/.libs/poly_test b/moon-abe/pbc-0.5.14/guru/.libs/poly_test Binary files differnew file mode 100755 index 00000000..2d56cb53 --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/.libs/poly_test diff --git a/moon-abe/pbc-0.5.14/guru/.libs/prodpairing_test b/moon-abe/pbc-0.5.14/guru/.libs/prodpairing_test Binary files differnew file mode 100755 index 00000000..a50ee043 --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/.libs/prodpairing_test diff --git a/moon-abe/pbc-0.5.14/guru/.libs/quadratic_test b/moon-abe/pbc-0.5.14/guru/.libs/quadratic_test Binary files differnew file mode 100755 index 00000000..b16a3801 --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/.libs/quadratic_test diff --git a/moon-abe/pbc-0.5.14/guru/.libs/ternary_extension_field_test b/moon-abe/pbc-0.5.14/guru/.libs/ternary_extension_field_test Binary files differnew file mode 100755 index 00000000..39dc22a7 --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/.libs/ternary_extension_field_test 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 b/moon-abe/pbc-0.5.14/guru/eta_T_3_test new file mode 100755 index 00000000..537a6039 --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/eta_T_3_test @@ -0,0 +1,228 @@ +#! /bin/sh + +# guru/eta_T_3_test - temporary wrapper script for .libs/eta_T_3_test +# Generated by libtool (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1 +# +# The guru/eta_T_3_test program cannot be directly executed until all the libtool +# libraries that it depends on are installed. +# +# This wrapper script should never be moved out of the build directory. +# If it is, it will not operate correctly. + +# Sed substitution that helps us do robust quoting. It backslashifies +# metacharacters that are still active within double-quoted strings. +sed_quote_subst='s/\([`"$\\]\)/\\\1/g' + +# Be Bourne compatible +if test -n "${ZSH_VERSION+set}" && (emulate sh) >/dev/null 2>&1; then + emulate sh + NULLCMD=: + # Zsh 3.x and 4.x performs word splitting on ${1+"$@"}, which + # is contrary to our usage. Disable this feature. + alias -g '${1+"$@"}'='"$@"' + setopt NO_GLOB_SUBST +else + case `(set -o) 2>/dev/null` in *posix*) set -o posix;; esac +fi +BIN_SH=xpg4; export BIN_SH # for Tru64 +DUALCASE=1; export DUALCASE # for MKS sh + +# The HP-UX ksh and POSIX shell print the target directory to stdout +# if CDPATH is set. +(unset CDPATH) >/dev/null 2>&1 && unset CDPATH + +relink_command="(cd /home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14; { test -z \"\${LIBRARY_PATH+set}\" || unset LIBRARY_PATH || { LIBRARY_PATH=; export LIBRARY_PATH; }; }; { test -z \"\${COMPILER_PATH+set}\" || unset COMPILER_PATH || { COMPILER_PATH=; export COMPILER_PATH; }; }; { test -z \"\${GCC_EXEC_PREFIX+set}\" || unset GCC_EXEC_PREFIX || { GCC_EXEC_PREFIX=; export GCC_EXEC_PREFIX; }; }; { test -z \"\${LD_RUN_PATH+set}\" || unset LD_RUN_PATH || { LD_RUN_PATH=; export LD_RUN_PATH; }; }; { test -z \"\${LD_LIBRARY_PATH+set}\" || unset LD_LIBRARY_PATH || { LD_LIBRARY_PATH=; export LD_LIBRARY_PATH; }; }; PATH=/sbin:/usr/sbin:/usr/bin:/bin:/usr/local/sbin:/usr/local/bin; export PATH; gcc -Wall -W -Wfloat-equal -Wpointer-arith -Wcast-align -Wstrict-prototypes -Wredundant-decls -Wendif-labels -Wshadow -pipe -ffast-math -U__STRICT_ANSI__ -std=gnu99 -fomit-frame-pointer -O3 -o \$progdir/\$file guru_eta_T_3_test-eta_T_3_test.o ./.libs/libpbc.so -lgmp -lm -Wl,-rpath -Wl,/home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14/.libs)" + +# This environment variable determines our operation mode. +if test "$libtool_install_magic" = "%%%MAGIC variable%%%"; then + # install mode needs the following variables: + generated_by_libtool_version='2.4.2' + notinst_deplibs=' libpbc.la' +else + # When we are sourced in execute mode, $file and $ECHO are already set. + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + file="$0" + +# A function that is used when there is no print builtin or printf. +func_fallback_echo () +{ + eval 'cat <<_LTECHO_EOF +$1 +_LTECHO_EOF' +} + ECHO="printf %s\\n" + fi + +# Very basic option parsing. These options are (a) specific to +# the libtool wrapper, (b) are identical between the wrapper +# /script/ and the wrapper /executable/ which is used only on +# windows platforms, and (c) all begin with the string --lt- +# (application programs are unlikely to have options which match +# this pattern). +# +# There are only two supported options: --lt-debug and +# --lt-dump-script. There is, deliberately, no --lt-help. +# +# The first argument to this parsing function should be the +# script's ./libtool value, followed by no. +lt_option_debug= +func_parse_lt_options () +{ + lt_script_arg0=$0 + shift + for lt_opt + do + case "$lt_opt" in + --lt-debug) lt_option_debug=1 ;; + --lt-dump-script) + lt_dump_D=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%/[^/]*$%%'` + test "X$lt_dump_D" = "X$lt_script_arg0" && lt_dump_D=. + lt_dump_F=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%^.*/%%'` + cat "$lt_dump_D/$lt_dump_F" + exit 0 + ;; + --lt-*) + $ECHO "Unrecognized --lt- option: '$lt_opt'" 1>&2 + exit 1 + ;; + esac + done + + # Print the debug banner immediately: + if test -n "$lt_option_debug"; then + echo "eta_T_3_test:guru/eta_T_3_test:${LINENO}: libtool wrapper (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1" 1>&2 + fi +} + +# Used when --lt-debug. Prints its arguments to stdout +# (redirection is the responsibility of the caller) +func_lt_dump_args () +{ + lt_dump_args_N=1; + for lt_arg + do + $ECHO "eta_T_3_test:guru/eta_T_3_test:${LINENO}: newargv[$lt_dump_args_N]: $lt_arg" + lt_dump_args_N=`expr $lt_dump_args_N + 1` + done +} + +# Core function for launching the target application +func_exec_program_core () +{ + + if test -n "$lt_option_debug"; then + $ECHO "eta_T_3_test:guru/eta_T_3_test:${LINENO}: newargv[0]: $progdir/$program" 1>&2 + func_lt_dump_args ${1+"$@"} 1>&2 + fi + exec "$progdir/$program" ${1+"$@"} + + $ECHO "$0: cannot exec $program $*" 1>&2 + exit 1 +} + +# A function to encapsulate launching the target application +# Strips options in the --lt-* namespace from $@ and +# launches target application with the remaining arguments. +func_exec_program () +{ + case " $* " in + *\ --lt-*) + for lt_wr_arg + do + case $lt_wr_arg in + --lt-*) ;; + *) set x "$@" "$lt_wr_arg"; shift;; + esac + shift + done ;; + esac + func_exec_program_core ${1+"$@"} +} + + # Parse options + func_parse_lt_options "$0" ${1+"$@"} + + # Find the directory that this script lives in. + thisdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + test "x$thisdir" = "x$file" && thisdir=. + + # Follow symbolic links until we get to the real thisdir. + file=`ls -ld "$file" | /bin/sed -n 's/.*-> //p'` + while test -n "$file"; do + destdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + + # If there was a directory component, then change thisdir. + if test "x$destdir" != "x$file"; then + case "$destdir" in + [\\/]* | [A-Za-z]:[\\/]*) thisdir="$destdir" ;; + *) thisdir="$thisdir/$destdir" ;; + esac + fi + + file=`$ECHO "$file" | /bin/sed 's%^.*/%%'` + file=`ls -ld "$thisdir/$file" | /bin/sed -n 's/.*-> //p'` + done + + # Usually 'no', except on cygwin/mingw when embedded into + # the cwrapper. + WRAPPER_SCRIPT_BELONGS_IN_OBJDIR=no + if test "$WRAPPER_SCRIPT_BELONGS_IN_OBJDIR" = "yes"; then + # special case for '.' + if test "$thisdir" = "."; then + thisdir=`pwd` + fi + # remove .libs from thisdir + case "$thisdir" in + *[\\/].libs ) thisdir=`$ECHO "$thisdir" | /bin/sed 's%[\\/][^\\/]*$%%'` ;; + .libs ) thisdir=. ;; + esac + fi + + # Try to get the absolute directory name. + absdir=`cd "$thisdir" && pwd` + test -n "$absdir" && thisdir="$absdir" + + program=lt-'eta_T_3_test' + progdir="$thisdir/.libs" + + if test ! -f "$progdir/$program" || + { file=`ls -1dt "$progdir/$program" "$progdir/../$program" 2>/dev/null | /bin/sed 1q`; \ + test "X$file" != "X$progdir/$program"; }; then + + file="$$-$program" + + if test ! -d "$progdir"; then + mkdir "$progdir" + else + rm -f "$progdir/$file" + fi + + # relink executable if necessary + if test -n "$relink_command"; then + if relink_command_output=`eval $relink_command 2>&1`; then : + else + printf %s\n "$relink_command_output" >&2 + rm -f "$progdir/$file" + exit 1 + fi + fi + + mv -f "$progdir/$file" "$progdir/$program" 2>/dev/null || + { rm -f "$progdir/$program"; + mv -f "$progdir/$file" "$progdir/$program"; } + rm -f "$progdir/$file" + fi + + if test -f "$progdir/$program"; then + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + # Run the actual program with our arguments. + func_exec_program ${1+"$@"} + fi + else + # The program doesn't exist. + $ECHO "$0: error: \`$progdir/$program' does not exist" 1>&2 + $ECHO "This script is just a wrapper for $program." 1>&2 + $ECHO "See the libtool documentation for more information." 1>&2 + exit 1 + fi +fi 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 b/moon-abe/pbc-0.5.14/guru/fp_test new file mode 100755 index 00000000..786ffa5b --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/fp_test @@ -0,0 +1,228 @@ +#! /bin/sh + +# guru/fp_test - temporary wrapper script for .libs/fp_test +# Generated by libtool (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1 +# +# The guru/fp_test program cannot be directly executed until all the libtool +# libraries that it depends on are installed. +# +# This wrapper script should never be moved out of the build directory. +# If it is, it will not operate correctly. + +# Sed substitution that helps us do robust quoting. It backslashifies +# metacharacters that are still active within double-quoted strings. +sed_quote_subst='s/\([`"$\\]\)/\\\1/g' + +# Be Bourne compatible +if test -n "${ZSH_VERSION+set}" && (emulate sh) >/dev/null 2>&1; then + emulate sh + NULLCMD=: + # Zsh 3.x and 4.x performs word splitting on ${1+"$@"}, which + # is contrary to our usage. Disable this feature. + alias -g '${1+"$@"}'='"$@"' + setopt NO_GLOB_SUBST +else + case `(set -o) 2>/dev/null` in *posix*) set -o posix;; esac +fi +BIN_SH=xpg4; export BIN_SH # for Tru64 +DUALCASE=1; export DUALCASE # for MKS sh + +# The HP-UX ksh and POSIX shell print the target directory to stdout +# if CDPATH is set. +(unset CDPATH) >/dev/null 2>&1 && unset CDPATH + +relink_command="(cd /home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14; { test -z \"\${LIBRARY_PATH+set}\" || unset LIBRARY_PATH || { LIBRARY_PATH=; export LIBRARY_PATH; }; }; { test -z \"\${COMPILER_PATH+set}\" || unset COMPILER_PATH || { COMPILER_PATH=; export COMPILER_PATH; }; }; { test -z \"\${GCC_EXEC_PREFIX+set}\" || unset GCC_EXEC_PREFIX || { GCC_EXEC_PREFIX=; export GCC_EXEC_PREFIX; }; }; { test -z \"\${LD_RUN_PATH+set}\" || unset LD_RUN_PATH || { LD_RUN_PATH=; export LD_RUN_PATH; }; }; { test -z \"\${LD_LIBRARY_PATH+set}\" || unset LD_LIBRARY_PATH || { LD_LIBRARY_PATH=; export LD_LIBRARY_PATH; }; }; PATH=/sbin:/usr/sbin:/usr/bin:/bin:/usr/local/sbin:/usr/local/bin; export PATH; gcc -Wall -W -Wfloat-equal -Wpointer-arith -Wcast-align -Wstrict-prototypes -Wredundant-decls -Wendif-labels -Wshadow -pipe -ffast-math -U__STRICT_ANSI__ -std=gnu99 -fomit-frame-pointer -O3 -o \$progdir/\$file guru_fp_test-fp_test.o ./.libs/libpbc.so -lgmp -lm -Wl,-rpath -Wl,/home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14/.libs)" + +# This environment variable determines our operation mode. +if test "$libtool_install_magic" = "%%%MAGIC variable%%%"; then + # install mode needs the following variables: + generated_by_libtool_version='2.4.2' + notinst_deplibs=' libpbc.la' +else + # When we are sourced in execute mode, $file and $ECHO are already set. + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + file="$0" + +# A function that is used when there is no print builtin or printf. +func_fallback_echo () +{ + eval 'cat <<_LTECHO_EOF +$1 +_LTECHO_EOF' +} + ECHO="printf %s\\n" + fi + +# Very basic option parsing. These options are (a) specific to +# the libtool wrapper, (b) are identical between the wrapper +# /script/ and the wrapper /executable/ which is used only on +# windows platforms, and (c) all begin with the string --lt- +# (application programs are unlikely to have options which match +# this pattern). +# +# There are only two supported options: --lt-debug and +# --lt-dump-script. There is, deliberately, no --lt-help. +# +# The first argument to this parsing function should be the +# script's ./libtool value, followed by no. +lt_option_debug= +func_parse_lt_options () +{ + lt_script_arg0=$0 + shift + for lt_opt + do + case "$lt_opt" in + --lt-debug) lt_option_debug=1 ;; + --lt-dump-script) + lt_dump_D=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%/[^/]*$%%'` + test "X$lt_dump_D" = "X$lt_script_arg0" && lt_dump_D=. + lt_dump_F=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%^.*/%%'` + cat "$lt_dump_D/$lt_dump_F" + exit 0 + ;; + --lt-*) + $ECHO "Unrecognized --lt- option: '$lt_opt'" 1>&2 + exit 1 + ;; + esac + done + + # Print the debug banner immediately: + if test -n "$lt_option_debug"; then + echo "fp_test:guru/fp_test:${LINENO}: libtool wrapper (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1" 1>&2 + fi +} + +# Used when --lt-debug. Prints its arguments to stdout +# (redirection is the responsibility of the caller) +func_lt_dump_args () +{ + lt_dump_args_N=1; + for lt_arg + do + $ECHO "fp_test:guru/fp_test:${LINENO}: newargv[$lt_dump_args_N]: $lt_arg" + lt_dump_args_N=`expr $lt_dump_args_N + 1` + done +} + +# Core function for launching the target application +func_exec_program_core () +{ + + if test -n "$lt_option_debug"; then + $ECHO "fp_test:guru/fp_test:${LINENO}: newargv[0]: $progdir/$program" 1>&2 + func_lt_dump_args ${1+"$@"} 1>&2 + fi + exec "$progdir/$program" ${1+"$@"} + + $ECHO "$0: cannot exec $program $*" 1>&2 + exit 1 +} + +# A function to encapsulate launching the target application +# Strips options in the --lt-* namespace from $@ and +# launches target application with the remaining arguments. +func_exec_program () +{ + case " $* " in + *\ --lt-*) + for lt_wr_arg + do + case $lt_wr_arg in + --lt-*) ;; + *) set x "$@" "$lt_wr_arg"; shift;; + esac + shift + done ;; + esac + func_exec_program_core ${1+"$@"} +} + + # Parse options + func_parse_lt_options "$0" ${1+"$@"} + + # Find the directory that this script lives in. + thisdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + test "x$thisdir" = "x$file" && thisdir=. + + # Follow symbolic links until we get to the real thisdir. + file=`ls -ld "$file" | /bin/sed -n 's/.*-> //p'` + while test -n "$file"; do + destdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + + # If there was a directory component, then change thisdir. + if test "x$destdir" != "x$file"; then + case "$destdir" in + [\\/]* | [A-Za-z]:[\\/]*) thisdir="$destdir" ;; + *) thisdir="$thisdir/$destdir" ;; + esac + fi + + file=`$ECHO "$file" | /bin/sed 's%^.*/%%'` + file=`ls -ld "$thisdir/$file" | /bin/sed -n 's/.*-> //p'` + done + + # Usually 'no', except on cygwin/mingw when embedded into + # the cwrapper. + WRAPPER_SCRIPT_BELONGS_IN_OBJDIR=no + if test "$WRAPPER_SCRIPT_BELONGS_IN_OBJDIR" = "yes"; then + # special case for '.' + if test "$thisdir" = "."; then + thisdir=`pwd` + fi + # remove .libs from thisdir + case "$thisdir" in + *[\\/].libs ) thisdir=`$ECHO "$thisdir" | /bin/sed 's%[\\/][^\\/]*$%%'` ;; + .libs ) thisdir=. ;; + esac + fi + + # Try to get the absolute directory name. + absdir=`cd "$thisdir" && pwd` + test -n "$absdir" && thisdir="$absdir" + + program=lt-'fp_test' + progdir="$thisdir/.libs" + + if test ! -f "$progdir/$program" || + { file=`ls -1dt "$progdir/$program" "$progdir/../$program" 2>/dev/null | /bin/sed 1q`; \ + test "X$file" != "X$progdir/$program"; }; then + + file="$$-$program" + + if test ! -d "$progdir"; then + mkdir "$progdir" + else + rm -f "$progdir/$file" + fi + + # relink executable if necessary + if test -n "$relink_command"; then + if relink_command_output=`eval $relink_command 2>&1`; then : + else + printf %s\n "$relink_command_output" >&2 + rm -f "$progdir/$file" + exit 1 + fi + fi + + mv -f "$progdir/$file" "$progdir/$program" 2>/dev/null || + { rm -f "$progdir/$program"; + mv -f "$progdir/$file" "$progdir/$program"; } + rm -f "$progdir/$file" + fi + + if test -f "$progdir/$program"; then + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + # Run the actual program with our arguments. + func_exec_program ${1+"$@"} + fi + else + # The program doesn't exist. + $ECHO "$0: error: \`$progdir/$program' does not exist" 1>&2 + $ECHO "This script is just a wrapper for $program." 1>&2 + $ECHO "See the libtool documentation for more information." 1>&2 + exit 1 + fi +fi 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 b/moon-abe/pbc-0.5.14/guru/poly_test new file mode 100755 index 00000000..ac4ee6ee --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/poly_test @@ -0,0 +1,228 @@ +#! /bin/sh + +# guru/poly_test - temporary wrapper script for .libs/poly_test +# Generated by libtool (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1 +# +# The guru/poly_test program cannot be directly executed until all the libtool +# libraries that it depends on are installed. +# +# This wrapper script should never be moved out of the build directory. +# If it is, it will not operate correctly. + +# Sed substitution that helps us do robust quoting. It backslashifies +# metacharacters that are still active within double-quoted strings. +sed_quote_subst='s/\([`"$\\]\)/\\\1/g' + +# Be Bourne compatible +if test -n "${ZSH_VERSION+set}" && (emulate sh) >/dev/null 2>&1; then + emulate sh + NULLCMD=: + # Zsh 3.x and 4.x performs word splitting on ${1+"$@"}, which + # is contrary to our usage. Disable this feature. + alias -g '${1+"$@"}'='"$@"' + setopt NO_GLOB_SUBST +else + case `(set -o) 2>/dev/null` in *posix*) set -o posix;; esac +fi +BIN_SH=xpg4; export BIN_SH # for Tru64 +DUALCASE=1; export DUALCASE # for MKS sh + +# The HP-UX ksh and POSIX shell print the target directory to stdout +# if CDPATH is set. +(unset CDPATH) >/dev/null 2>&1 && unset CDPATH + +relink_command="(cd /home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14; { test -z \"\${LIBRARY_PATH+set}\" || unset LIBRARY_PATH || { LIBRARY_PATH=; export LIBRARY_PATH; }; }; { test -z \"\${COMPILER_PATH+set}\" || unset COMPILER_PATH || { COMPILER_PATH=; export COMPILER_PATH; }; }; { test -z \"\${GCC_EXEC_PREFIX+set}\" || unset GCC_EXEC_PREFIX || { GCC_EXEC_PREFIX=; export GCC_EXEC_PREFIX; }; }; { test -z \"\${LD_RUN_PATH+set}\" || unset LD_RUN_PATH || { LD_RUN_PATH=; export LD_RUN_PATH; }; }; { test -z \"\${LD_LIBRARY_PATH+set}\" || unset LD_LIBRARY_PATH || { LD_LIBRARY_PATH=; export LD_LIBRARY_PATH; }; }; PATH=/sbin:/usr/sbin:/usr/bin:/bin:/usr/local/sbin:/usr/local/bin; export PATH; gcc -Wall -W -Wfloat-equal -Wpointer-arith -Wcast-align -Wstrict-prototypes -Wredundant-decls -Wendif-labels -Wshadow -pipe -ffast-math -U__STRICT_ANSI__ -std=gnu99 -fomit-frame-pointer -O3 -o \$progdir/\$file guru_poly_test-field.o guru_poly_test-z.o guru_poly_test-naivefp.o guru_poly_test-fastfp.o guru_poly_test-fp.o guru_poly_test-fasterfp.o guru_poly_test-montfp.o guru_poly_test-ternary_extension_field.o guru_poly_test-multiz.o guru_poly_test-dlog.o guru_poly_test-fieldquadratic.o guru_poly_test-poly.o guru_poly_test-random.o guru_poly_test-init_random.o guru_poly_test-darray.o guru_poly_test-symtab.o guru_poly_test-get_time.o guru_poly_test-utils.o guru_poly_test-memory.o guru_poly_test-extend_printf.o guru_poly_test-mpc.o guru_poly_test-mnt.o guru_poly_test-hilbert.o guru_poly_test-curve.o guru_poly_test-pairing.o guru_poly_test-singular.o guru_poly_test-eta_T_3.o guru_poly_test-param.o guru_poly_test-a_param.o guru_poly_test-d_param.o guru_poly_test-e_param.o guru_poly_test-f_param.o guru_poly_test-g_param.o guru_poly_test-poly_test.o ./.libs/libpbc.so -lgmp -lm -Wl,-rpath -Wl,/home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14/.libs)" + +# This environment variable determines our operation mode. +if test "$libtool_install_magic" = "%%%MAGIC variable%%%"; then + # install mode needs the following variables: + generated_by_libtool_version='2.4.2' + notinst_deplibs=' libpbc.la' +else + # When we are sourced in execute mode, $file and $ECHO are already set. + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + file="$0" + +# A function that is used when there is no print builtin or printf. +func_fallback_echo () +{ + eval 'cat <<_LTECHO_EOF +$1 +_LTECHO_EOF' +} + ECHO="printf %s\\n" + fi + +# Very basic option parsing. These options are (a) specific to +# the libtool wrapper, (b) are identical between the wrapper +# /script/ and the wrapper /executable/ which is used only on +# windows platforms, and (c) all begin with the string --lt- +# (application programs are unlikely to have options which match +# this pattern). +# +# There are only two supported options: --lt-debug and +# --lt-dump-script. There is, deliberately, no --lt-help. +# +# The first argument to this parsing function should be the +# script's ./libtool value, followed by no. +lt_option_debug= +func_parse_lt_options () +{ + lt_script_arg0=$0 + shift + for lt_opt + do + case "$lt_opt" in + --lt-debug) lt_option_debug=1 ;; + --lt-dump-script) + lt_dump_D=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%/[^/]*$%%'` + test "X$lt_dump_D" = "X$lt_script_arg0" && lt_dump_D=. + lt_dump_F=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%^.*/%%'` + cat "$lt_dump_D/$lt_dump_F" + exit 0 + ;; + --lt-*) + $ECHO "Unrecognized --lt- option: '$lt_opt'" 1>&2 + exit 1 + ;; + esac + done + + # Print the debug banner immediately: + if test -n "$lt_option_debug"; then + echo "poly_test:guru/poly_test:${LINENO}: libtool wrapper (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1" 1>&2 + fi +} + +# Used when --lt-debug. Prints its arguments to stdout +# (redirection is the responsibility of the caller) +func_lt_dump_args () +{ + lt_dump_args_N=1; + for lt_arg + do + $ECHO "poly_test:guru/poly_test:${LINENO}: newargv[$lt_dump_args_N]: $lt_arg" + lt_dump_args_N=`expr $lt_dump_args_N + 1` + done +} + +# Core function for launching the target application +func_exec_program_core () +{ + + if test -n "$lt_option_debug"; then + $ECHO "poly_test:guru/poly_test:${LINENO}: newargv[0]: $progdir/$program" 1>&2 + func_lt_dump_args ${1+"$@"} 1>&2 + fi + exec "$progdir/$program" ${1+"$@"} + + $ECHO "$0: cannot exec $program $*" 1>&2 + exit 1 +} + +# A function to encapsulate launching the target application +# Strips options in the --lt-* namespace from $@ and +# launches target application with the remaining arguments. +func_exec_program () +{ + case " $* " in + *\ --lt-*) + for lt_wr_arg + do + case $lt_wr_arg in + --lt-*) ;; + *) set x "$@" "$lt_wr_arg"; shift;; + esac + shift + done ;; + esac + func_exec_program_core ${1+"$@"} +} + + # Parse options + func_parse_lt_options "$0" ${1+"$@"} + + # Find the directory that this script lives in. + thisdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + test "x$thisdir" = "x$file" && thisdir=. + + # Follow symbolic links until we get to the real thisdir. + file=`ls -ld "$file" | /bin/sed -n 's/.*-> //p'` + while test -n "$file"; do + destdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + + # If there was a directory component, then change thisdir. + if test "x$destdir" != "x$file"; then + case "$destdir" in + [\\/]* | [A-Za-z]:[\\/]*) thisdir="$destdir" ;; + *) thisdir="$thisdir/$destdir" ;; + esac + fi + + file=`$ECHO "$file" | /bin/sed 's%^.*/%%'` + file=`ls -ld "$thisdir/$file" | /bin/sed -n 's/.*-> //p'` + done + + # Usually 'no', except on cygwin/mingw when embedded into + # the cwrapper. + WRAPPER_SCRIPT_BELONGS_IN_OBJDIR=no + if test "$WRAPPER_SCRIPT_BELONGS_IN_OBJDIR" = "yes"; then + # special case for '.' + if test "$thisdir" = "."; then + thisdir=`pwd` + fi + # remove .libs from thisdir + case "$thisdir" in + *[\\/].libs ) thisdir=`$ECHO "$thisdir" | /bin/sed 's%[\\/][^\\/]*$%%'` ;; + .libs ) thisdir=. ;; + esac + fi + + # Try to get the absolute directory name. + absdir=`cd "$thisdir" && pwd` + test -n "$absdir" && thisdir="$absdir" + + program=lt-'poly_test' + progdir="$thisdir/.libs" + + if test ! -f "$progdir/$program" || + { file=`ls -1dt "$progdir/$program" "$progdir/../$program" 2>/dev/null | /bin/sed 1q`; \ + test "X$file" != "X$progdir/$program"; }; then + + file="$$-$program" + + if test ! -d "$progdir"; then + mkdir "$progdir" + else + rm -f "$progdir/$file" + fi + + # relink executable if necessary + if test -n "$relink_command"; then + if relink_command_output=`eval $relink_command 2>&1`; then : + else + printf %s\n "$relink_command_output" >&2 + rm -f "$progdir/$file" + exit 1 + fi + fi + + mv -f "$progdir/$file" "$progdir/$program" 2>/dev/null || + { rm -f "$progdir/$program"; + mv -f "$progdir/$file" "$progdir/$program"; } + rm -f "$progdir/$file" + fi + + if test -f "$progdir/$program"; then + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + # Run the actual program with our arguments. + func_exec_program ${1+"$@"} + fi + else + # The program doesn't exist. + $ECHO "$0: error: \`$progdir/$program' does not exist" 1>&2 + $ECHO "This script is just a wrapper for $program." 1>&2 + $ECHO "See the libtool documentation for more information." 1>&2 + exit 1 + fi +fi 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 b/moon-abe/pbc-0.5.14/guru/prodpairing_test new file mode 100755 index 00000000..e1c948c3 --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/prodpairing_test @@ -0,0 +1,228 @@ +#! /bin/sh + +# guru/prodpairing_test - temporary wrapper script for .libs/prodpairing_test +# Generated by libtool (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1 +# +# The guru/prodpairing_test program cannot be directly executed until all the libtool +# libraries that it depends on are installed. +# +# This wrapper script should never be moved out of the build directory. +# If it is, it will not operate correctly. + +# Sed substitution that helps us do robust quoting. It backslashifies +# metacharacters that are still active within double-quoted strings. +sed_quote_subst='s/\([`"$\\]\)/\\\1/g' + +# Be Bourne compatible +if test -n "${ZSH_VERSION+set}" && (emulate sh) >/dev/null 2>&1; then + emulate sh + NULLCMD=: + # Zsh 3.x and 4.x performs word splitting on ${1+"$@"}, which + # is contrary to our usage. Disable this feature. + alias -g '${1+"$@"}'='"$@"' + setopt NO_GLOB_SUBST +else + case `(set -o) 2>/dev/null` in *posix*) set -o posix;; esac +fi +BIN_SH=xpg4; export BIN_SH # for Tru64 +DUALCASE=1; export DUALCASE # for MKS sh + +# The HP-UX ksh and POSIX shell print the target directory to stdout +# if CDPATH is set. +(unset CDPATH) >/dev/null 2>&1 && unset CDPATH + +relink_command="(cd /home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14; { test -z \"\${LIBRARY_PATH+set}\" || unset LIBRARY_PATH || { LIBRARY_PATH=; export LIBRARY_PATH; }; }; { test -z \"\${COMPILER_PATH+set}\" || unset COMPILER_PATH || { COMPILER_PATH=; export COMPILER_PATH; }; }; { test -z \"\${GCC_EXEC_PREFIX+set}\" || unset GCC_EXEC_PREFIX || { GCC_EXEC_PREFIX=; export GCC_EXEC_PREFIX; }; }; { test -z \"\${LD_RUN_PATH+set}\" || unset LD_RUN_PATH || { LD_RUN_PATH=; export LD_RUN_PATH; }; }; { test -z \"\${LD_LIBRARY_PATH+set}\" || unset LD_LIBRARY_PATH || { LD_LIBRARY_PATH=; export LD_LIBRARY_PATH; }; }; PATH=/sbin:/usr/sbin:/usr/bin:/bin:/usr/local/sbin:/usr/local/bin; export PATH; gcc -Wall -W -Wfloat-equal -Wpointer-arith -Wcast-align -Wstrict-prototypes -Wredundant-decls -Wendif-labels -Wshadow -pipe -ffast-math -U__STRICT_ANSI__ -std=gnu99 -fomit-frame-pointer -O3 -o \$progdir/\$file guru_prodpairing_test-prodpairing_test.o ./.libs/libpbc.so -lgmp -lm -Wl,-rpath -Wl,/home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14/.libs)" + +# This environment variable determines our operation mode. +if test "$libtool_install_magic" = "%%%MAGIC variable%%%"; then + # install mode needs the following variables: + generated_by_libtool_version='2.4.2' + notinst_deplibs=' libpbc.la' +else + # When we are sourced in execute mode, $file and $ECHO are already set. + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + file="$0" + +# A function that is used when there is no print builtin or printf. +func_fallback_echo () +{ + eval 'cat <<_LTECHO_EOF +$1 +_LTECHO_EOF' +} + ECHO="printf %s\\n" + fi + +# Very basic option parsing. These options are (a) specific to +# the libtool wrapper, (b) are identical between the wrapper +# /script/ and the wrapper /executable/ which is used only on +# windows platforms, and (c) all begin with the string --lt- +# (application programs are unlikely to have options which match +# this pattern). +# +# There are only two supported options: --lt-debug and +# --lt-dump-script. There is, deliberately, no --lt-help. +# +# The first argument to this parsing function should be the +# script's ./libtool value, followed by no. +lt_option_debug= +func_parse_lt_options () +{ + lt_script_arg0=$0 + shift + for lt_opt + do + case "$lt_opt" in + --lt-debug) lt_option_debug=1 ;; + --lt-dump-script) + lt_dump_D=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%/[^/]*$%%'` + test "X$lt_dump_D" = "X$lt_script_arg0" && lt_dump_D=. + lt_dump_F=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%^.*/%%'` + cat "$lt_dump_D/$lt_dump_F" + exit 0 + ;; + --lt-*) + $ECHO "Unrecognized --lt- option: '$lt_opt'" 1>&2 + exit 1 + ;; + esac + done + + # Print the debug banner immediately: + if test -n "$lt_option_debug"; then + echo "prodpairing_test:guru/prodpairing_test:${LINENO}: libtool wrapper (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1" 1>&2 + fi +} + +# Used when --lt-debug. Prints its arguments to stdout +# (redirection is the responsibility of the caller) +func_lt_dump_args () +{ + lt_dump_args_N=1; + for lt_arg + do + $ECHO "prodpairing_test:guru/prodpairing_test:${LINENO}: newargv[$lt_dump_args_N]: $lt_arg" + lt_dump_args_N=`expr $lt_dump_args_N + 1` + done +} + +# Core function for launching the target application +func_exec_program_core () +{ + + if test -n "$lt_option_debug"; then + $ECHO "prodpairing_test:guru/prodpairing_test:${LINENO}: newargv[0]: $progdir/$program" 1>&2 + func_lt_dump_args ${1+"$@"} 1>&2 + fi + exec "$progdir/$program" ${1+"$@"} + + $ECHO "$0: cannot exec $program $*" 1>&2 + exit 1 +} + +# A function to encapsulate launching the target application +# Strips options in the --lt-* namespace from $@ and +# launches target application with the remaining arguments. +func_exec_program () +{ + case " $* " in + *\ --lt-*) + for lt_wr_arg + do + case $lt_wr_arg in + --lt-*) ;; + *) set x "$@" "$lt_wr_arg"; shift;; + esac + shift + done ;; + esac + func_exec_program_core ${1+"$@"} +} + + # Parse options + func_parse_lt_options "$0" ${1+"$@"} + + # Find the directory that this script lives in. + thisdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + test "x$thisdir" = "x$file" && thisdir=. + + # Follow symbolic links until we get to the real thisdir. + file=`ls -ld "$file" | /bin/sed -n 's/.*-> //p'` + while test -n "$file"; do + destdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + + # If there was a directory component, then change thisdir. + if test "x$destdir" != "x$file"; then + case "$destdir" in + [\\/]* | [A-Za-z]:[\\/]*) thisdir="$destdir" ;; + *) thisdir="$thisdir/$destdir" ;; + esac + fi + + file=`$ECHO "$file" | /bin/sed 's%^.*/%%'` + file=`ls -ld "$thisdir/$file" | /bin/sed -n 's/.*-> //p'` + done + + # Usually 'no', except on cygwin/mingw when embedded into + # the cwrapper. + WRAPPER_SCRIPT_BELONGS_IN_OBJDIR=no + if test "$WRAPPER_SCRIPT_BELONGS_IN_OBJDIR" = "yes"; then + # special case for '.' + if test "$thisdir" = "."; then + thisdir=`pwd` + fi + # remove .libs from thisdir + case "$thisdir" in + *[\\/].libs ) thisdir=`$ECHO "$thisdir" | /bin/sed 's%[\\/][^\\/]*$%%'` ;; + .libs ) thisdir=. ;; + esac + fi + + # Try to get the absolute directory name. + absdir=`cd "$thisdir" && pwd` + test -n "$absdir" && thisdir="$absdir" + + program=lt-'prodpairing_test' + progdir="$thisdir/.libs" + + if test ! -f "$progdir/$program" || + { file=`ls -1dt "$progdir/$program" "$progdir/../$program" 2>/dev/null | /bin/sed 1q`; \ + test "X$file" != "X$progdir/$program"; }; then + + file="$$-$program" + + if test ! -d "$progdir"; then + mkdir "$progdir" + else + rm -f "$progdir/$file" + fi + + # relink executable if necessary + if test -n "$relink_command"; then + if relink_command_output=`eval $relink_command 2>&1`; then : + else + printf %s\n "$relink_command_output" >&2 + rm -f "$progdir/$file" + exit 1 + fi + fi + + mv -f "$progdir/$file" "$progdir/$program" 2>/dev/null || + { rm -f "$progdir/$program"; + mv -f "$progdir/$file" "$progdir/$program"; } + rm -f "$progdir/$file" + fi + + if test -f "$progdir/$program"; then + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + # Run the actual program with our arguments. + func_exec_program ${1+"$@"} + fi + else + # The program doesn't exist. + $ECHO "$0: error: \`$progdir/$program' does not exist" 1>&2 + $ECHO "This script is just a wrapper for $program." 1>&2 + $ECHO "See the libtool documentation for more information." 1>&2 + exit 1 + fi +fi 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 b/moon-abe/pbc-0.5.14/guru/quadratic_test new file mode 100755 index 00000000..350eaf1f --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/quadratic_test @@ -0,0 +1,228 @@ +#! /bin/sh + +# guru/quadratic_test - temporary wrapper script for .libs/quadratic_test +# Generated by libtool (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1 +# +# The guru/quadratic_test program cannot be directly executed until all the libtool +# libraries that it depends on are installed. +# +# This wrapper script should never be moved out of the build directory. +# If it is, it will not operate correctly. + +# Sed substitution that helps us do robust quoting. It backslashifies +# metacharacters that are still active within double-quoted strings. +sed_quote_subst='s/\([`"$\\]\)/\\\1/g' + +# Be Bourne compatible +if test -n "${ZSH_VERSION+set}" && (emulate sh) >/dev/null 2>&1; then + emulate sh + NULLCMD=: + # Zsh 3.x and 4.x performs word splitting on ${1+"$@"}, which + # is contrary to our usage. Disable this feature. + alias -g '${1+"$@"}'='"$@"' + setopt NO_GLOB_SUBST +else + case `(set -o) 2>/dev/null` in *posix*) set -o posix;; esac +fi +BIN_SH=xpg4; export BIN_SH # for Tru64 +DUALCASE=1; export DUALCASE # for MKS sh + +# The HP-UX ksh and POSIX shell print the target directory to stdout +# if CDPATH is set. +(unset CDPATH) >/dev/null 2>&1 && unset CDPATH + +relink_command="(cd /home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14; { test -z \"\${LIBRARY_PATH+set}\" || unset LIBRARY_PATH || { LIBRARY_PATH=; export LIBRARY_PATH; }; }; { test -z \"\${COMPILER_PATH+set}\" || unset COMPILER_PATH || { COMPILER_PATH=; export COMPILER_PATH; }; }; { test -z \"\${GCC_EXEC_PREFIX+set}\" || unset GCC_EXEC_PREFIX || { GCC_EXEC_PREFIX=; export GCC_EXEC_PREFIX; }; }; { test -z \"\${LD_RUN_PATH+set}\" || unset LD_RUN_PATH || { LD_RUN_PATH=; export LD_RUN_PATH; }; }; { test -z \"\${LD_LIBRARY_PATH+set}\" || unset LD_LIBRARY_PATH || { LD_LIBRARY_PATH=; export LD_LIBRARY_PATH; }; }; PATH=/sbin:/usr/sbin:/usr/bin:/bin:/usr/local/sbin:/usr/local/bin; export PATH; gcc -Wall -W -Wfloat-equal -Wpointer-arith -Wcast-align -Wstrict-prototypes -Wredundant-decls -Wendif-labels -Wshadow -pipe -ffast-math -U__STRICT_ANSI__ -std=gnu99 -fomit-frame-pointer -O3 -o \$progdir/\$file guru_quadratic_test-quadratic_test.o ./.libs/libpbc.so -lgmp -lm -Wl,-rpath -Wl,/home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14/.libs)" + +# This environment variable determines our operation mode. +if test "$libtool_install_magic" = "%%%MAGIC variable%%%"; then + # install mode needs the following variables: + generated_by_libtool_version='2.4.2' + notinst_deplibs=' libpbc.la' +else + # When we are sourced in execute mode, $file and $ECHO are already set. + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + file="$0" + +# A function that is used when there is no print builtin or printf. +func_fallback_echo () +{ + eval 'cat <<_LTECHO_EOF +$1 +_LTECHO_EOF' +} + ECHO="printf %s\\n" + fi + +# Very basic option parsing. These options are (a) specific to +# the libtool wrapper, (b) are identical between the wrapper +# /script/ and the wrapper /executable/ which is used only on +# windows platforms, and (c) all begin with the string --lt- +# (application programs are unlikely to have options which match +# this pattern). +# +# There are only two supported options: --lt-debug and +# --lt-dump-script. There is, deliberately, no --lt-help. +# +# The first argument to this parsing function should be the +# script's ./libtool value, followed by no. +lt_option_debug= +func_parse_lt_options () +{ + lt_script_arg0=$0 + shift + for lt_opt + do + case "$lt_opt" in + --lt-debug) lt_option_debug=1 ;; + --lt-dump-script) + lt_dump_D=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%/[^/]*$%%'` + test "X$lt_dump_D" = "X$lt_script_arg0" && lt_dump_D=. + lt_dump_F=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%^.*/%%'` + cat "$lt_dump_D/$lt_dump_F" + exit 0 + ;; + --lt-*) + $ECHO "Unrecognized --lt- option: '$lt_opt'" 1>&2 + exit 1 + ;; + esac + done + + # Print the debug banner immediately: + if test -n "$lt_option_debug"; then + echo "quadratic_test:guru/quadratic_test:${LINENO}: libtool wrapper (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1" 1>&2 + fi +} + +# Used when --lt-debug. Prints its arguments to stdout +# (redirection is the responsibility of the caller) +func_lt_dump_args () +{ + lt_dump_args_N=1; + for lt_arg + do + $ECHO "quadratic_test:guru/quadratic_test:${LINENO}: newargv[$lt_dump_args_N]: $lt_arg" + lt_dump_args_N=`expr $lt_dump_args_N + 1` + done +} + +# Core function for launching the target application +func_exec_program_core () +{ + + if test -n "$lt_option_debug"; then + $ECHO "quadratic_test:guru/quadratic_test:${LINENO}: newargv[0]: $progdir/$program" 1>&2 + func_lt_dump_args ${1+"$@"} 1>&2 + fi + exec "$progdir/$program" ${1+"$@"} + + $ECHO "$0: cannot exec $program $*" 1>&2 + exit 1 +} + +# A function to encapsulate launching the target application +# Strips options in the --lt-* namespace from $@ and +# launches target application with the remaining arguments. +func_exec_program () +{ + case " $* " in + *\ --lt-*) + for lt_wr_arg + do + case $lt_wr_arg in + --lt-*) ;; + *) set x "$@" "$lt_wr_arg"; shift;; + esac + shift + done ;; + esac + func_exec_program_core ${1+"$@"} +} + + # Parse options + func_parse_lt_options "$0" ${1+"$@"} + + # Find the directory that this script lives in. + thisdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + test "x$thisdir" = "x$file" && thisdir=. + + # Follow symbolic links until we get to the real thisdir. + file=`ls -ld "$file" | /bin/sed -n 's/.*-> //p'` + while test -n "$file"; do + destdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + + # If there was a directory component, then change thisdir. + if test "x$destdir" != "x$file"; then + case "$destdir" in + [\\/]* | [A-Za-z]:[\\/]*) thisdir="$destdir" ;; + *) thisdir="$thisdir/$destdir" ;; + esac + fi + + file=`$ECHO "$file" | /bin/sed 's%^.*/%%'` + file=`ls -ld "$thisdir/$file" | /bin/sed -n 's/.*-> //p'` + done + + # Usually 'no', except on cygwin/mingw when embedded into + # the cwrapper. + WRAPPER_SCRIPT_BELONGS_IN_OBJDIR=no + if test "$WRAPPER_SCRIPT_BELONGS_IN_OBJDIR" = "yes"; then + # special case for '.' + if test "$thisdir" = "."; then + thisdir=`pwd` + fi + # remove .libs from thisdir + case "$thisdir" in + *[\\/].libs ) thisdir=`$ECHO "$thisdir" | /bin/sed 's%[\\/][^\\/]*$%%'` ;; + .libs ) thisdir=. ;; + esac + fi + + # Try to get the absolute directory name. + absdir=`cd "$thisdir" && pwd` + test -n "$absdir" && thisdir="$absdir" + + program=lt-'quadratic_test' + progdir="$thisdir/.libs" + + if test ! -f "$progdir/$program" || + { file=`ls -1dt "$progdir/$program" "$progdir/../$program" 2>/dev/null | /bin/sed 1q`; \ + test "X$file" != "X$progdir/$program"; }; then + + file="$$-$program" + + if test ! -d "$progdir"; then + mkdir "$progdir" + else + rm -f "$progdir/$file" + fi + + # relink executable if necessary + if test -n "$relink_command"; then + if relink_command_output=`eval $relink_command 2>&1`; then : + else + printf %s\n "$relink_command_output" >&2 + rm -f "$progdir/$file" + exit 1 + fi + fi + + mv -f "$progdir/$file" "$progdir/$program" 2>/dev/null || + { rm -f "$progdir/$program"; + mv -f "$progdir/$file" "$progdir/$program"; } + rm -f "$progdir/$file" + fi + + if test -f "$progdir/$program"; then + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + # Run the actual program with our arguments. + func_exec_program ${1+"$@"} + fi + else + # The program doesn't exist. + $ECHO "$0: error: \`$progdir/$program' does not exist" 1>&2 + $ECHO "This script is just a wrapper for $program." 1>&2 + $ECHO "See the libtool documentation for more information." 1>&2 + exit 1 + fi +fi 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 b/moon-abe/pbc-0.5.14/guru/ternary_extension_field_test new file mode 100755 index 00000000..b4f94880 --- /dev/null +++ b/moon-abe/pbc-0.5.14/guru/ternary_extension_field_test @@ -0,0 +1,228 @@ +#! /bin/sh + +# guru/ternary_extension_field_test - temporary wrapper script for .libs/ternary_extension_field_test +# Generated by libtool (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1 +# +# The guru/ternary_extension_field_test program cannot be directly executed until all the libtool +# libraries that it depends on are installed. +# +# This wrapper script should never be moved out of the build directory. +# If it is, it will not operate correctly. + +# Sed substitution that helps us do robust quoting. It backslashifies +# metacharacters that are still active within double-quoted strings. +sed_quote_subst='s/\([`"$\\]\)/\\\1/g' + +# Be Bourne compatible +if test -n "${ZSH_VERSION+set}" && (emulate sh) >/dev/null 2>&1; then + emulate sh + NULLCMD=: + # Zsh 3.x and 4.x performs word splitting on ${1+"$@"}, which + # is contrary to our usage. Disable this feature. + alias -g '${1+"$@"}'='"$@"' + setopt NO_GLOB_SUBST +else + case `(set -o) 2>/dev/null` in *posix*) set -o posix;; esac +fi +BIN_SH=xpg4; export BIN_SH # for Tru64 +DUALCASE=1; export DUALCASE # for MKS sh + +# The HP-UX ksh and POSIX shell print the target directory to stdout +# if CDPATH is set. +(unset CDPATH) >/dev/null 2>&1 && unset CDPATH + +relink_command="(cd /home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14; { test -z \"\${LIBRARY_PATH+set}\" || unset LIBRARY_PATH || { LIBRARY_PATH=; export LIBRARY_PATH; }; }; { test -z \"\${COMPILER_PATH+set}\" || unset COMPILER_PATH || { COMPILER_PATH=; export COMPILER_PATH; }; }; { test -z \"\${GCC_EXEC_PREFIX+set}\" || unset GCC_EXEC_PREFIX || { GCC_EXEC_PREFIX=; export GCC_EXEC_PREFIX; }; }; { test -z \"\${LD_RUN_PATH+set}\" || unset LD_RUN_PATH || { LD_RUN_PATH=; export LD_RUN_PATH; }; }; { test -z \"\${LD_LIBRARY_PATH+set}\" || unset LD_LIBRARY_PATH || { LD_LIBRARY_PATH=; export LD_LIBRARY_PATH; }; }; PATH=/sbin:/usr/sbin:/usr/bin:/bin:/usr/local/sbin:/usr/local/bin; export PATH; gcc -Wall -W -Wfloat-equal -Wpointer-arith -Wcast-align -Wstrict-prototypes -Wredundant-decls -Wendif-labels -Wshadow -pipe -ffast-math -U__STRICT_ANSI__ -std=gnu99 -fomit-frame-pointer -O3 -o \$progdir/\$file guru_ternary_extension_field_test-ternary_extension_field_test.o ./.libs/libpbc.so -lgmp -lm -Wl,-rpath -Wl,/home/wukong/Dropbox/04_Workspace/opnfv-moon/moon-abe/pbc-0.5.14/.libs)" + +# This environment variable determines our operation mode. +if test "$libtool_install_magic" = "%%%MAGIC variable%%%"; then + # install mode needs the following variables: + generated_by_libtool_version='2.4.2' + notinst_deplibs=' libpbc.la' +else + # When we are sourced in execute mode, $file and $ECHO are already set. + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + file="$0" + +# A function that is used when there is no print builtin or printf. +func_fallback_echo () +{ + eval 'cat <<_LTECHO_EOF +$1 +_LTECHO_EOF' +} + ECHO="printf %s\\n" + fi + +# Very basic option parsing. These options are (a) specific to +# the libtool wrapper, (b) are identical between the wrapper +# /script/ and the wrapper /executable/ which is used only on +# windows platforms, and (c) all begin with the string --lt- +# (application programs are unlikely to have options which match +# this pattern). +# +# There are only two supported options: --lt-debug and +# --lt-dump-script. There is, deliberately, no --lt-help. +# +# The first argument to this parsing function should be the +# script's ./libtool value, followed by no. +lt_option_debug= +func_parse_lt_options () +{ + lt_script_arg0=$0 + shift + for lt_opt + do + case "$lt_opt" in + --lt-debug) lt_option_debug=1 ;; + --lt-dump-script) + lt_dump_D=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%/[^/]*$%%'` + test "X$lt_dump_D" = "X$lt_script_arg0" && lt_dump_D=. + lt_dump_F=`$ECHO "X$lt_script_arg0" | /bin/sed -e 's/^X//' -e 's%^.*/%%'` + cat "$lt_dump_D/$lt_dump_F" + exit 0 + ;; + --lt-*) + $ECHO "Unrecognized --lt- option: '$lt_opt'" 1>&2 + exit 1 + ;; + esac + done + + # Print the debug banner immediately: + if test -n "$lt_option_debug"; then + echo "ternary_extension_field_test:guru/ternary_extension_field_test:${LINENO}: libtool wrapper (GNU libtool) 2.4.2 Debian-2.4.2-1ubuntu1" 1>&2 + fi +} + +# Used when --lt-debug. Prints its arguments to stdout +# (redirection is the responsibility of the caller) +func_lt_dump_args () +{ + lt_dump_args_N=1; + for lt_arg + do + $ECHO "ternary_extension_field_test:guru/ternary_extension_field_test:${LINENO}: newargv[$lt_dump_args_N]: $lt_arg" + lt_dump_args_N=`expr $lt_dump_args_N + 1` + done +} + +# Core function for launching the target application +func_exec_program_core () +{ + + if test -n "$lt_option_debug"; then + $ECHO "ternary_extension_field_test:guru/ternary_extension_field_test:${LINENO}: newargv[0]: $progdir/$program" 1>&2 + func_lt_dump_args ${1+"$@"} 1>&2 + fi + exec "$progdir/$program" ${1+"$@"} + + $ECHO "$0: cannot exec $program $*" 1>&2 + exit 1 +} + +# A function to encapsulate launching the target application +# Strips options in the --lt-* namespace from $@ and +# launches target application with the remaining arguments. +func_exec_program () +{ + case " $* " in + *\ --lt-*) + for lt_wr_arg + do + case $lt_wr_arg in + --lt-*) ;; + *) set x "$@" "$lt_wr_arg"; shift;; + esac + shift + done ;; + esac + func_exec_program_core ${1+"$@"} +} + + # Parse options + func_parse_lt_options "$0" ${1+"$@"} + + # Find the directory that this script lives in. + thisdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + test "x$thisdir" = "x$file" && thisdir=. + + # Follow symbolic links until we get to the real thisdir. + file=`ls -ld "$file" | /bin/sed -n 's/.*-> //p'` + while test -n "$file"; do + destdir=`$ECHO "$file" | /bin/sed 's%/[^/]*$%%'` + + # If there was a directory component, then change thisdir. + if test "x$destdir" != "x$file"; then + case "$destdir" in + [\\/]* | [A-Za-z]:[\\/]*) thisdir="$destdir" ;; + *) thisdir="$thisdir/$destdir" ;; + esac + fi + + file=`$ECHO "$file" | /bin/sed 's%^.*/%%'` + file=`ls -ld "$thisdir/$file" | /bin/sed -n 's/.*-> //p'` + done + + # Usually 'no', except on cygwin/mingw when embedded into + # the cwrapper. + WRAPPER_SCRIPT_BELONGS_IN_OBJDIR=no + if test "$WRAPPER_SCRIPT_BELONGS_IN_OBJDIR" = "yes"; then + # special case for '.' + if test "$thisdir" = "."; then + thisdir=`pwd` + fi + # remove .libs from thisdir + case "$thisdir" in + *[\\/].libs ) thisdir=`$ECHO "$thisdir" | /bin/sed 's%[\\/][^\\/]*$%%'` ;; + .libs ) thisdir=. ;; + esac + fi + + # Try to get the absolute directory name. + absdir=`cd "$thisdir" && pwd` + test -n "$absdir" && thisdir="$absdir" + + program=lt-'ternary_extension_field_test' + progdir="$thisdir/.libs" + + if test ! -f "$progdir/$program" || + { file=`ls -1dt "$progdir/$program" "$progdir/../$program" 2>/dev/null | /bin/sed 1q`; \ + test "X$file" != "X$progdir/$program"; }; then + + file="$$-$program" + + if test ! -d "$progdir"; then + mkdir "$progdir" + else + rm -f "$progdir/$file" + fi + + # relink executable if necessary + if test -n "$relink_command"; then + if relink_command_output=`eval $relink_command 2>&1`; then : + else + printf %s\n "$relink_command_output" >&2 + rm -f "$progdir/$file" + exit 1 + fi + fi + + mv -f "$progdir/$file" "$progdir/$program" 2>/dev/null || + { rm -f "$progdir/$program"; + mv -f "$progdir/$file" "$progdir/$program"; } + rm -f "$progdir/$file" + fi + + if test -f "$progdir/$program"; then + if test "$libtool_execute_magic" != "%%%MAGIC variable%%%"; then + # Run the actual program with our arguments. + func_exec_program ${1+"$@"} + fi + else + # The program doesn't exist. + $ECHO "$0: error: \`$progdir/$program' does not exist" 1>&2 + $ECHO "This script is just a wrapper for $program." 1>&2 + $ECHO "See the libtool documentation for more information." 1>&2 + exit 1 + fi +fi 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; +} |