Add generating of points on non-prime order subgroups of a curve.

 - Use --points=nonprime

2 files changed, 99 insertions, 0 deletions

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