Fix errors in point generation, for "nonprime" points mainly.

4 files changed, 119 insertions, 51 deletions

diff --git a/src/gen/point.c b/src/gen/point.c
index 45e833b..0c6e99e 100644
--- a/src/gen/point.c
+++ b/src/gen/point.c
@@ -3,8 +3,8 @@
  * Copyright (C) 2017 J08nY
  */
 #include "point.h"
+#include "io/output.h"
 #include "math/subgroups.h"
-#include "order.h"
 #include "types.h"
 #include "util/memory.h"
 
@@ -122,14 +122,14 @@ GENERATOR(points_gen_random) {
 	return 1;
 }
 
-static int points_from_orders(curve_t *curve, const config_t *cfg, GEN orders) {
+static int points_from_orders(curve_t *curve, GEN orders) {
 	// TODO better stack code
 	size_t norders = (size_t)glength(orders);
 
 	curve->points = points_new(norders);
 	curve->npoints = norders;
 
-	for (size_t ngen = 0; ngen <= curve->ngens; ++ngen) {
+	for (size_t ngen = 0; ngen < curve->ngens; ++ngen) {
 		point_t *gen = curve->generators[ngen];
 
 		for (long i = 0; i < norders; ++i) {
@@ -146,6 +146,8 @@ static int points_from_orders(curve_t *curve, const config_t *cfg, GEN orders) {
 				}
 
 				if (point) {
+					debug_log("VERIFY %Ps %Ps", num,
+					          ellorder(curve->curve, point, NULL));
 					curve->points[i] = point_new();
 					gerepileall(ftop, 1, &point);
 					curve->points[i]->point = point;
@@ -172,25 +174,26 @@ GENERATOR(points_gen_trial) {
 		gel(orders, i) = utoi(primes[i - 1]);
 	}
 
-	return points_from_orders(curve, cfg, orders);
+	return points_from_orders(curve, orders);
 }
 
 GENERATOR(points_gen_prime) {
-	GEN primes = subgroups_prime(curve->order, cfg);
-	return points_from_orders(curve, cfg, primes);
+	GEN primes = subgroups_prime(curve, cfg);
+	return points_from_orders(curve, primes);
 }
 
 GENERATOR(points_gen_allgroups) {
-	GEN groups = subgroups_all(curve->order, cfg);
-	return points_from_orders(curve, cfg, groups);
+	GEN groups = subgroups_all(curve, cfg);
+	return points_from_orders(curve, groups);
 }
 
 GENERATOR(points_gen_nonprime) {
-	GEN groups = subgroups_nonprime(curve->order, cfg);
+	GEN groups = subgroups_nonprime(curve, cfg);
 	if (!groups) {
-		return -6;
+		// No non-prime order points on curve.
+		return 1;
 	} else {
-		return points_from_orders(curve, cfg, groups);
+		return points_from_orders(curve, groups);
 	}
 }
 
diff --git a/src/io/output.h b/src/io/output.h
index 459834d..05c00e3 100644
--- a/src/io/output.h
+++ b/src/io/output.h
@@ -14,28 +14,35 @@
 
 #ifdef DEBUG
 
-#include "time.h"
+#include <inttypes.h>
+#include <time.h>
+
+#define _debug_print(prefix)             \
+	fprintf(verbose, prefix);            \
+	struct timespec ts;                  \
+	clock_gettime(CLOCK_MONOTONIC, &ts); \
+	fprintf(verbose, "%" PRIdMAX ".%.9ld ", ts.tv_sec, ts.tv_nsec);
 
 #define debug(...) pari_fprintf(verbose, __VA_ARGS__)
-#define debug_log(...)                            \
-	do {                                          \
-		fprintf(verbose, " -  %lu ", time(NULL)); \
-		debug(__VA_ARGS__);                       \
-		fprintf(verbose, "\n");                   \
+#define debug_log(...)          \
+	do {                        \
+		_debug_print(" -  ");   \
+		debug(__VA_ARGS__);     \
+		fprintf(verbose, "\n"); \
 	} while (0)
 
-#define debug_log_start(...)                      \
-	do {                                          \
-		fprintf(verbose, "[ ] %lu ", time(NULL)); \
-		debug(__VA_ARGS__);                       \
-		fprintf(verbose, "\n");                   \
+#define debug_log_start(...)    \
+	do {                        \
+		_debug_print("[ ] ");   \
+		debug(__VA_ARGS__);     \
+		fprintf(verbose, "\n"); \
 	} while (0)
 
-#define debug_log_end(...)                        \
-	do {                                          \
-		fprintf(verbose, "[*] %lu ", time(NULL)); \
-		debug(__VA_ARGS__);                       \
-		fprintf(verbose, "\n");                   \
+#define debug_log_end(...)      \
+	do {                        \
+		_debug_print("[*] ");   \
+		debug(__VA_ARGS__);     \
+		fprintf(verbose, "\n"); \
 	} while (0)
 
 #else
diff --git a/src/math/subgroups.c b/src/math/subgroups.c
index 304d43e..91bd16a 100644
--- a/src/math/subgroups.c
+++ b/src/math/subgroups.c
@@ -3,19 +3,56 @@
  * Copyright (C) 2017 J08nY
  */
 #include "subgroups.h"
+#include "io/output.h"
 
-GEN subgroups_prime(GEN order, const config_t *cfg) {
-	if (cfg->prime || isprime(order)) {
-		return gtovec(order);
+/**
+ * @brief All prime divisors of a given integer.
+ * @param order
+ * @return
+ */
+static GEN subgroups_factors(GEN order) {
+	GEN factors = Z_factor(order);
+	return gel(factors, 1);
+}
+
+/**
+ * @brief All prime divisors of a given integer with multiplicity.
+ * @param order
+ * @return
+ */
+static GEN subgroups_divisors(GEN order) {
+	GEN factors = Z_factor(order);
+	GEN primes = gel(factors, 1);
+	GEN multiples = gel(factors, 2);
+	long uniqs = glength(primes);
+
+	long size = 0;
+	for (long i = 1; i <= uniqs; ++i) {
+		size += itos(gel(multiples, i));
+	}
+	GEN result = gtovec0(gen_0, size);
+
+	long count = 0;
+	for (long i = 1; i <= uniqs; ++i) {
+		long multiple = itos(gel(multiples, i));
+		for (long j = 1; j <= multiple; ++j) {
+			gel(result, ++count) = gel(primes, i);
+		}
+	}
+	return result;
+}
+
+GEN subgroups_prime(const curve_t *curve, const config_t *cfg) {
+	if (cfg->prime || isprime(curve->order)) {
+		return gtovec(curve->order);
 	} else {
-		GEN factors = Z_factor(order);
-		return gel(factors, 1);
+		return subgroups_factors(curve->order);
 	}
 }
 
-// TODO: what if some factor multiple times? Prove this works..
 static GEN subgroups_2n(GEN factors, size_t min_bits) {
 	long nprimes = glength(factors);
+	if (nprimes == min_bits) return NULL;
 	GEN amount = int2n(nprimes);
 	GEN groups = gtovec0(gen_0, itos(amount) - (min_bits * nprimes) - 1);
 
@@ -37,24 +74,45 @@ static GEN subgroups_2n(GEN factors, size_t min_bits) {
 			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)) {
+GEN subgroups_nonprime(const curve_t *curve, const config_t *cfg) {
+	if (cfg->prime || isprime(curve->order)) {
 		return NULL;
 	} else {
-		GEN factors = subgroups_prime(order, cfg);
-		return subgroups_2n(factors, 1);
+		if (curve->ngens == 1) {
+			GEN factors = subgroups_factors(curve->order);
+			return subgroups_2n(factors, 1);
+		} else {
+			GEN one_factors = subgroups_factors(curve->generators[0]->order);
+			GEN one = subgroups_2n(one_factors, 1);
+			GEN other_factors = subgroups_factors(curve->generators[1]->order);
+			GEN other = subgroups_2n(other_factors, 1);
+			if (!one) {
+				return other;
+			}
+			if (!other) {
+				return one;
+			}
+			GEN result = gtovec0(gen_0, glength(one) + glength(other));
+			for (long i = 1; i <= glength(result); ++i) {
+				if (i <= glength(one)) {
+					gel(result, i) = gel(one, i);
+				} else {
+					gel(result, i) = gel(other, i - glength(one));
+				}
+			}
+			return result;
+		}
 	}
 }
 
-GEN subgroups_all(GEN order, const config_t *cfg) {
-	if (cfg->prime || isprime(order)) {
-		return gtovec(order);
+GEN subgroups_all(const curve_t *curve, const config_t *cfg) {
+	if (cfg->prime || isprime(curve->order)) {
+		return gtovec(curve->order);
 	} else {
-		GEN factors = subgroups_prime(order, cfg);
+		GEN factors = subgroups_factors(curve->order);
 		return subgroups_2n(factors, 0);
 	}
 }
\ No newline at end of file
diff --git a/src/math/subgroups.h b/src/math/subgroups.h
index 42c81f7..fee095b 100644
--- a/src/math/subgroups.h
+++ b/src/math/subgroups.h
@@ -12,27 +12,27 @@
 #include "gen/types.h"
 
 /**
- * @brief Enumerates prime subgroup orders of a given finite group.
- * @param order group order
+ * @brief Enumerates prime subgroup orders of a given curve.
+ * @param curve
  * @param cfg
  * @return
  */
-GEN subgroups_prime(GEN i, const config_t *cfg);
+GEN subgroups_prime(const curve_t *curve, const config_t *cfg);
 
 /**
- * @brief Enumerates nonprime subgroup orders of a given finite group.
- * @param order group order
+ * @brief Enumerates nonprime subgroup orders of a given curve.
+ * @param curve
  * @param cfg
  * @return
  */
-GEN subgroups_nonprime(GEN order, const config_t *cfg);
+GEN subgroups_nonprime(const curve_t *curve, const config_t *cfg);
 
 /**
- * @brief Enumerates all subgroup orders of a given finite group.
- * @param order group order
+ * @brief Enumerates all subgroup orders of a given curve.
+ * @param curve
  * @param cfg
  * @return
  */
-GEN subgroups_all(GEN order, const config_t *cfg);
+GEN subgroups_all(const curve_t *curve, const config_t *cfg);
 
 #endif  // ECGEN_SUBGROUPS_H