aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/cm/cm.c17
-rw-r--r--src/cm/p1363.c391
-rw-r--r--src/cm/p1363.h39
-rw-r--r--src/exhaustive/anomalous.c156
-rw-r--r--src/exhaustive/anomalous.h32
-rw-r--r--src/exhaustive/exhaustive.c33
-rw-r--r--src/exhaustive/seed.c23
-rw-r--r--src/io/cli.c25
-rw-r--r--src/io/cli.h1
-rw-r--r--src/io/config.h3
-rw-r--r--src/math/arg.c4
-rw-r--r--src/math/types.h7
12 files changed, 718 insertions, 13 deletions
diff --git a/src/cm/cm.c b/src/cm/cm.c
index 71e720c..43ae515 100644
--- a/src/cm/cm.c
+++ b/src/cm/cm.c
@@ -2,10 +2,21 @@
* ecgen, tool for generating Elliptic curve domain parameters
* Copyright (C) 2017 J08nY
*/
+/**
+ * @file cm.c
+ */
#include "cm.h"
-#include "io/output.h"
+#include "exhaustive/anomalous.h"
+#include "p1363.h"
int cm_do(config_t *cfg) {
- debug("# Starting Complex Multiplication method\n");
- return INT_MIN;
+ GEN D = stoi(71);
+ form_t **forms;
+ size_t nforms = p1363_forms(D, &forms);
+ for (size_t i = 0; i < nforms; ++i) {
+ p1363_invariant(D, forms[i]);
+ }
+
+ p1363_free(&forms, nforms);
+ return 0;
}
diff --git a/src/cm/p1363.c b/src/cm/p1363.c
new file mode 100644
index 0000000..24d28cb
--- /dev/null
+++ b/src/cm/p1363.c
@@ -0,0 +1,391 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+/**
+ * @file p1363.c
+ */
+#include "p1363.h"
+#include <pari/paripriv.h>
+
+GEN p1363_group(GEN D) {
+ pari_sp ltop = avma;
+ GEN s = mpfloor(sqrtr(rdivis(D, 3, BIGDEFAULTPREC)));
+ long llen = itos(s) * 2;
+ GEN l = gtovec0(gen_0, llen);
+
+ long j = 1;
+ GEN B = gen_0;
+ for (; cmpii(B, s) <= 0; B = addii(B, gen_1)) {
+ GEN B2 = sqri(B);
+ GEN d = addii(D, B2);
+ GEN lower = mulis(B, 2);
+ GEN upper = gsqrt(d, BIGDEFAULTPREC);
+
+ GEN divs = divisors(d);
+ long len = glength(divs);
+ for (long i = 1; i <= len; ++i) {
+ GEN div = gel(divs, i);
+ if (gcmp(div, lower) >= 0 && gcmp(div, upper) <= 0) {
+ GEN A = div;
+ GEN C = divii(d, A);
+ GEN gcd = gcdii(gcdii(A, lower), C);
+
+ if (gequal1(gcd)) {
+ GEN v = gtovec0(gen_0, 3);
+ gel(v, 1) = A;
+ gel(v, 2) = B;
+ gel(v, 3) = C;
+ gel(l, j++) = v;
+ if (cmpii(gen_0, lower) < 0 && cmpii(lower, A) < 0 &&
+ cmpii(A, C) < 0) {
+ GEN n = gtovec0(gen_0, 3);
+ gel(n, 1) = A;
+ gel(n, 2) = negi(B);
+ gel(n, 3) = C;
+ gel(l, j++) = n;
+ }
+ }
+ }
+ }
+ }
+ return gerepilecopy(ltop, vec_shorten(l, j - 1));
+}
+
+long p1363_num(GEN group) { return glength(group); }
+
+size_t p1363_forms(GEN D, form_t ***forms) {
+ GEN group = p1363_group(D);
+ size_t nforms = (size_t)p1363_num(group);
+ *forms = pari_malloc(nforms * sizeof(form_t *));
+ memset(*forms, 0, nforms * sizeof(form_t *));
+
+ for (size_t i = 0; i < nforms; ++i) {
+ (*forms)[i] = pari_malloc(sizeof(form_t));
+ memset((*forms)[i], 0, sizeof(form_t));
+ (*forms)[i]->A = gel(gel(group, i + 1), 1);
+ (*forms)[i]->B = gel(gel(group, i + 1), 2);
+ (*forms)[i]->C = gel(gel(group, i + 1), 3);
+ }
+
+ return nforms;
+}
+
+void p1363_free(form_t ***forms, size_t nforms) {
+ if (*forms) {
+ for (size_t i = 0; i < nforms; ++i) {
+ if ((*forms)[i]) {
+ pari_free((*forms)[i]);
+ (*forms)[i] = NULL;
+ }
+ }
+ pari_free(*forms);
+ *forms = NULL;
+ }
+}
+
+GEN p1363_func_F(GEN z) {
+ pari_sp ltop = avma;
+
+ if (gequal0(z)) {
+ return gcopy(gen_1);
+ }
+ GEN sum = cgetc(BIGDEFAULTPREC * 5);
+ gel(sum, 1) = real_1(BIGDEFAULTPREC * 5);
+ gel(sum, 2) = real_0(BIGDEFAULTPREC * 5);
+ pari_printf("initial sum = %Ps\n", sum);
+ GEN last;
+
+ GEN j = gcopy(gen_1);
+ do {
+ last = gcopy(sum);
+
+ GEN j3 = mulsi(3, sqri(j));
+ GEN quota = divis(subii(j3, j), 2);
+ GEN quotb = divis(addii(j3, j), 2);
+
+ GEN term = gadd(gpow(z, quota, BIGDEFAULTPREC),
+ gpow(z, quotb, BIGDEFAULTPREC));
+ pari_printf("%Ps %Ps \n", sum, term);
+ if (mod2(j) == 0) {
+ sum = gadd(sum, term);
+ } else {
+ sum = gsub(sum, term);
+ }
+
+ addiiz(j, gen_1, j);
+ if (gc_needed(ltop, 1)) gerepileall(ltop, 3, &j, &sum, &last);
+ } while (!gequal(sum, last));
+
+ pari_printf("end sum = %Ps, last = %Ps\n", sum, last);
+
+ return gerepilecopy(ltop, sum);
+}
+
+GEN p1363_func_fzero(GEN D, form_t *form) {
+ pari_sp ltop = avma;
+
+ GEN upper = p1363_func_F(gneg(form->theta));
+ GEN lower = p1363_func_F(gsqr(form->theta));
+ GEN front = gpow(form->theta, gdivgs(gen_m1, 24), BIGDEFAULTPREC * 5);
+
+ GEN result = gmul(gdiv(upper, lower), front);
+
+ return gerepilecopy(ltop, result);
+}
+
+GEN p1363_func_fone(GEN D, form_t *form) {
+ pari_sp ltop = avma;
+
+ GEN upper = p1363_func_F(form->theta);
+ GEN lower = p1363_func_F(gsqr(form->theta));
+ GEN front = gpow(form->theta, gdivgs(gen_m1, 24), BIGDEFAULTPREC * 5);
+
+ GEN result = gmul(gdiv(upper, lower), front);
+
+ return gerepilecopy(ltop, result);
+}
+
+GEN p1363_func_ftwo(GEN D, form_t *form) {
+ pari_sp ltop = avma;
+
+ GEN upper = p1363_func_F(gpowgs(form->theta, 4));
+ GEN lower = p1363_func_F(gsqr(form->theta));
+ GEN front = gmul(sqrti(gen_2),
+ gpow(form->theta, gdivgs(gen_1, 12), BIGDEFAULTPREC * 5));
+
+ GEN result = gmul(gdiv(upper, lower), front);
+
+ return gerepilecopy(ltop, result);
+}
+
+void p1363_m8(GEN D, form_t *form) { form->m8 = mod8(D); }
+
+void p1363_I(GEN D, form_t *form) {
+ switch (form->m8) {
+ case 1:
+ case 2:
+ case 6:
+ case 7:
+ form->I = 3;
+ break;
+ case 5:
+ form->I = 6;
+ break;
+ case 3:
+ if (dvdis(D, 3)) {
+ form->I = 2;
+ } else {
+ form->I = 0;
+ }
+ break;
+ default:
+ pari_err_DOMAIN("p1636_I", "D", "==", stoi(8), D);
+ }
+}
+
+void p1363_J(GEN D, form_t *form) {
+ pari_sp ltop = avma;
+ GEN ac = mulii(form->A, form->C);
+
+ if (mod2(ac) == 1) {
+ form->J = 0;
+ } else {
+ if (mod2(form->C) == 0) {
+ form->J = 1;
+ } else if (mod2(form->A) == 0) {
+ form->J = 2;
+ } else {
+ pari_err_BUG("hwat?");
+ }
+ }
+ avma = ltop;
+}
+
+void p1363_K(GEN D, form_t *form) {
+ switch (form->m8) {
+ case 1:
+ case 2:
+ case 6:
+ form->K = 2;
+ break;
+ case 3:
+ case 7:
+ form->K = 1;
+ break;
+ case 5:
+ form->K = 5;
+ break;
+ default:
+ pari_err_DOMAIN("p1636_I", "D", "==", stoi(8), D);
+ }
+}
+
+void p1363_L(GEN D, form_t *form) {
+ pari_sp ltop = avma;
+ GEN ac = mulii(form->A, form->C);
+ long a2 = mod2(form->A);
+ long c2 = mod2(form->C);
+
+ if (mod2(ac) == 1 || (form->m8 == 5 && mod2(form->C) == 0)) {
+ form->L = addii(subii(form->A, form->C), mulii(sqri(form->A), form->C));
+ } else {
+ if (a2 == 0) {
+ if (form->m8 == 3) {
+ form->L = addii(subii(form->A, form->C),
+ mulsi(5, mulii(form->A, sqri(form->C))));
+ } else {
+ form->L = subii(subii(form->A, form->C),
+ mulii(form->A, sqri(form->C)));
+ }
+ } else if (c2 == 0) {
+ form->L = subii(addii(form->A, mulsi(2, form->C)),
+ mulii(form->A, sqri(form->C)));
+ } else {
+ pari_err_BUG("what?");
+ }
+ }
+ form->L = gerepileupto(ltop, form->L);
+}
+
+void p1363_M(GEN D, form_t *form) {
+ pari_sp ltop = avma;
+ GEN quot;
+ if (mod2(form->A) == 0) {
+ quot = divis(subis(sqri(form->C), 1), 8);
+ } else {
+ quot = divis(subis(sqri(form->A), 1), 8);
+ }
+ form->M = gerepileupto(ltop, powii(gen_m1, quot));
+}
+
+void p1363_N(GEN D, form_t *form) {
+ pari_sp ltop = avma;
+ long ac2 = mod2(mulii(form->A, form->C));
+
+ switch (form->m8) {
+ case 5:
+ form->N = gen_1;
+ break;
+ case 1:
+ case 2:
+ case 6:
+ form->N = gcopy(form->M);
+ break;
+ case 3:
+ if (ac2 == 0) {
+ form->N = negi(form->M);
+ } else {
+ form->N = gen_1;
+ }
+ break;
+ case 7:
+ if (ac2 == 0) {
+ form->N = gen_1;
+ } else {
+ form->N = gcopy(form->M);
+ }
+ break;
+ default:
+ pari_err_DOMAIN("p1363_N", "D", "=", stoi(8), D);
+ }
+ form->N = gerepileupto(ltop, form->N);
+}
+
+void p1363_lambda(GEN D, form_t *form) {
+ pari_sp ltop = avma;
+ GEN pik = mulri(mppi(BIGDEFAULTPREC), stoi(form->K));
+ GEN quot = divrs(pik, 24);
+ form->lambda = gerepileupto(ltop, expIr(quot));
+}
+
+void p1363_theta(GEN D, form_t *form) {
+ pari_sp ltop = avma;
+
+ GEN upper = gadd(gneg(gsqrt(D, BIGDEFAULTPREC)), gmul(form->B, gen_I()));
+ GEN quot = gmul(gdiv(upper, form->A), mppi(BIGDEFAULTPREC));
+
+ form->theta = gerepileupto(ltop, gexp(quot, BIGDEFAULTPREC));
+}
+
+GEN p1363_invariant(GEN D, form_t *form) {
+ pari_printf("[A,B,C] = %Pi %Pi %Pi\n", form->A, form->B, form->C);
+ pari_sp ltop = avma;
+
+ p1363_m8(D, form);
+ p1363_I(D, form);
+ printf("I = %li\n", form->I);
+ p1363_J(D, form);
+ printf("J = %li\n", form->J);
+ p1363_K(D, form);
+ printf("K = %li\n", form->K);
+ p1363_L(D, form);
+ pari_printf("L = %Pi\n", form->L);
+ p1363_M(D, form);
+ pari_printf("M = %Pi\n", form->M);
+ p1363_N(D, form);
+ pari_printf("N = %Pi\n", form->N);
+ p1363_lambda(D, form);
+ pari_printf("lambda = %Ps\n", form->lambda);
+ p1363_theta(D, form);
+ pari_printf("theta = %Ps\n", form->theta);
+
+ GEN G = gcdii(D, stoi(3));
+ pari_printf("G = %Pi\n", G);
+
+ GEN bl = mulii(form->B, form->L);
+
+ GEN lmbl = gpow(form->lambda, negi(bl), BIGDEFAULTPREC);
+ pari_printf("lmbl = %Ps\n", lmbl);
+
+ GEN mi6 = gneg(gdiv(stoi(form->I), stoi(6)));
+ GEN powmi6 = gpow(gen_2, mi6, BIGDEFAULTPREC);
+ pari_printf("powmi6 = %Ps\n", powmi6);
+
+ GEN f = gen_0;
+ switch (form->J) {
+ case 0:
+ f = p1363_func_fzero(D, form);
+ break;
+ case 1:
+ f = p1363_func_fone(D, form);
+ break;
+ case 2:
+ f = p1363_func_ftwo(D, form);
+ break;
+ default:
+ pari_err_DOMAIN("p1363_invariant", "J", ">", stoi(2),
+ stoi(form->J));
+ }
+
+ pari_printf("f = %Ps\n", f);
+
+ GEN fK = gpow(f, stoi(form->K), BIGDEFAULTPREC);
+ pari_printf("fK = %Ps\n", fK);
+
+ GEN in = gmul(lmbl, powmi6);
+ pari_printf("in = %Ps\n", in);
+ GEN inner = gmul(gmul(form->N, in), fK);
+ pari_printf("inner = %Ps\n", inner);
+ GEN result = gpow(inner, G, BIGDEFAULTPREC);
+ pari_printf("result = %Ps\n", result);
+
+ return gerepilecopy(ltop, result);
+}
+
+GEN p1363_poly(GEN D, form_t **forms, size_t nforms) {
+ pari_sp ltop = avma;
+ long v = fetch_var();
+ name_var(v, "t");
+
+ GEN terms = gtovec0(gen_0, nforms);
+ for (size_t i = 0; i < nforms; ++i) {
+ gel(terms, i + 1) = gsub(pol_x(v), p1363_invariant(D, forms[i]));
+ }
+
+ GEN result = gen_1;
+ for (size_t i = 0; i < nforms; ++i) {
+ gmulz(result, gel(terms, i + 1), result);
+ }
+ return gerepilecopy(ltop, result);
+}
diff --git a/src/cm/p1363.h b/src/cm/p1363.h
new file mode 100644
index 0000000..e5c9fbd
--- /dev/null
+++ b/src/cm/p1363.h
@@ -0,0 +1,39 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+/**
+ * @file p1363.h
+ */
+#ifndef ECGEN_P1363_H
+#define ECGEN_P1363_H
+
+#include <pari/pari.h>
+
+typedef struct form_t {
+ GEN A;
+ GEN B;
+ GEN C;
+
+ long m8;
+
+ long I;
+ long J;
+ long K;
+ GEN L;
+ GEN M;
+ GEN N;
+
+ GEN lambda;
+ GEN theta;
+} form_t;
+
+size_t p1363_forms(GEN D, form_t ***forms);
+
+void p1363_free(form_t ***forms, size_t nforms);
+
+GEN p1363_invariant(GEN D, form_t *form);
+
+GEN p1363_poly(GEN D, form_t **forms, size_t nforms);
+
+#endif // ECGEN_P1363_H
diff --git a/src/exhaustive/anomalous.c b/src/exhaustive/anomalous.c
new file mode 100644
index 0000000..c87d61c
--- /dev/null
+++ b/src/exhaustive/anomalous.c
@@ -0,0 +1,156 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+/**
+ * @file anomalous.c
+ */
+#include "anomalous.h"
+#include <io/config.h>
+#include <math/types.h>
+
+static disc_t **disc_table;
+
+void anomalous_init() {
+ disc_table = pari_malloc(sizeof(disc_t *) * 5);
+ if (!disc_table) {
+ perror("Couldn't malloc.");
+ exit(1);
+ }
+ for (int i = 0; i < 5; ++i) {
+ disc_table[i] = pari_malloc(sizeof(disc_t));
+ if (!disc_table[i]) {
+ perror("Couldn't malloc.");
+ exit(1);
+ }
+ }
+
+ /*
+ * Discriminant, j-invariant and field-element (Alpha) from Atsuko Miyaji's
+ * paper.
+ */
+ GEN a = stoi(-32);
+ GEN b = stoi(-64);
+ disc_table[0]->d = stoi(11);
+ disc_table[0]->j = powis(a, 3);
+ disc_table[0]->alpha = stoi(21);
+ disc_table[1]->d = stoi(19);
+ disc_table[1]->j = powis(mulis(a, 3), 3);
+ disc_table[1]->alpha = stoi(3);
+ disc_table[2]->d = stoi(43);
+ disc_table[2]->j = powis(mulis(b, 16), 3);
+ disc_table[2]->alpha = stoi(70);
+ disc_table[3]->d = stoi(67);
+ disc_table[3]->j = powis(mulis(a, 165), 3);
+ disc_table[3]->alpha = stoi(35805);
+ disc_table[3]->d = stoi(163);
+ disc_table[3]->j = powis(mulis(b, 10005), 3);
+ disc_table[3]->alpha = stoi(3717878010);
+}
+
+static GEN anomalous_prime(size_t i, unsigned long bits) {
+ GEN D = disc_table[i]->d;
+
+ pari_sp ltop = avma;
+ GEN last = divis(addis(D, 1), 4);
+ GEN lower = divii(subii(int2n(bits - 1), last), D);
+ GEN upper = divii(subii(int2n(bits), last), D);
+
+ GEN lower_bound = gceil(gdiv(
+ gsub(gsqrt(addis(mulis(lower, 4), 1), BIGDEFAULTPREC), gen_1), gen_2));
+ GEN upper_bound = gfloor(gdiv(
+ gsub(gsqrt(addis(mulis(upper, 4), 1), BIGDEFAULTPREC), gen_1), gen_2));
+
+ GEN range = gtovec0(gen_0, 2);
+ gel(range, 1) = lower_bound;
+ gel(range, 2) = upper_bound;
+ GEN first, middle;
+ GEN p, b;
+
+ pari_sp btop = avma;
+ do {
+ b = genrand(range);
+ middle = mulii(D, b);
+ first = mulii(middle, b);
+ p = addii(addii(first, middle), last);
+ gerepileall(btop, 2, &p, &last);
+ } while (!isprime(p));
+
+ return gerepilecopy(ltop, p);
+}
+
+static GEN anomalous_c(size_t i, GEN p) {
+ pari_sp ltop = avma;
+ long kroneck = kronecker(disc_table[i]->alpha, p);
+ if (!kroneck) {
+ return NULL;
+ }
+ long cp = -kroneck;
+
+ GEN c;
+ pari_sp btop = avma;
+ do {
+ c = genrand(p);
+ gerepileall(btop, 1, &c);
+ } while (kronecker(c, p) != cp);
+
+ return gerepilecopy(ltop, c);
+}
+
+int anomalous_field(curve_t *curve, const config_t *cfg, arg_t *args) {
+ if (!args) {
+ fprintf(stderr, "No args to an arged function. anomalous_field\n");
+ return INT_MIN;
+ }
+ size_t i = *(size_t *)args->args;
+
+ // find suitable prime field
+ pari_sp ltop = avma;
+ GEN p;
+ do {
+ p = anomalous_prime(i, cfg->bits);
+ gerepileall(ltop, 1, &p);
+ } while (!kronecker(disc_table[0]->alpha, p));
+
+ curve->field = gerepilecopy(ltop, p);
+ return 1;
+}
+
+int anomalous_equation(curve_t *curve, const config_t *cfg, arg_t *args) {
+ if (!args) {
+ fprintf(stderr, "No args to an arged function. anomalous_equation\n");
+ return INT_MIN;
+ }
+ size_t i = *(size_t *)args->args;
+
+ // 1 on success, -2 on failure
+ pari_sp ltop = avma;
+ GEN c = anomalous_c(i, curve->field);
+
+ GEN a_upper = gmodulo(disc_table[i]->j, curve->field);
+ GEN a_lower = gmodulo(subsi(1728, disc_table[i]->j), curve->field);
+ GEN a = gdiv(a_upper, a_lower);
+
+ curve->a = gmul(stoi(3), gmul(gsqr(c), a));
+ curve->b = gmul(gen_2, gmul(gpowgs(c, 3), a));
+ gerepileall(ltop, 2, &curve->a, &curve->b);
+ return 1;
+}
+
+int anomalous_order(curve_t *curve, const config_t *cfg, arg_t *args) {
+ // copy field to order
+ curve->order = gcopy(curve->field);
+ obj_insert(curve->curve, 1, curve->order);
+ return 1;
+}
+
+void anomalous_quit() {
+ if (disc_table) {
+ for (int i = 0; i < 5; ++i) {
+ if (disc_table[i]) {
+ pari_free(disc_table[i]);
+ }
+ }
+ pari_free(disc_table);
+ }
+}
diff --git a/src/exhaustive/anomalous.h b/src/exhaustive/anomalous.h
new file mode 100644
index 0000000..ac86018
--- /dev/null
+++ b/src/exhaustive/anomalous.h
@@ -0,0 +1,32 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+/**
+ * @file anomalous.h
+ */
+#ifndef ECGEN_ANOMALOUS_H
+#define ECGEN_ANOMALOUS_H
+
+#include <pari/pari.h>
+#include "io/cli.h"
+#include "math/arg.h"
+#include "math/types.h"
+
+typedef struct disc_t {
+ GEN d;
+ GEN j;
+ GEN alpha;
+} disc_t;
+
+int anomalous_field(curve_t *curve, const config_t *cfg, arg_t *args);
+
+int anomalous_equation(curve_t *curve, const config_t *cfg, arg_t *args);
+
+int anomalous_order(curve_t *curve, const config_t *cfg, arg_t *args);
+
+void anomalous_init();
+
+void anomalous_quit();
+
+#endif // ECGEN_ANOMALOUS_H
diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c
index e0fde07..3e0209f 100644
--- a/src/exhaustive/exhaustive.c
+++ b/src/exhaustive/exhaustive.c
@@ -3,6 +3,9 @@
* Copyright (C) 2017 J08nY
*/
#include "exhaustive.h"
+#include <io/config.h>
+#include <math/types.h>
+#include "anomalous.h"
#include "io/output.h"
#include "math/arg.h"
#include "math/curve.h"
@@ -30,7 +33,10 @@ static void exhaustive_ginit(gen_t *generators, const config_t *cfg) {
} else {
generators[OFFSET_SEED] = &gen_skip;
- if (cfg->random) {
+ if (cfg->anomalous) {
+ generators[OFFSET_A] = &gen_skip;
+ generators[OFFSET_B] = &anomalous_equation;
+ } else if (cfg->random) {
generators[OFFSET_A] = &a_random;
generators[OFFSET_B] = &b_random;
} else {
@@ -48,6 +54,8 @@ static void exhaustive_ginit(gen_t *generators, const config_t *cfg) {
generators[OFFSET_ORDER] = &order_prime;
} else if (cfg->cofactor) {
generators[OFFSET_ORDER] = &order_smallfact;
+ } else if (cfg->anomalous) {
+ generators[OFFSET_ORDER] = &anomalous_order;
} else {
generators[OFFSET_ORDER] = &order_any;
}
@@ -58,7 +66,9 @@ static void exhaustive_ginit(gen_t *generators, const config_t *cfg) {
generators[OFFSET_GENERATORS] = &gens_any;
}
- if (cfg->random) {
+ if (cfg->anomalous) {
+ generators[OFFSET_FIELD] = &anomalous_field;
+ } else if (cfg->random) {
generators[OFFSET_FIELD] = &field_random;
} else {
generators[OFFSET_FIELD] = &field_input;
@@ -85,6 +95,19 @@ static void exhaustive_ainit(arg_t **argss, const config_t *cfg) {
for (size_t i = 0; i < OFFSET_END; ++i) {
argss[i] = NULL;
}
+ if (cfg->anomalous) {
+ arg_t *field_arg = arg_new();
+ arg_t *eq_arg = arg_new();
+ size_t *i = pari_malloc(sizeof(size_t));
+ *i = 3;
+ field_arg->args = i;
+ field_arg->nargs = 1;
+ eq_arg->args = i;
+ eq_arg->nargs = 1;
+ eq_arg->mallocd = i;
+ argss[OFFSET_FIELD] = field_arg;
+ argss[OFFSET_B] = eq_arg;
+ }
if (cfg->points.type == POINTS_RANDOM) {
arg_t *points_arg = arg_new();
points_arg->args = &cfg->points.amount;
@@ -151,7 +174,7 @@ int exhaustive_gen_retry(curve_t *curve, const config_t *cfg,
avma = tops[new_state - start_offset];
}
- if (diff == 0) {
+ if (diff <= 0) {
int tried = ++tries[state - start_offset];
if (retry && tried >= retry) {
fprintf(stderr, "Reached retry limit: %i, state = %i\n", retry,
@@ -186,8 +209,11 @@ int exhaustive_gen(curve_t *curve, const config_t *cfg, gen_t generators[],
start_offset, end_offset, 0);
}
+static void exhaustive_init() { anomalous_init(); }
+
static void exhaustive_quit(arg_t *argss[]) {
equation_quit();
+ anomalous_quit();
for (size_t i = 0; i < OFFSET_END; ++i) {
if (argss[i]) {
arg_free(&(argss[i]));
@@ -204,6 +230,7 @@ int exhaustive_do(config_t *cfg) {
exhaustive_ginit(generators, cfg);
exhaustive_ainit(argss, cfg);
exhaustive_uinit(unrolls, cfg);
+ exhaustive_init();
output_o_begin(cfg);
for (unsigned long i = 0; i < cfg->count; ++i) {
diff --git a/src/exhaustive/seed.c b/src/exhaustive/seed.c
index bd6f274..d35fc05 100644
--- a/src/exhaustive/seed.c
+++ b/src/exhaustive/seed.c
@@ -61,15 +61,38 @@ static GEN seed_stoi(const char *cstr) {
return gerepilecopy(ltop, seed);
}
+char *seed_itos(GEN seed) {
+ pari_sp ltop = avma;
+ GEN bits = binary_zv(seed);
+
+ long len = glength(bits);
+ long bytes = (len / 8) + (len % 8 == 0 ? 0 : 1);
+ char *result = pari_malloc((size_t)bytes);
+ if (!result) {
+ perror("Couldn't malloc.");
+ exit(1);
+ }
+
+ for (long i = 0; i < len; ++i) {
+ // TODO
+ }
+ avma = ltop;
+ return result;
+}
+
int seed_random(curve_t *curve, const config_t *cfg, arg_t *args) {
curve->seed = seed_new();
curve->seed->seed = random_int(160);
+ curve->seed->raw = seed_itos(curve->seed->seed);
+ curve->seed->raw_len = strlen(curve->seed->raw);
return 1;
}
int seed_argument(curve_t *curve, const config_t *cfg, arg_t *args) {
curve->seed = seed_new();
curve->seed->seed = seed_stoi(cfg->seed);
+ curve->seed->raw = cfg->seed;
+ curve->seed->raw_len = strlen(cfg->seed);
return 1;
}
diff --git a/src/io/cli.c b/src/io/cli.c
index 21eeb56..cc2f156 100644
--- a/src/io/cli.c
+++ b/src/io/cli.c
@@ -33,7 +33,8 @@ enum opt_keys {
OPT_F2M,
OPT_POINTS,
OPT_THREADS,
- OPT_TSTACK
+ OPT_TSTACK,
+ OPT_ANOMALOUS
};
// clang-format off
@@ -45,12 +46,13 @@ struct argp_option options[] = {
{"random", OPT_RANDOM, 0, 0, "Generate a random curve (using Random approach).", 2},
{"prime", OPT_PRIME, 0, 0, "Generate a curve with prime order.", 2},
{"cofactor", OPT_COFACTOR, "BOUND", 0, "Generate a curve with cofactor up to BOUND.", 2},
- {"seed", OPT_SEED, "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (ANSI X9.62 verifiable procedure).", 2},
- {"invalid", OPT_INVALID, 0, 0, "Generate a set of invalid curves, for a given curve (using Invalid curve algorithm).", 2},
- {"order", OPT_ORDER, "ORDER", 0, "Generate a curve with given order (using Complex Multiplication).", 2},
{"koblitz", OPT_KOBLITZ, 0, 0, "Generate a Koblitz curve (a = 0).", 2},
{"unique", OPT_UNIQUE, 0, 0, "Generate a curve with only one generator.", 2},
+ {"anomalous",OPT_ANOMALOUS,0, 0, "Generate an anomalous curve (of trace one, with field order equal to curve order).", 2},
{"points", OPT_POINTS, "TYPE", 0, "Generate points of given type (random/prime/none).", 2},
+ {"seed", OPT_SEED, "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (ANSI X9.62 verifiable procedure).", 2},
+ {"invalid", OPT_INVALID, 0, 0, "Generate a set of invalid curves, for a given curve (using Invalid curve algorithm).", 2},
+ {"order", OPT_ORDER, "ORDER", 0, "Generate a curve with given order (using Complex Multiplication).", 2},
{"count", OPT_COUNT, "COUNT", 0, "Generate multiple curves.", 2},
{0, 0, 0, 0, "Input/Output options:", 3},
{"format", OPT_FORMAT, "FORMAT", 0, "Format to output in. One of [csv,json], default is json.", 3},
@@ -178,6 +180,9 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) {
case OPT_UNIQUE:
cfg->unique = true;
break;
+ case OPT_ANOMALOUS:
+ cfg->anomalous = true;
+ break;
case OPT_POINTS:
if (arg) {
if (strstr(arg, "random")) {
@@ -240,13 +245,23 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) {
"from seed, exhaustive or prime order.");
}
if (cfg->cm && (cfg->prime || cfg->from_seed || cfg->invalid ||
- cfg->cofactor)) {
+ cfg->cofactor || cfg->anomalous)) {
argp_failure(state, 1, 0,
"Fixed order curve generation can not generate "
"curves from seed, or invalid curves. Prime order "
"also doesn't make sense if the given one isn't "
"prime.");
}
+ if (cfg->anomalous &&
+ (cfg->binary_field || cfg->cofactor || cfg->from_seed ||
+ cfg->cm || cfg->invalid || cfg->koblitz)) {
+ argp_failure(
+ state, 1, 0,
+ "Anomalous curve generation can not generate "
+ "binary field curves, curves with a cofactor, from seed "
+ "with fixed order, invalid or Koblitz curves.");
+ }
+
// default values
if (!cfg->count) {
cfg->count = 1;
diff --git a/src/io/cli.h b/src/io/cli.h
index 82dcf4b..c670328 100644
--- a/src/io/cli.h
+++ b/src/io/cli.h
@@ -9,6 +9,7 @@
#define ECGEN_CLI_H
#include <argp.h>
+#include <stdbool.h>
#include <stdlib.h>
extern char doc[];
diff --git a/src/io/config.h b/src/io/config.h
index 70018a9..426661c 100644
--- a/src/io/config.h
+++ b/src/io/config.h
@@ -24,12 +24,13 @@ typedef struct {
bool binary_field;
bool prime_field;
- unsigned long count;
+ long count;
bool random;
bool prime;
bool invalid;
bool cm;
char *order;
+ bool anomalous;
bool koblitz;
bool cofactor;
long cofactor_bound;
diff --git a/src/math/arg.c b/src/math/arg.c
index e313adb..d2eba9b 100644
--- a/src/math/arg.c
+++ b/src/math/arg.c
@@ -16,6 +16,10 @@ arg_t *arg_new(void) {
void arg_free(arg_t **arg) {
if (*arg) {
+ if ((*arg)->mallocd) {
+ pari_free((*arg)->mallocd);
+ (*arg)->mallocd = NULL;
+ }
pari_free(*arg);
*arg = NULL;
}
diff --git a/src/math/types.h b/src/math/types.h
index 96103e5..64b9c99 100644
--- a/src/math/types.h
+++ b/src/math/types.h
@@ -15,7 +15,11 @@
/**
* @brief
*/
-typedef struct { GEN seed; } seed_t;
+typedef struct seed_t {
+ char *raw;
+ size_t raw_len;
+ GEN seed;
+} seed_t;
/**
* @brief A point type.
@@ -76,6 +80,7 @@ typedef enum {
typedef struct {
const void *args;
size_t nargs;
+ void *mallocd;
} arg_t;
/**
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 22:25:13 +0000