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

1 files changed, 73 insertions, 15 deletions

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