Added generating of points on all subgroups of a curve.

 - Use --points=all, the number of points can be quite large however,
   it's 2^(num of prime subgroups of the curve).

8 files changed, 141 insertions, 18 deletions

diff --git a/src/math/order.c b/src/math/order.c
index 4c8c728..347015c 100644
--- a/src/math/order.c
+++ b/src/math/order.c
@@ -4,6 +4,39 @@
  */
 #include "order.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_any) {
 	GEN ord = ellff_get_card(curve->curve);
 	if (isclone(ord)) {
diff --git a/src/math/order.h b/src/math/order.h
index 8a56b94..ce3cd0b 100644
--- a/src/math/order.h
+++ b/src/math/order.h
@@ -11,6 +11,23 @@
 #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)
  * Calculates the curve order, using a general algorithm.
  * Always succeeds.
diff --git a/src/math/point.c b/src/math/point.c
index f590ca2..4251913 100644
--- a/src/math/point.c
+++ b/src/math/point.c
@@ -3,6 +3,7 @@
  * Copyright (C) 2017 J08nY
  */
 #include "point.h"
+#include "order.h"
 #include "util/memory.h"
 
 point_t *point_new(void) { return try_calloc(sizeof(point_t)); }
@@ -176,8 +177,7 @@ GENERATOR(points_gen_trial) {
 GENERATOR(points_gen_prime) {
 	// TODO stack code!!!
 
-	GEN factors = Z_factor(curve->order);
-	GEN primes = gel(factors, 1);
+	GEN primes = order_factors(curve, cfg);
 	long nprimes = glength(primes);
 
 	curve->points = points_new((size_t)nprimes);
@@ -195,14 +195,13 @@ GENERATOR(points_gen_prime) {
 
 				// primes[i] divides ord
 				// mul = ord/primes[i]
-				GEN p = gcopy(gel(primes, i));
-				GEN mul = divii(ord, p);
+				GEN mul = divii(ord, gel(primes, i));
 				GEN point = ellmul(curve->curve, rand, mul);
 
 				curve->points[i - 1] = point_new();
-				gerepileall(ftop, 2, &point, &p);
+				gerepileall(ftop, 1, &point);
 				curve->points[i - 1]->point = point;
-				curve->points[i - 1]->order = p;
+				curve->points[i - 1]->order = gcopy(gel(primes, i));
 				npoints++;
 			}
 		}
@@ -211,6 +210,49 @@ GENERATOR(points_gen_prime) {
 	return 1;
 }
 
+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);
+
+			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);
+				}
+
+				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;
+				}
+			}
+		}
+	}
+
+	return 1;
+}
+
 UNROLL(points_unroll) {
 	if (curve->points) {
 		points_free_deep(&curve->points, curve->npoints);
diff --git a/src/math/point.h b/src/math/point.h
index 49c37c6..a25ec2c 100644
--- a/src/math/point.h
+++ b/src/math/point.h
@@ -159,6 +159,19 @@ GENERATOR(points_gen_trial);
 GENERATOR(points_gen_prime);
 
 /**
+ * GENERATOR(gen_t)
+ *
+ * Generates points on all subgroups of the curve. Prime and non-prime order.
+ *
+ * @param curve
+ * @param cfg
+ * @param args
+ * @return
+ */
+GENERATOR(points_gen_allgroups);
+
+/**
+ * UNROLL(unroll_t)
  *
  * @param curve
  * @param cfg
diff --git a/src/math/poly.c b/src/math/poly.c
index 50d0da0..2b655da 100644
--- a/src/math/poly.c
+++ b/src/math/poly.c
@@ -2729,7 +2729,7 @@ polynomial_t *poly_find(unsigned long m) {
 		len_penta = sizeof(hp_pentanomials) / sizeof(polynomial_t);
 	}
 
-	polynomial_t searched = {(int)m};
+	polynomial_t searched = {(unsigned int)m};
 	polynomial_t *tri = (polynomial_t *)bsearch(
 	    &searched, search_tri, len_tri, sizeof(polynomial_t), &compare_poly);
 	if (tri) {
diff --git a/src/math/poly.h b/src/math/poly.h
index 664ca6b..83b909a 100644
--- a/src/math/poly.h
+++ b/src/math/poly.h
@@ -12,10 +12,10 @@
 #include <stdbool.h>
 
 typedef struct {
-	int m;
-	int e1;
-	int e2;
-	int e3;
+	unsigned int m;
+	unsigned int e1;
+	unsigned int e2;
+	unsigned int e3;
 } polynomial_t;
 
 /**
diff --git a/src/math/random.c b/src/math/random.c
index da4bc2c..519ce6b 100644
--- a/src/math/random.c
+++ b/src/math/random.c
@@ -3,6 +3,7 @@
  * Copyright (C) 2017 J08nY
  */
 #define _POSIX_C_SOURCE 200809L
+
 #include "random.h"
 #include <time.h>
 
@@ -43,13 +44,11 @@ GEN random_prime(unsigned long bits) {
 	gel(range, 2) = powis(gen_2, bits);
 
 	GEN p;
-	{
-		pari_sp btop = avma;
-		do {
-			p = randomprime(range);
-			p = gerepileupto(btop, p);
-		} while (!isprime(p));
-	}
+	pari_sp btop = avma;
+	do {
+		p = randomprime(range);
+		p = gerepileupto(btop, p);
+	} while (!isprime(p));
 
 	return gerepilecopy(ltop, p);
 }
diff --git a/src/math/random.h b/src/math/random.h
index de03abb..1152bb5 100644
--- a/src/math/random.h
+++ b/src/math/random.h
@@ -11,10 +11,29 @@
 #include <pari/pari.h>
 #include <stdbool.h>
 
+/**
+ * @brief Init the PARI-GP random generator.
+ *
+ * Initializes the PARI-GP random generator, tries to do so from
+ * cryptographically strong sources(/dev/urandom) at first but falls back on
+ * clock_gettime and {@link time(NULL)}.
+ *
+ * @return Whether the initialization was successful.
+ */
 bool random_init(void);
 
+/**
+ * @brief Generate random <code>bits</code> sized prime.
+ * @param bits the size of the prime to generate
+ * @return a random prime in range [2^(bits - 1), 2^bits]
+ */
 GEN random_prime(unsigned long bits);
 
+/**
+ * @brief Generate random <code>bits</code> sized integer.
+ * @param bits the size of the integer to generate
+ * @return a random integer in range [2^(bits - 1), 2^bits]
+ */
 GEN random_int(unsigned long bits);
 
 #endif  // ECGEN_RANDOM_H