8 files changed, 182 insertions, 50 deletions

diff --git a/src/exhaustive/brainpool.c b/src/exhaustive/brainpool.c
index d7f0c59..3debaec 100644
--- a/src/exhaustive/brainpool.c
+++ b/src/exhaustive/brainpool.c
@@ -4,6 +4,9 @@
  */
 
 #include "brainpool.h"
+#include <misc/types.h>
+#include "gen/gens.h"
+#include "gen/point.h"
 #include "gen/seed.h"
 #include "io/output.h"
 #include "util/bits.h"
@@ -155,7 +158,8 @@ GENERATOR(brainpool_gen_equation) {
 			avma = btop;
 			continue;
 		}
-		z = Fp_sqrtn(Fp_muls(am, -1, curve->field), stoi(4), curve->field, NULL);
+		z = Fp_sqrtn(Fp_muls(am, -1, curve->field), stoi(4), curve->field,
+		             NULL);
 		if (z == NULL) {
 			brainpool_update_seed(seed->seed);
 			avma = btop;
@@ -189,13 +193,6 @@ GENERATOR(brainpool_gen_equation) {
 			continue;
 		}
 
-		brainpool_update_seed(seed->seed);
-		seed->brainpool.seed_bp = bits_copy(seed->seed);
-
-		bits_t *mult_bits =
-		    brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
-		seed->brainpool.mult = bits_to_i(mult_bits);
-
 		curve->a = mod_a;
 		curve->b = mod_b;
 		gerepileall(btop, 2, &curve->a, &curve->b);
@@ -204,4 +201,64 @@ GENERATOR(brainpool_gen_equation) {
 
 	seed->brainpool.update_seed = true;
 	return 1;
+}
+
+GENERATOR(brainpool_gen_gens) {
+	pari_sp ltop = avma;
+	seed_t *seed = curve->seed;
+	brainpool_update_seed(seed->seed);
+
+	bits_t *k_bits =
+	    brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
+	GEN k = bits_to_i(k_bits);
+	bits_free(&k_bits);
+	GEN x = gen_0;
+	GEN Qy = ellordinate(curve->curve, x, 0);
+	while (glength(Qy) == 0) {
+		mpaddz(x, gen_1, x);
+		Qy = ellordinate(curve->curve, x, 0);
+	}
+
+	GEN P = NULL;
+	if (glength(Qy) == 1) {
+		P = mkvec2(x, gel(Qy, 1));
+	} else if (glength(Qy) == 2) {
+		if (random_bits(1)) {
+			P = mkvec2(x, gel(Qy, 1));
+		} else {
+			P = mkvec2(x, gel(Qy, 2));
+		}
+	} else {
+		avma = ltop;
+		return INT_MIN;
+	}
+
+	curve->generators = points_new(1);
+	point_t *G = point_new();
+	curve->generators[0] = G;
+	G->point = gerepilecopy(ltop, ellmul(curve->curve, P, k));
+	G->order = ellorder(curve->curve, G->point, NULL);
+	G->cofactor = divii(curve->order, G->order);
+
+	return 1;
+}
+
+CHECK(brainpool_check_gens) {
+	pari_sp ltop = avma;
+	point_t *G = curve->generators[0];
+	GEN min_degree = divis(subii(G->order, gen_1), 100);
+	if (mpcmp(min_degree, gens_get_embedding(curve->field, G->order)) >= 0) {
+		avma = ltop;
+		return -5;
+	}
+	avma = ltop;
+	return 1;
+}
+
+CHECK(brainpool_check_order) {
+	if (mpcmp(curve->order, curve->field) < 0) {
+		return 1;
+	} else {
+		return -4;
+	}
 }
\ No newline at end of file
diff --git a/src/exhaustive/brainpool.h b/src/exhaustive/brainpool.h
index 741bf2f..0b19fa3 100644
--- a/src/exhaustive/brainpool.h
+++ b/src/exhaustive/brainpool.h
@@ -58,7 +58,7 @@ GENERATOR(brainpool_gen_seed_argument);
 GENERATOR(brainpool_gen_seed_input);
 
 /**
- *
+ * @brief
  * @param curve
  * @param args
  * @param state
@@ -75,4 +75,31 @@ GENERATOR(brainpool_gen_field);
  */
 GENERATOR(brainpool_gen_equation);
 
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_gen_gens);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+CHECK(brainpool_check_gens);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+CHECK(brainpool_check_order);
+
 #endif  // ECGEN_BRAINPOOL_H
diff --git a/src/exhaustive/brainpool_rfc.c b/src/exhaustive/brainpool_rfc.c
index 1a9fea9..921dff3 100644
--- a/src/exhaustive/brainpool_rfc.c
+++ b/src/exhaustive/brainpool_rfc.c
@@ -33,34 +33,46 @@ GENERATOR(brainpool_rfc_gen_equation) {
 	// field is definitely prime
 	pari_sp btop = avma;
 	seed_t *seed = curve->seed;
+	pari_printf("seed before %P#x\n", bits_to_i(seed->seed));
 	do {
 		if (seed->brainpool.update_seed) {
+			printf("updating seed\n");
 			brainpool_update_seed(seed->seed);
+			pari_printf("seed after %P#x\n", bits_to_i(seed->seed));
 			seed->brainpool.update_seed = false;
 		}
 
-		GEN z;
 		bits_t *a_bits =
 		    brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
 		GEN a = bits_to_i(a_bits);
+		pari_printf("trying a = '%P#x'\n", a);
 		bits_free(&a_bits);
 		GEN am = Fp_invsafe(a, curve->field);
 		if (am == NULL) {
 			brainpool_update_seed(seed->seed);
+			pari_printf("a, update seed(noinv) %P#x\n", bits_to_i(seed->seed));
 			avma = btop;
 			continue;
 		}
-		z = Fp_sqrtn(Fp_muls(am, -1, curve->field), stoi(4), curve->field, NULL);
+		GEN z;
+		z = Fp_sqrtn(Fp_muls(am, -3, curve->field), stoi(4), curve->field,
+		             NULL);
 		if (z == NULL) {
 			brainpool_update_seed(seed->seed);
+			pari_printf("a, update seed(sqrtn) %P#x\n", bits_to_i(seed->seed));
 			avma = btop;
 			continue;
 		}
 		seed->brainpool.seed_a = bits_copy(seed->seed);
 
-		GEN b;
+		GEN b = NULL;
+		pari_sp bbtop = avma;
 		do {
+			if (b != NULL) {
+				avma = bbtop;
+			}
 			brainpool_update_seed(seed->seed);
+			pari_printf("b, update seed %P#x\n", bits_to_i(seed->seed));
 			bits_t *b_bits = brainpool_hash(seed->seed, seed->brainpool.w,
 			                                seed->brainpool.v);
 			b = bits_to_i(b_bits);
@@ -75,19 +87,13 @@ GENERATOR(brainpool_rfc_gen_equation) {
 		if (gequal0(gmulsg(-16, gadd(gmulsg(4, gpowgs(mod_a, 3)),
 		                             gmulsg(27, gsqr(mod_b)))))) {
 			brainpool_update_seed(seed->seed);
+			pari_printf("curve, update seed %P#x\n", bits_to_i(seed->seed));
 			bits_free(&seed->brainpool.seed_a);
 			bits_free(&seed->brainpool.seed_b);
 			avma = btop;
 			continue;
 		}
 
-		brainpool_update_seed(seed->seed);
-		seed->brainpool.seed_bp = bits_copy(seed->seed);
-
-		bits_t *mult_bits =
-		    brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
-		seed->brainpool.mult = bits_to_i(mult_bits);
-
 		curve->a = mod_a;
 		curve->b = mod_b;
 		gerepileall(btop, 2, &curve->a, &curve->b);
@@ -96,4 +102,4 @@ GENERATOR(brainpool_rfc_gen_equation) {
 
 	seed->brainpool.update_seed = true;
 	return 1;
-}
\ No newline at end of file
+}
diff --git a/src/exhaustive/brainpool_rfc.h b/src/exhaustive/brainpool_rfc.h
index c838419..8a27410 100644
--- a/src/exhaustive/brainpool_rfc.h
+++ b/src/exhaustive/brainpool_rfc.h
@@ -9,7 +9,7 @@
 #include "misc/types.h"
 
 /**
- *
+ * @brief
  * @param curve
  * @param args
  * @param state
@@ -18,7 +18,7 @@
 GENERATOR(brainpool_rfc_gen_seed_argument);
 
 /**
- *
+ * @brief
  * @param curve
  * @param args
  * @param state
@@ -27,7 +27,7 @@ GENERATOR(brainpool_rfc_gen_seed_argument);
 GENERATOR(brainpool_rfc_gen_seed_random);
 
 /**
- *
+ * @brief
  * @param curve
  * @param args
  * @param state
diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c
index ee475ff..71d5442 100644
--- a/src/exhaustive/exhaustive.c
+++ b/src/exhaustive/exhaustive.c
@@ -40,6 +40,14 @@ void exhaustive_clear(exhaustive_t *setup) {
 
 static void exhaustive_ginit(gen_f *generators) {
 	if (cfg->seed_algo) {
+		if (cfg->prime) {
+			generators[OFFSET_ORDER] = &order_gen_prime;
+		} else if (cfg->cofactor) {
+			generators[OFFSET_ORDER] = &order_gen_smallfact;
+		} else {
+			generators[OFFSET_ORDER] = &order_gen_any;
+		}
+
 		switch (cfg->seed_algo) {
 			case SEED_ANSI: {
 				// setup ANSI X9.62 generators
@@ -52,13 +60,13 @@ static void exhaustive_ginit(gen_f *generators) {
 						generators[OFFSET_SEED] = &ansi_gen_seed_input;
 					}
 				}
-				generators[OFFSET_A] = &gen_skip;
-				generators[OFFSET_B] = &ansi_gen_equation;
 				if (cfg->random) {
 					generators[OFFSET_FIELD] = &field_gen_random;
 				} else {
 					generators[OFFSET_FIELD] = &field_gen_input;
 				}
+				generators[OFFSET_A] = &gen_skip;
+				generators[OFFSET_B] = &ansi_gen_equation;
 			} break;
 			case SEED_BRAINPOOL: {
 				if (cfg->seed) {
@@ -73,6 +81,8 @@ static void exhaustive_ginit(gen_f *generators) {
 				generators[OFFSET_FIELD] = &brainpool_gen_field;
 				generators[OFFSET_A] = &gen_skip;
 				generators[OFFSET_B] = &brainpool_gen_equation;
+				generators[OFFSET_ORDER] = &order_gen_prime;
+				generators[OFFSET_GENERATORS] = &brainpool_gen_gens;
 			} break;
 			case SEED_BRAINPOOL_RFC: {
 				if (cfg->seed) {
@@ -88,20 +98,14 @@ static void exhaustive_ginit(gen_f *generators) {
 				generators[OFFSET_FIELD] = &brainpool_gen_field;
 				generators[OFFSET_A] = &gen_skip;
 				generators[OFFSET_B] = &brainpool_rfc_gen_equation;
+				generators[OFFSET_ORDER] = &order_gen_prime;
+				generators[OFFSET_GENERATORS] = &brainpool_gen_gens;
 			} break;
 			case SEED_FIPS:
 				break;
 			default:
 				break;
 		}
-
-		if (cfg->prime) {
-			generators[OFFSET_ORDER] = &order_gen_prime;
-		} else if (cfg->cofactor) {
-			generators[OFFSET_ORDER] = &order_gen_smallfact;
-		} else {
-			generators[OFFSET_ORDER] = &order_gen_any;
-		}
 	} else {
 		// setup normal generators
 		generators[OFFSET_SEED] = &gen_skip;
@@ -148,16 +152,16 @@ static void exhaustive_ginit(gen_f *generators) {
 		} else {
 			generators[OFFSET_FIELD] = &field_gen_input;
 		}
+
+		if (cfg->unique) {
+			generators[OFFSET_GENERATORS] = &gens_gen_one;
+		} else {
+			generators[OFFSET_GENERATORS] = &gens_gen_any;
+		}
 	}
 	// setup common generators
 	generators[OFFSET_CURVE] = &curve_gen_any;
 
-	if (cfg->unique) {
-		generators[OFFSET_GENERATORS] = &gens_gen_one;
-	} else {
-		generators[OFFSET_GENERATORS] = &gens_gen_any;
-	}
-
 	switch (cfg->points.type) {
 		case POINTS_RANDOM:
 			if (cfg->points.amount) {
@@ -189,6 +193,25 @@ static void exhaustive_cinit(check_t **validators) {
 		check_t *hex_check = check_new(hex_check_param, NULL);
 		validators[OFFSET_POINTS] = hex_check;
 	}
+
+	if (cfg->method == METHOD_SEED) {
+		switch (cfg->seed_algo) {
+			case SEED_ANSI:
+				break;
+			case SEED_BRAINPOOL:
+			case SEED_BRAINPOOL_RFC: {
+				check_t *order_check = check_new(brainpool_check_order, NULL);
+				validators[OFFSET_ORDER] = order_check;
+				check_t *gens_check =
+				    check_new(gens_check_anomalous, brainpool_check_gens, NULL);
+				validators[OFFSET_GENERATORS] = gens_check;
+			} break;
+			case SEED_FIPS:
+				break;
+			default:
+				break;
+		}
+	}
 }
 
 static void exhaustive_ainit(arg_t **gen_argss, arg_t **check_argss) {
@@ -205,12 +228,14 @@ static void exhaustive_ainit(arg_t **gen_argss, arg_t **check_argss) {
 		gen_argss[OFFSET_FIELD] = field_arg;
 		gen_argss[OFFSET_B] = eq_arg;
 	}
+
 	if (cfg->points.type == POINTS_RANDOM) {
 		arg_t *points_arg = arg_new();
 		points_arg->args = &cfg->points.amount;
 		points_arg->nargs = 1;
 		gen_argss[OFFSET_POINTS] = points_arg;
 	}
+
 	if (cfg->cofactor) {
 		arg_t *order_arg = arg_new();
 		arg_t *gens_arg = arg_new();
@@ -278,6 +303,7 @@ int exhaustive_gen_retry(curve_t *curve, const exhaustive_t *setup,
 		}
 		timeout_stop();
 		if (diff > 0 && setup->validators && setup->validators[state]) {
+			pari_sp ctop = avma;
 			check_t *validator = setup->validators[state];
 			for (size_t i = 0; i < validator->nchecks; ++i) {
 				int new_diff =
@@ -287,6 +313,7 @@ int exhaustive_gen_retry(curve_t *curve, const exhaustive_t *setup,
 					break;
 				}
 			}
+			avma = ctop;
 		}
 
 		int new_state = state + diff;
diff --git a/src/gen/gens.c b/src/gen/gens.c
index 2cffbc4..e2c624e 100644
--- a/src/gen/gens.c
+++ b/src/gen/gens.c
@@ -40,16 +40,25 @@ GENERATOR(gens_gen_one) {
 
 CHECK(gens_check_anomalous) {
 	if (cfg->field == FIELD_BINARY) return 1;
-	pari_sp ltop = avma;
 	for (size_t i = 0; i < curve->ngens; ++i) {
 		if (mpcmp(curve->field, curve->generators[i]->order) == 0) {
-			avma = ltop;
 			return -5;
 		}
 	}
 	return 1;
 }
 
+GEN gens_get_embedding(GEN prime, GEN order) {
+	pari_sp ltop = avma;
+	GEN power = gen_1;
+	GEN pm;
+	do {
+		power = mulii(power, prime);
+		pm = subii(power, gen_1);
+	} while (!dvdii(pm, order));
+	return gerepilecopy(ltop, power);
+}
+
 CHECK(gens_check_embedding) {
 	HAS_ARG(args);
 	if (cfg->field == FIELD_BINARY) return 1;
@@ -59,13 +68,8 @@ CHECK(gens_check_embedding) {
 	GEN mind = strtoi(min_degree);
 
 	for (size_t i = 0; i < curve->ngens; ++i) {
-		GEN power = gen_0;
-		GEN pm;
-		do {
-			power = addii(power, gen_1);
-			GEN ppow = powii(curve->field, power);
-			pm = subii(ppow, gen_1);
-		} while (!dvdii(pm, curve->generators[i]->order));
+		GEN power =
+		    gens_get_embedding(curve->field, curve->generators[i]->order);
 
 		if (mpcmp(power, mind) <= 0) {
 			avma = ltop;
diff --git a/src/gen/gens.h b/src/gen/gens.h
index 18c9815..11b349b 100644
--- a/src/gen/gens.h
+++ b/src/gen/gens.h
@@ -30,6 +30,7 @@ GENERATOR(gens_gen_any);
 GENERATOR(gens_gen_one);
 
 /**
+ * CHECK(check_f)
  *
  * @param curve
  * @param args
@@ -39,6 +40,18 @@ GENERATOR(gens_gen_one);
 CHECK(gens_check_anomalous);
 
 /**
+ * @brief Get the embedding degree of a subgroup of <code>order</code> in a
+ * power of F_prime.
+ *
+ * @param prime The order of the base field.
+ * @param order The order of the subgroup generator (in the curve group).
+ * @return The embedding degree 't' such that <code>order</code> divides
+ * 'prime^t - 1'.
+ */
+GEN gens_get_embedding(GEN prime, GEN order);
+
+/**
+ * CHECK(check_f)
  *
  * @param curve
  * @param args
diff --git a/src/misc/types.h b/src/misc/types.h
index 960745c..76f8510 100644
--- a/src/misc/types.h
+++ b/src/misc/types.h
@@ -49,8 +49,6 @@ typedef struct {
 			long v;
 			bits_t *seed_a;
 			bits_t *seed_b;
-			bits_t *seed_bp;
-			GEN mult;
 		} brainpool;
 	};
 } seed_t;