10 files changed, 175 insertions, 164 deletions

diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c
index f2c555b..5c50a71 100644
--- a/src/exhaustive/exhaustive.c
+++ b/src/exhaustive/exhaustive.c
@@ -87,12 +87,16 @@ static void exhaustive_ginit(gen_t *generators, const config_t *cfg) {
 		case POINTS_PRIME:
 			generators[OFFSET_POINTS] = &points_gen_prime;
 			break;
+		case POINTS_NONPRIME:
+			generators[OFFSET_POINTS] = &points_gen_nonprime;
+			break;
 		case POINTS_ALL:
 			generators[OFFSET_POINTS] = &points_gen_allgroups;
 			break;
 		case POINTS_NONE:
 			generators[OFFSET_POINTS] = &gen_skip;
 			break;
+
 	}
 }
 
diff --git a/src/gen/order.c b/src/gen/order.c
index 2c963f6..6ecd7d6 100644
--- a/src/gen/order.c
+++ b/src/gen/order.c
@@ -5,39 +5,6 @@
 #include "order.h"
 #include "io/input.h"
 
-GEN order_factors(curve_t *curve, const config_t *cfg) {
-	if (cfg->prime) {
-		return gtovec(curve->order);
-	} else {
-		GEN factors = Z_factor(curve->order);
-		return gel(factors, 1);
-	}
-}
-
-GEN order_groups(curve_t *curve, const config_t *cfg, GEN factors) {
-	long nprimes = glength(factors);
-	if (cfg->prime) {
-		return gtovec(curve->order);
-	} else {
-		GEN amount = int2n(nprimes);
-		GEN groups = gtovec0(gen_0, itos(amount) - 1);
-
-		for (size_t count = 1; count < (size_t)(1 << nprimes); ++count) {
-			GEN result = gen_1;
-			for (long bit = 0; bit < nprimes; ++bit) {
-				size_t mask = (size_t)(1 << bit);
-				if (count & mask) {
-					result = mulii(result, gel(factors, bit + 1));
-				}
-			}
-			gel(groups, count) = result;
-		}
-		// TODO: sort this, as it is not necessarily sorted, in fact most likely
-		// not
-		return groups;
-	}
-}
-
 GENERATOR(order_gen_input) {
 	pari_sp ltop = avma;
 	GEN ord = input_int("order", cfg->bits);
diff --git a/src/gen/order.h b/src/gen/order.h
index bdb6ec0..da62c4d 100644
--- a/src/gen/order.h
+++ b/src/gen/order.h
@@ -11,23 +11,6 @@
 #include "types.h"
 
 /**
- * @brief Factors curve order.
- * @param curve
- * @param cfg
- * @return
- */
-GEN order_factors(curve_t *curve, const config_t *cfg);
-
-/**
- * @brief Enumerates all subgroup orders of a curve given prime order factors.
- * @param curve
- * @param cfg
- * @param factors
- * @return
- */
-GEN order_groups(curve_t *curve, const config_t *cfg, GEN factors);
-
-/**
  * GENERATOR(gen_t)
  * Reads the curve order from input, does not verify it.
  *
diff --git a/src/gen/point.c b/src/gen/point.c
index 4251913..66a77d4 100644
--- a/src/gen/point.c
+++ b/src/gen/point.c
@@ -5,6 +5,8 @@
 #include "point.h"
 #include "order.h"
 #include "util/memory.h"
+#include "math/subgroups.h"
+#include "types.h"
 
 point_t *point_new(void) { return try_calloc(sizeof(point_t)); }
 
@@ -120,53 +122,35 @@ GENERATOR(points_gen_random) {
 	return 1;
 }
 
-/*
-    GEN o = utoi(dprimes[i]);
-    GEN mul = ellmul(curve->curve, rand, o);
-
-    if (gequal0(mul)) {
-        printf("Success! %lu\n", npoints);
-        curve->points[i] = point_new();
-
-        gerepileall(btop, 2, &rand, &o);
-        curve->points[i]->point = rand;
-        curve->points[i]->order = o;
-        npoints++;
-        break;
-    }
- */
-
-GENERATOR(points_gen_trial) {
-	// TODO stack code!!!
-	if (!args) {
-		fprintf(stderr, "No args to an arged function. points_gen_trial\n");
-		return INT_MIN;
-	}
-
-	pari_ulong *primes = (pari_ulong *)args->args;
-	size_t nprimes = args->nargs;
+static int points_from_orders(curve_t *curve, const config_t *cfg, GEN orders) {
+	// TODO better stack code
+	size_t norders = (size_t)glength(orders);
 
-	curve->points = points_new(nprimes);
-	curve->npoints = nprimes;
+	curve->points = points_new(norders);
+	curve->npoints = norders;
 
-	size_t npoints = 0;
-	while (npoints < nprimes) {
-		GEN rand = genrand(curve->curve);
-		GEN ord = ellorder(curve->curve, rand, NULL);
+	for (size_t ngen = 0; ngen <= curve->ngens; ++ngen) {
+		point_t *gen = curve->generators[ngen];
 
-		for (long i = 0; i < nprimes; ++i) {
-			if (curve->points[i] == NULL && dvdis(ord, primes[i])) {
+		for (long i = 0; i < norders; ++i) {
+			GEN num = gel(orders, i + 1);
+			if (curve->points[i] == NULL) {
 				pari_sp ftop = avma;
 
-				GEN p = stoi(primes[i]);
-				GEN mul = divii(ord, p);
-				GEN point = ellmul(curve->curve, rand, mul);
+				GEN point = NULL;
+				if (equalii(gen->order, num)) {
+					point = gcopy(gen->point);
+				} else if (dvdii(gen->order, num)) {
+					GEN mul = divii(gen->order, num);
+					point = ellmul(curve->curve, gen->point, mul);
+				}
 
-				curve->points[i] = point_new();
-				gerepileall(ftop, 2, &point, &p);
-				curve->points[i]->point = point;
-				curve->points[i]->order = p;
-				npoints++;
+				if (point) {
+					curve->points[i] = point_new();
+					gerepileall(ftop, 1, &point);
+					curve->points[i]->point = point;
+					curve->points[i]->order = gcopy(num);
+				}
 			}
 		}
 	}
@@ -174,83 +158,41 @@ GENERATOR(points_gen_trial) {
 	return 1;
 }
 
-GENERATOR(points_gen_prime) {
-	// TODO stack code!!!
-
-	GEN primes = order_factors(curve, cfg);
-	long nprimes = glength(primes);
 
-	curve->points = points_new((size_t)nprimes);
-	curve->npoints = (size_t)nprimes;
-
-	long npoints = 0;
-	while (npoints < nprimes) {
-		GEN rand = genrand(curve->curve);
-		GEN ord = ellorder(curve->curve, rand, NULL);
-		// ord(rand) = ord
-
-		for (long i = 1; i <= nprimes; ++i) {
-			if (curve->points[i - 1] == NULL && dvdii(ord, gel(primes, i))) {
-				pari_sp ftop = avma;
+GENERATOR(points_gen_trial) {
+	if (!args) {
+		fprintf(stderr, "No args to an arged function. points_gen_trial\n");
+		return INT_MIN;
+	}
 
-				// primes[i] divides ord
-				// mul = ord/primes[i]
-				GEN mul = divii(ord, gel(primes, i));
-				GEN point = ellmul(curve->curve, rand, mul);
+	pari_ulong *primes = (pari_ulong *)args->args;
+	size_t nprimes = args->nargs;
 
-				curve->points[i - 1] = point_new();
-				gerepileall(ftop, 1, &point);
-				curve->points[i - 1]->point = point;
-				curve->points[i - 1]->order = gcopy(gel(primes, i));
-				npoints++;
-			}
-		}
+	GEN orders = gtovec0(gen_0, nprimes);
+	for (size_t i = 1; i <= nprimes; ++i) {
+		gel(orders, i) = utoi(primes[i - 1]);
 	}
 
-	return 1;
+	return points_from_orders(curve, cfg, orders);
 }
 
-GENERATOR(points_gen_allgroups) {
-	// TODO stack code!!!
-
-	GEN primes = order_factors(curve, cfg);
-
-	GEN groups = order_groups(curve, cfg, primes);
-	long ngroups = glength(groups);
-
-	curve->points = points_new((size_t)ngroups);
-	curve->npoints = (size_t)ngroups;
-
-	long npoints = 0;
-	while (npoints < ngroups) {
-		GEN rand = genrand(curve->curve);
-		GEN ord = ellorder(curve->curve, rand, NULL);
-
-		for (long i = 1; i <= ngroups; ++i) {
-			pari_sp ftop = avma;
-			GEN num = gel(groups, i);
+GENERATOR(points_gen_prime) {
+	GEN primes = subgroups_prime(curve->order, cfg);
+	return points_from_orders(curve, cfg, primes);
+}
 
-			if (curve->points[i - 1] == NULL) {
-				GEN point = NULL;
-				if (equalii(ord, num)) {
-					point = gcopy(rand);
-				} else if (dvdii(ord, num)) {
-					GEN mul = divii(ord, num);
-					point = ellmul(curve->curve, rand, mul);
-				}
+GENERATOR(points_gen_allgroups) {
+	GEN groups = subgroups_all(curve->order, cfg);
+	return points_from_orders(curve, cfg, groups);
+}
 
-				if (point) {
-					curve->points[i - 1] = point_new();
-					gerepileall(ftop, 1, &point);
-					curve->points[i - 1]->point = point;
-					curve->points[i - 1]->order = gcopy(num);
-					++npoints;
-				}
-			}
-		}
+GENERATOR(points_gen_nonprime) {
+	GEN groups = subgroups_nonprime(curve->order, cfg);
+	if (!groups) {
+		return -6;
+	} else {
+		return points_from_orders(curve, cfg, groups);
 	}
-
-	return 1;
 }
 
 UNROLL(points_unroll) {
diff --git a/src/gen/point.h b/src/gen/point.h
index 1a0b348..c8cae17 100644
--- a/src/gen/point.h
+++ b/src/gen/point.h
@@ -167,6 +167,18 @@ GENERATOR(points_gen_prime);
 GENERATOR(points_gen_allgroups);
 
 /**
+ * GENERATOR(gen_t)
+ *
+ * Generates points on non-prime order of the curve.
+ *
+ * @param curve A curve_t being generated
+ * @param cfg An application config
+ * @param args unused
+ * @return state diff
+ */
+GENERATOR(points_gen_nonprime);
+
+/**
  * UNROLL(unroll_t)
  *
  * @param curve
diff --git a/src/io/cli.c b/src/io/cli.c
index f074c3f..db76b5b 100644
--- a/src/io/cli.c
+++ b/src/io/cli.c
@@ -50,7 +50,7 @@ struct argp_option cli_options[] = {
 	{"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/all/none).",                                    2},
+	{"points",       OPT_POINTS,    "TYPE",   0,                 "Generate points of given type (random/prime/all/nonprime/none).",                       2},
 	{"seed",         OPT_SEED,      "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (ANSI X9.62 verifiable procedure). **NOT IMPLEMENTED**",     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). **NOT IMPLEMENTED**", 2},
@@ -175,13 +175,15 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) {
 			char *num_end;
 			long amount = strtol(arg, &num_end, 10);
 			cfg->points.amount = (size_t)amount;
-			if (strstr(num_end, "random")) {
+			if (strstr(num_end, "random") == num_end) {
 				cfg->points.type = POINTS_RANDOM;
-			} else if (strstr(num_end, "prime")) {
+			} else if (strstr(num_end, "prime") == num_end) {
 				cfg->points.type = POINTS_PRIME;
-			} else if (strstr(num_end, "all")) {
+			} else if (strstr(num_end, "all") == num_end) {
 				cfg->points.type = POINTS_ALL;
-			} else if (strstr(num_end, "none")) {
+			} else if (strstr(num_end, "nonprime") == num_end) {
+				cfg->points.type = POINTS_NONPRIME;
+			} else if (strstr(num_end, "none") == num_end) {
 				cfg->points.type = POINTS_NONE;
 			} else {
 				argp_failure(state, 1, 0, "Unknown point type. %s", num_end);
diff --git a/src/io/config.h b/src/io/config.h
index 5186c67..b365987 100644
--- a/src/io/config.h
+++ b/src/io/config.h
@@ -13,7 +13,7 @@
 
 enum field_e { FIELD_PRIME, FIELD_BINARY };
 enum format_e { FORMAT_JSON, FORMAT_CSV };
-enum points_e { POINTS_PRIME, POINTS_RANDOM, POINTS_ALL, POINTS_NONE };
+enum points_e { POINTS_PRIME, POINTS_RANDOM, POINTS_ALL, POINTS_NONPRIME, POINTS_NONE };
 struct points_s {
 	enum points_e type;
 	size_t amount;
diff --git a/src/math/subgroups.c b/src/math/subgroups.c
new file mode 100644
index 0000000..304d43e
--- /dev/null
+++ b/src/math/subgroups.c
@@ -0,0 +1,60 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+#include "subgroups.h"
+
+GEN subgroups_prime(GEN order, const config_t *cfg) {
+	if (cfg->prime || isprime(order)) {
+		return gtovec(order);
+	} else {
+		GEN factors = Z_factor(order);
+		return gel(factors, 1);
+	}
+}
+
+// TODO: what if some factor multiple times? Prove this works..
+static GEN subgroups_2n(GEN factors, size_t min_bits) {
+	long nprimes = glength(factors);
+	GEN amount = int2n(nprimes);
+	GEN groups = gtovec0(gen_0, itos(amount) - (min_bits * nprimes) - 1);
+
+	size_t i = 0;
+	for (size_t count = 1; count < (size_t)(1 << nprimes); ++count) {
+		pari_sp btop = avma;
+		GEN result = gen_1;
+		size_t bits = 0;
+		for (long bit = 0; bit < nprimes; ++bit) {
+			size_t mask = (size_t)(1 << bit);
+			if (count & mask) {
+				result = mulii(result, gel(factors, bit + 1));
+				bits++;
+			}
+		}
+		if (bits > min_bits) {
+			gel(groups, ++i) = result;
+		} else {
+			avma = btop;
+		}
+	}
+	// TODO: sort this, as it is not sorted
+	return groups;
+}
+
+GEN subgroups_nonprime(GEN order, const config_t *cfg) {
+	if (cfg->prime || isprime(order)) {
+		return NULL;
+	} else {
+		GEN factors = subgroups_prime(order, cfg);
+		return subgroups_2n(factors, 1);
+	}
+}
+
+GEN subgroups_all(GEN order, const config_t *cfg) {
+	if (cfg->prime || isprime(order)) {
+		return gtovec(order);
+	} else {
+		GEN factors = subgroups_prime(order, cfg);
+		return subgroups_2n(factors, 0);
+	}
+}
\ No newline at end of file
diff --git a/src/math/subgroups.h b/src/math/subgroups.h
new file mode 100644
index 0000000..bd9b29d
--- /dev/null
+++ b/src/math/subgroups.h
@@ -0,0 +1,39 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+/**
+ * @file subgroups.h
+ */
+#ifndef ECGEN_SUBGROUPS_H
+#define ECGEN_SUBGROUPS_H
+
+#include <pari/pari.h>
+#include "gen/types.h"
+
+/**
+ * @brief Enumerates prime subgroup orders of a given finite group.
+ * @param order group order
+ * @param cfg
+ * @return
+ */
+GEN subgroups_prime(GEN i, const config_t *cfg);
+
+/**
+ * @brief Enumerates nonprime subgroup orders of a given finite group.
+ * @param order group order
+ * @param cfg
+ * @return
+ */
+GEN subgroups_nonprime(GEN order, const config_t *cfg);
+
+/**
+ * @brief Enumerates all subgroup orders of a given finite group.
+ * @param order group order
+ * @param cfg
+ * @return
+ */
+GEN subgroups_all(GEN order, const config_t *cfg);
+
+
+#endif //ECGEN_SUBGROUPS_H
diff --git a/test/ecgen.sh b/test/ecgen.sh
index a4bf2e8..692f1b7 100755
--- a/test/ecgen.sh
+++ b/test/ecgen.sh
@@ -56,12 +56,14 @@ function exhaustive() {
 	assert_raises "${ecgen} --fp -r --points=random 10"
 	assert_raises "${ecgen} --fp -r --points=10random 10"
 	assert_raises "${ecgen} --fp -r --points=prime 10"
+	assert_raises "${ecgen} --fp -r --points=nonprime 10"
 	assert_raises "${ecgen} --fp -r --points=all 10"
 	assert_raises "${ecgen} --fp -r --points=none 10"
 
 	assert_raises "${ecgen} --f2m -r --points=random 10"
 	assert_raises "${ecgen} --f2m -r --points=10random 10"
 	assert_raises "${ecgen} --f2m -r --points=prime 10"
+	assert_raises "${ecgen} --f2m -r --points=nonprime 10"
 	assert_raises "${ecgen} --f2m -r --points=all 10"
 	assert_raises "${ecgen} --f2m -r --points=none 10"
 }