Begin CM work

4 files changed, 169 insertions, 2 deletions

diff --git a/src/exhaustive/anomalous.c b/src/exhaustive/anomalous.c
new file mode 100644
index 0000000..fea27ed
--- /dev/null
+++ b/src/exhaustive/anomalous.c
@@ -0,0 +1,100 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+/**
+ * @file anomalous.c
+ */
+#include "anomalous.h"
+#include "math/random.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]->a = stoi(21);
+	disc_table[1]->D = stoi(19);
+	disc_table[1]->j = powis(mulis(a, 3), 3);
+	disc_table[1]->a = stoi(3);
+	disc_table[2]->D = stoi(43);
+	disc_table[2]->j = powis(mulis(b, 16), 3);
+	disc_table[2]->a = stoi(70);
+	disc_table[3]->D = stoi(67);
+	disc_table[3]->j = powis(mulis(a, 165), 3);
+	disc_table[3]->a = stoi(35805);
+	disc_table[3]->D = stoi(163);
+	disc_table[3]->j = powis(mulis(b, 10005), 3);
+	disc_table[3]->a = stoi(3717878010);
+}
+
+static GEN anomalous_prime(GEN D, const config_t *cfg) {
+	pari_sp ltop = avma;
+	GEN last = divis(addis(D, 1), 4);
+	GEN middle;
+	GEN first;
+	GEN p;
+	GEN b;
+
+	do {
+		b = random_int(cfg->bits);
+		middle = mulii(D, b);
+		first = mulii(middle, b);
+		p = addii(addii(first, middle), last);
+		if (gc_needed(ltop, 1)) {
+			gerepileall(ltop, 2, &p, &last);
+		}
+	} while (!isprime(p));
+
+	// TODO: this does not give me a bits sized prime..
+	// but quite a larger one
+	return gerepilecopy(ltop, p);
+}
+
+int anomalous_field(curve_t *curve, const config_t *cfg, arg_t *args) {
+	// find suitable prime field
+	curve->field = anomalous_prime(disc_table[0]->D, cfg);
+	return 1;
+}
+
+int anomalous_equation(curve_t *curve, const config_t *cfg, arg_t *args) {
+	// 1 on success, -2 on failure
+	pari_sp ltop = avma;
+	return INT_MIN;  // TODO this
+}
+
+int anomalous_order(curve_t *curve, const config_t *cfg, arg_t *args) {
+	// copy field to order
+	curve->order = gcopy(curve->field);
+	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..eff4686
--- /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 a;
+} 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 9202c7a..5e2fcc8 100644
--- a/src/exhaustive/exhaustive.c
+++ b/src/exhaustive/exhaustive.c
@@ -3,6 +3,7 @@
  * Copyright (C) 2017 J08nY
  */
 #include "exhaustive.h"
+#include "anomalous.h"
 #include "io/output.h"
 #include "math/arg.h"
 #include "math/curve.h"
@@ -30,7 +31,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 +52,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 +64,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;
@@ -186,8 +194,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 +215,7 @@ int exhaustive_do(config_t *cfg) {
 	exhaustive_ginit(generators, cfg);
 	exhaustive_ainit(argss, cfg);
 	exhaustive_uinit(unrolls, cfg);
+	exhaustive_init();
 
 	for (unsigned long i = 0; i < cfg->count; ++i) {
 		curve_t *curve = curve_new();
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;
 }