aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/cm/cm.c18
-rw-r--r--src/cm/cm_any.c225
-rw-r--r--src/cm/cm_any.h22
-rw-r--r--src/cm/cm_prime.c (renamed from src/cm/custom.c)125
-rw-r--r--src/cm/cm_prime.h (renamed from src/cm/custom.h)15
-rw-r--r--src/ecgen.c2
-rwxr-xr-xtest/ecgen.sh2
-rw-r--r--test/src/cm/test_cm.c (renamed from test/src/cm/test_custom.c)29
8 files changed, 349 insertions, 89 deletions
diff --git a/src/cm/cm.c b/src/cm/cm.c
index 8fa174d..a29e368 100644
--- a/src/cm/cm.c
+++ b/src/cm/cm.c
@@ -3,7 +3,8 @@
* Copyright (C) 2017-2018 J08nY
*/
#include "cm.h"
-#include "custom.h"
+#include "cm_any.h"
+#include "cm_prime.h"
#include "io/output.h"
#include "obj/curve.h"
#include "p1363.h"
@@ -12,7 +13,20 @@ int cm_do() {
debug_log_start("Starting Complex Multiplication method");
int result = 0;
- curve_t *curve = custom_curve();
+ GEN order = strtoi(cfg->cm_order);
+ curve_t *curve = NULL;
+
+ if (gequal0(order)) {
+ fprintf(err, "Order requested not a number: %s\n", cfg->cm_order);
+ result = 1;
+ } else if (isprime(order)) {
+ debug_log("Starting prime order curve generation");
+ curve = cm_prime_curve(order);
+ } else {
+ debug_log("Starting composite order curve generation");
+ curve = cm_any_curve(order);
+ }
+
if (curve) {
output_o_begin();
output_o(curve);
diff --git a/src/cm/cm_any.c b/src/cm/cm_any.c
new file mode 100644
index 0000000..401a544
--- /dev/null
+++ b/src/cm/cm_any.c
@@ -0,0 +1,225 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017-2018 J08nY
+ */
+#include "cm_any.h"
+#include <obj/obj.h>
+#include "io/output.h"
+#include "obj/curve.h"
+#include "util/memory.h"
+
+/**
+ * @brief Slightly adapted algorithm from section 4.2 of
+ * Constructing elliptic curves of prescribed order,
+ * Reiner Broker
+ * @param order
+ * @return
+ */
+static cm_any_qdisc_t *good_qdisc_minimal(GEN order) {
+ pari_sp ltop = avma;
+ GEN d = stoi(2);
+ while (true) {
+ if (!issquarefree(d)) {
+ d = addis(d, 1);
+ continue;
+ }
+ GEN D = quaddisc(negi(d));
+ GEN K = Buchall(quadpoly(D), 0, DEFAULTPREC);
+ GEN alphas = bnfisintnorm(K, order);
+ long len = glength(alphas);
+ if (len != 0) {
+ debug_log("Got some elems of norm N: %Ps", alphas);
+ for (long i = 1; i <= len; ++i) {
+ GEN alpha = gel(alphas, i);
+ GEN trace = nftrace(K, alpha);
+ GEN p = subii(addis(order, 1), trace);
+ if (isprime(p)) {
+ debug_log(
+ "Got an elem of prime trace: %Pi, d = %Pi, D = %Pi", p,
+ d, D);
+ cm_any_qdisc_t *result = try_calloc(sizeof(cm_any_qdisc_t));
+ result->p = p;
+ result->d = D;
+ gerepileall(ltop, 2, &result->p, &result->d);
+ return result;
+ }
+ }
+ }
+ d = gerepileupto(ltop, addis(d, 1));
+ }
+}
+
+/**
+ * @brief Find a fundamental quadratic discriminant < d_range, start looking
+ * at the sides of the inverted Hasse interval around order, upto p_range
+ *
+ * order + 1 - 2*sqrt(order) order + 1 + 2*sqrt(order)
+ * | |
+ * |-----|----------|----------|-----|
+ * >_____> | <_____<
+ * | order |
+ * p_range p_range
+ * Inspired by a method from:
+ * Constructing elliptic curves of prescribed order,
+ * Reiner Broker
+ *
+ * @param order
+ * @param p_range
+ * @param d_range
+ * @return
+ *//*
+
+static cm_any_qdisc_t *good_qdisc_brute_range(GEN order, GEN p_range, GEN d_range) {
+ pari_sp ltop = avma;
+ GEN tsqrt_ord = mulis(sqrti(order), 2);
+ GEN left_p = subii(addis(order, 1), tsqrt_ord);
+ GEN right_p = addii(addis(order, 1), tsqrt_ord);
+
+ GEN left_max_p = addii(left_p, p_range);
+ GEN right_min_p = subii(right_p, p_range);
+
+ GEN min_d = stoi(0);
+ bool left = true;
+ while (true) {
+ GEN p;
+ if (left) {
+ left_p = nextprime(addis(left_p, 1));
+ p = left_p;
+ } else {
+ right_p = precprime(subis(right_p, 1));
+ p = right_p;
+ }
+ left = !left;
+ GEN t = subii(addis(p, 1), order);
+ GEN D = subii(sqri(t), mulis(p, 4));
+ GEN d = coredisc(D);
+ if (gequal0(min_d) || cmpii(d, min_d) > 0) {
+ debug_log("New min D = %Pi", d);
+ min_d = d;
+ }
+ if (cmpii(absi(d), d_range) < 0) {
+ debug_log("Good min D = %Pi", d);
+ } else if (cmpii(left_p, left_max_p) > 0 || cmpii(right_p, right_min_p) < 0) {
+ debug_log("Over p_range, D = %Pi", d);
+ } else {
+ continue;
+ }
+ cm_any_qdisc_t *result = try_calloc(sizeof(cm_any_qdisc_t));
+ result->p = p;
+ result->d = d;
+ gerepileall(ltop, 2, &result->p, &result->d);
+ return result;
+ };
+}
+
+*/
+/**
+ * @brief Find a fundamental quadratic discriminant < order^beta, start looking
+ * at the sides of the inverted Hasse interval around order, upto
+ * order^alpha width.
+ * @param order
+ * @param alpha
+ * @param beta
+ * @return
+ *//*
+
+static cm_any_qdisc_t *good_qdisc_brute(GEN order, GEN alpha, GEN beta) {
+ GEN ord_a = ground(gpow(order, alpha, DEFAULTPREC));
+ GEN ord_b = ground(gpow(order, beta, DEFAULTPREC));
+ return good_qdisc_brute_range(order, ord_a, ord_b);
+}
+*/
+
+GEN cm_construct_curve(GEN order, GEN d, GEN p, bool ord_prime) {
+ debug_log("Constructing a curve with N = %Pi, d = %Pi, p = %Pi", order, d,
+ p);
+ pari_sp ltop = avma;
+ GEN H = polclass(d, 0, 0);
+ debug_log("H = %Ps", H);
+
+ GEN r = FpX_roots(H, p);
+ debug_log("roots = %Ps", r);
+ if (gequal(r, gtovec(gen_0))) {
+ return NULL;
+ }
+
+ long rlen = glength(r);
+ for (long i = 1; i <= rlen; ++i) {
+ GEN root = gel(r, i);
+ debug_log("trying root = %Pi", root);
+
+ GEN e = ellinit(ellfromj(mkintmod(root, p)), p, 0);
+ pari_CATCH(e_TYPE) { continue; }
+ pari_TRY { checkell(e); };
+ pari_ENDCATCH{};
+
+ if (ord_prime) {
+ // Easy part, the requested order is prime so
+ // [order]G = 0 iff the curve has exactly order points, for any G on
+ // it. otherwise it is the twist
+ GEN g = genrand(e);
+ if (ell_is_inf(ellmul(e, g, order))) {
+ debug_log("Got curve.");
+ return gerepilecopy(ltop, e);
+ } else {
+ debug_log("Got curve twist.");
+ return gerepilecopy(ltop, ellinit(elltwist(e, NULL), p, 0));
+ }
+ } else {
+ // Hard part, requested order is composite, so it might share a
+ // factor with the order of the twist, which means [order]G = 0
+ // might be true for a point on the twist as well as a point o the
+ // right curve.
+ //
+ // We calculate what the twist order is, then compute gcd of the
+ // orders which leads to the product of the factors that the orders
+ // do not share. By multiplying a random point by this product on
+ // some curve, we can determine that that curve has that number of
+ // points.
+ GEN twist_order = subii(addis(p, 1), subii(order, addis(p, 1)));
+ GEN twist = ellinit(elltwist(e, NULL), p, 0);
+ GEN gcd = gcdii(order, twist_order);
+ GEN orig_mul = divii(order, gcd);
+ GEN twist_mul = divii(twist_order, gcd);
+ while (true) {
+ GEN orig_point = genrand(e);
+ if (ell_is_inf(ellmul(e, orig_point, orig_mul))) {
+ debug_log("Got curve.");
+ return gerepilecopy(ltop, e);
+ }
+ if (ell_is_inf(ellmul(e, orig_point, twist_mul))) {
+ debug_log("Got curve twist.");
+ return gerepilecopy(ltop, twist);
+ }
+ GEN twist_point = genrand(twist);
+ if (ell_is_inf(ellmul(e, twist_point, twist_mul))) {
+ debug_log("Got curve.");
+ return gerepilecopy(ltop, e);
+ }
+ if (ell_is_inf(ellmul(e, twist_point, orig_mul))) {
+ debug_log("Got curve twist.");
+ return gerepilecopy(ltop, twist);
+ }
+ };
+ }
+ }
+ return NULL;
+}
+
+curve_t *cm_any_curve(GEN order) {
+ cm_any_qdisc_t *min_disc = good_qdisc_minimal(order);
+ debug_log("Got min D = %Pi", min_disc->d);
+ GEN e = cm_construct_curve(order, min_disc->d, min_disc->p, false);
+ if (e == NULL) {
+ fprintf(err, "Could not construct curve.");
+ return NULL;
+ }
+ curve_t *curve = curve_new();
+ curve->field = min_disc->p;
+ curve->curve = e;
+ curve->a = ell_get_a4(e);
+ curve->b = ell_get_a6(e);
+ curve->order = gcopy(order);
+ try_free(min_disc);
+ return curve;
+} \ No newline at end of file
diff --git a/src/cm/cm_any.h b/src/cm/cm_any.h
new file mode 100644
index 0000000..c2ab350
--- /dev/null
+++ b/src/cm/cm_any.h
@@ -0,0 +1,22 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017-2018 J08nY
+ */
+#ifndef ECGEN_CM_ANY_H
+#define ECGEN_CM_ANY_H
+
+#include "misc/types.h"
+
+typedef struct {
+ GEN p;
+ GEN d;
+} cm_any_qdisc_t;
+
+/**
+ * @brief
+ * @param order
+ * @return
+ */
+curve_t *cm_any_curve(GEN order);
+
+#endif // ECGEN_CM_ANY_H
diff --git a/src/cm/custom.c b/src/cm/cm_prime.c
index 10caff4..267b8c1 100644
--- a/src/cm/custom.c
+++ b/src/cm/cm_prime.c
@@ -1,16 +1,15 @@
/*
* ecgen, tool for generating Elliptic curve domain parameters
- * Copyright (C) 2017 J08nY
+ * Copyright (C) 2017-2018 J08nY
*/
-#include "custom.h"
+#include "cm_prime.h"
#include "io/output.h"
#include "obj/curve.h"
#include "obj/point.h"
#include "obj/subgroup.h"
#include "util/bits.h"
-static size_t custom_add_primes(GEN r, GEN order, GEN **primes,
- size_t nprimes) {
+static size_t add_primes(GEN r, GEN order, GEN **primes, size_t nprimes) {
debug_log("add_primes r = %Pi, nprimes = %lu", r, nprimes);
size_t nalloc = nprimes;
if (nprimes == 0) {
@@ -49,44 +48,44 @@ static size_t custom_add_primes(GEN r, GEN order, GEN **primes,
return nprimes;
}
-static void custom_quadr_init(custom_quadr_t *quadr, GEN order) {
- quadr->D = gen_0;
- quadr->p = gen_0;
- quadr->t = gen_0;
+static void qdisc_init(cm_prime_qdisc_t *qdisc, GEN order) {
+ qdisc->D = gen_0;
+ qdisc->p = gen_0;
+ qdisc->t = gen_0;
- quadr->order = order;
- quadr->r = gen_0;
- quadr->i = gen_0;
- quadr->Sp = NULL;
- quadr->nprimes = 0;
+ qdisc->order = order;
+ qdisc->r = gen_0;
+ qdisc->i = gen_0;
+ qdisc->Sp = NULL;
+ qdisc->nprimes = 0;
}
-static void custom_quadr_next(custom_quadr_t *quadr) {
+static void qdisc_next(cm_prime_qdisc_t *qdisc) {
// Ok I get some state in r, i, Sp and nprimes.
// Here I want to check if I want to generate more primes into Sp
// Then continue with i
- GEN logN = ground(glog(quadr->order, BIGDEFAULTPREC));
- GEN rlog2 = sqri(mulii(addis(quadr->r, 1), logN));
+ GEN logN = ground(glog(qdisc->order, BIGDEFAULTPREC));
+ GEN rlog2 = sqri(mulii(addis(qdisc->r, 1), logN));
// When do I want more primes? If i == imax, or nprimes == 0
- GEN imax = int2n(quadr->nprimes);
- if (equalii(quadr->i, imax) || quadr->nprimes == 0) {
- quadr->nprimes = custom_add_primes(quadr->r, quadr->order, &(quadr->Sp),
- quadr->nprimes);
- imax = int2n(quadr->nprimes);
+ GEN imax = int2n(qdisc->nprimes);
+ if (equalii(qdisc->i, imax) || qdisc->nprimes == 0) {
+ qdisc->nprimes =
+ add_primes(qdisc->r, qdisc->order, &(qdisc->Sp), qdisc->nprimes);
+ imax = int2n(qdisc->nprimes);
}
pari_sp btop = avma;
while (true) {
- while (cmpii(quadr->i, imax) < 0) {
- // debug_log("i %Pi", quadr->i);
+ while (cmpii(qdisc->i, imax) < 0) {
+ // debug_log("i %Pi", qdisc->i);
GEN pprod = gen_1;
- bits_t *ibits = bits_from_i_len(quadr->i, quadr->nprimes);
- for (size_t j = 0; j < quadr->nprimes; ++j) {
+ bits_t *ibits = bits_from_i_len(qdisc->i, qdisc->nprimes);
+ for (size_t j = 0; j < qdisc->nprimes; ++j) {
if (GET_BIT(ibits->bits, j) == 1) {
- // debug_log("multiplying %Pi", quadr->Sp[j]);
- pprod = mulii(pprod, quadr->Sp[j]);
+ // debug_log("multiplying %Pi", qdisc->Sp[j]);
+ pprod = mulii(pprod, qdisc->Sp[j]);
}
}
bits_free(&ibits);
@@ -98,69 +97,63 @@ static void custom_quadr_next(custom_quadr_t *quadr) {
debug_log("candidate D = %Pi", pprod);
GEN x;
GEN y;
- if (!cornacchia2(absp, quadr->order, &x, &y)) {
- quadr->i = gerepileupto(btop, addis(quadr->i, 1));
+ if (!cornacchia2(absp, qdisc->order, &x, &y)) {
+ qdisc->i = gerepileupto(btop, addis(qdisc->i, 1));
// debug_log("Cornacchia fail");
continue;
}
- GEN pp1 = addii(addis(quadr->order, 1), x);
- GEN pp2 = subii(addis(quadr->order, 1), x);
+ GEN pp1 = addii(addis(qdisc->order, 1), x);
+ GEN pp2 = subii(addis(qdisc->order, 1), x);
if (isprime(pp1)) {
- quadr->p = pp1;
- quadr->D = pprod;
- quadr->t = x;
- quadr->i = addis(quadr->i, 1);
+ qdisc->p = pp1;
+ qdisc->D = pprod;
+ qdisc->t = x;
+ qdisc->i = addis(qdisc->i, 1);
debug_log("good D %Pi", pprod);
return;
}
if (isprime(pp2)) {
- quadr->p = pp2;
- quadr->D = pprod;
- quadr->t = x;
- quadr->i = addis(quadr->i, 1);
+ qdisc->p = pp2;
+ qdisc->D = pprod;
+ qdisc->t = x;
+ qdisc->i = addis(qdisc->i, 1);
debug_log("good D %Pi", pprod);
return;
}
}
- quadr->i = gerepileupto(btop, addis(quadr->i, 1));
+ qdisc->i = gerepileupto(btop, addis(qdisc->i, 1));
}
- quadr->r = addis(quadr->r, 1);
- quadr->nprimes = custom_add_primes(quadr->r, quadr->order, &(quadr->Sp),
- quadr->nprimes);
- rlog2 = sqri(mulii(addis(quadr->r, 1), logN));
- imax = int2n(quadr->nprimes);
+ qdisc->r = addis(qdisc->r, 1);
+ qdisc->nprimes =
+ add_primes(qdisc->r, qdisc->order, &(qdisc->Sp), qdisc->nprimes);
+ rlog2 = sqri(mulii(addis(qdisc->r, 1), logN));
+ imax = int2n(qdisc->nprimes);
btop = avma;
}
}
-static void custom_quadr_free(custom_quadr_t *quadr) { try_free(quadr->Sp); }
-
-curve_t *custom_curve() {
- GEN order = strtoi(cfg->cm_order);
- if (!isprime(order)) {
- fprintf(err, "Currently, order must be prime for CM to work.\n");
- return NULL;
- }
+static void qdisc_free(cm_prime_qdisc_t *qdisc) { try_free(qdisc->Sp); }
+curve_t *cm_prime_curve(GEN order) {
GEN a = NULL;
GEN b = NULL;
GEN e = NULL;
GEN g = NULL;
- custom_quadr_t quadr;
- custom_quadr_init(&quadr, order);
+ cm_prime_qdisc_t qdisc;
+ qdisc_init(&qdisc, order);
while (true) {
- custom_quadr_next(&quadr);
+ qdisc_next(&qdisc);
debug_log("order = %Pi", order);
- debug_log("p = %Pi, t = %Pi, D = %Pi, ", quadr.p, quadr.t, quadr.D);
- GEN H = polclass(quadr.D, 0, 0);
+ debug_log("p = %Pi, t = %Pi, D = %Pi, ", qdisc.p, qdisc.t, qdisc.D);
+ GEN H = polclass(qdisc.D, 0, 0);
debug_log("H = %Ps", H);
- GEN r = FpX_roots(H, quadr.p);
+ GEN r = FpX_roots(H, qdisc.p);
debug_log("roots = %Ps", r);
if (gequal(r, gtovec(gen_0))) {
continue;
@@ -173,12 +166,12 @@ curve_t *custom_curve() {
GEN root = gel(r, i);
a = mkintmod(
Fp_div(
- Fp_mul(stoi(27), root, quadr.p),
- Fp_mul(stoi(4), Fp_sub(stoi(1728), root, quadr.p), quadr.p),
- quadr.p),
- quadr.p);
+ Fp_mul(stoi(27), root, qdisc.p),
+ Fp_mul(stoi(4), Fp_sub(stoi(1728), root, qdisc.p), qdisc.p),
+ qdisc.p),
+ qdisc.p);
b = gneg(a);
- e = ellinit(mkvec2(a, b), quadr.p, 0);
+ e = ellinit(mkvec2(a, b), qdisc.p, 0);
pari_CATCH(e_TYPE) { continue; }
pari_TRY { checkell(e); };
pari_ENDCATCH{};
@@ -195,10 +188,10 @@ curve_t *custom_curve() {
if (has_curve) break;
}
- custom_quadr_free(&quadr);
+ qdisc_free(&qdisc);
curve_t *result = curve_new();
- result->field = quadr.p;
+ result->field = qdisc.p;
result->a = a;
result->b = b;
result->curve = e;
diff --git a/src/cm/custom.h b/src/cm/cm_prime.h
index ddb89fe..59debac 100644
--- a/src/cm/custom.h
+++ b/src/cm/cm_prime.h
@@ -1,15 +1,15 @@
/*
* ecgen, tool for generating Elliptic curve domain parameters
- * Copyright (C) 2017 J08nY
+ * Copyright (C) 2017-2018 J08nY
*/
-#ifndef ECGEN_CUSTOM_H
-#define ECGEN_CUSTOM_H
+#ifndef ECGEN_CM_PRIME_H
+#define ECGEN_CM_PRIME_H
#include "misc/config.h"
#include "misc/types.h"
typedef struct {
- /* Stuff filled with custom_quadr_next. */
+ /* Stuff filled with qdisc_next. */
GEN p;
GEN t;
GEN D;
@@ -20,14 +20,15 @@ typedef struct {
GEN i;
GEN* Sp;
size_t nprimes;
-} custom_quadr_t;
+} cm_prime_qdisc_t;
/**
* Algorithm mostly from:
* Constructing elliptic curves of prime order
* by Reinier Broker and Peter Stevenhagen
+ * @param order the requested order, must be prime
* @return
*/
-curve_t* custom_curve();
+curve_t* cm_prime_curve(GEN order);
-#endif // ECGEN_CUSTOM_H
+#endif // ECGEN_CM_PRIME_H
diff --git a/src/ecgen.c b/src/ecgen.c
index dc79ed2..76fae79 100644
--- a/src/ecgen.c
+++ b/src/ecgen.c
@@ -58,7 +58,7 @@ bool init(void) {
default0("datadir", cfg->datadir);
}
-#ifdef DEBUG
+#ifdef PARI_DEBUG
default0("debug", "2");
#endif
diff --git a/test/ecgen.sh b/test/ecgen.sh
index e9fbe66..fd1da25 100755
--- a/test/ecgen.sh
+++ b/test/ecgen.sh
@@ -153,7 +153,7 @@ function hex() {
function cm() {
start_test
- assert_raises "${ecgen} --fp --order=2147483723 32" 1
+ assert_raises "${ecgen} --fp --order=2147483723 32"
assert_raises "${ecgen} --fp --order=123456789012345678901234567890123456789012345678901234568197 137"
}
diff --git a/test/src/cm/test_custom.c b/test/src/cm/test_cm.c
index df1ada8..d3f8257 100644
--- a/test/src/cm/test_custom.c
+++ b/test/src/cm/test_cm.c
@@ -1,47 +1,52 @@
/*
* ecgen, tool for generating Elliptic curve domain parameters
- * Copyright (C) 2017 J08nY
+ * Copyright (C) 2017-2018 J08nY
*/
#include <criterion/criterion.h>
-#include "cm/custom.h"
+#include "cm/cm_any.h"
+#include "cm/cm_prime.h"
#include "obj/curve.h"
#include "test/default.h"
#include "test/input.h"
#include "test/output.h"
#include "util/random.h"
-void custom_setup() {
+void cm_setup() {
default_setup();
input_setup();
output_setup();
random_init();
}
-void custom_teardown() {
+void cm_teardown() {
default_teardown();
input_teardown();
output_teardown();
}
-TestSuite(custom, .init = custom_setup, .fini = custom_teardown);
+TestSuite(cm, .init = cm_setup, .fini = cm_teardown);
-Test(custom, test_curve_one) {
+Test(cm, test_curve_prime) {
cfg->bits = 128;
cfg->cm_order = "263473633827487324648193013259296339349";
GEN order = strtoi(cfg->cm_order);
- curve_t *curve = custom_curve();
+ curve_t *curve = cm_prime_curve(order);
cr_assert_not_null(curve, );
cr_assert(equalii(curve->order, order), );
cr_assert(equalii(ellcard(curve->curve, NULL), order), );
curve_free(&curve);
}
-Test(custom, test_curve_other) {
- cfg->bits = 32;
- cfg->cm_order = "2147483723";
+Test(cm, test_curve_composite) {
+ cfg->bits = 64;
+ cfg->cm_order = "13282407956253574712";
+ GEN order = strtoi(cfg->cm_order);
- curve_t *curve = custom_curve();
- cr_assert_null(curve, );
+ curve_t *curve = cm_any_curve(order);
+ cr_assert_not_null(curve, );
+ cr_assert(equalii(curve->order, order), );
+ cr_assert(equalii(ellcard(curve->curve, NULL), order), );
+ curve_free(&curve);
} \ No newline at end of file
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 12:07:28 +0000