diff options
53 files changed, 588 insertions, 250 deletions
diff --git a/.github/workflows/release.yml b/.github/workflows/release.yml index 61c8fc3..170ce0f 100644 --- a/.github/workflows/release.yml +++ b/.github/workflows/release.yml @@ -9,7 +9,7 @@ jobs: release: runs-on: ubuntu-24.04 steps: - - uses: actions/checkout@v4 + - uses: actions/checkout@v6 with: submodules: true - name: Setup pari @@ -20,7 +20,19 @@ jobs: run: | make strip ecgen + mv ecgen ecgen-release + make clean + make STATIC=1 + mv ecgen ecgen-static + make clean + make DEBUG=1 + mv ecgen ecgen-debug + make clean + mv ecgen-release ecgen - name: Release uses: softprops/action-gh-release@v2 with: - files: ecgen + files: | + ecgen + ecgen-static + ecgen-debug diff --git a/.github/workflows/test.yml b/.github/workflows/test.yml index 59de7c8..76d9ecf 100644 --- a/.github/workflows/test.yml +++ b/.github/workflows/test.yml @@ -11,13 +11,21 @@ jobs: env: CC: ${{ matrix.CC }} steps: - - uses: actions/checkout@v4 + - uses: actions/checkout@v6 with: submodules: true - name: Setup pari run: | sudo apt-get update sudo apt-get install -y libpari-dev pari-gp pari-seadata meson ninja-build + - name: Build + run: | + make + make clean + make STATIC=1 + make clean + make DEBUG=1 + make clean - name: Test run: | TEST=1 make unittest @@ -26,7 +34,7 @@ jobs: run: | cd src && find . -name "*.gcda" -exec gcov -pb "{}" +; - name: Code coverage upload - uses: codecov/codecov-action@v4 + uses: codecov/codecov-action@v5 if: ${{ matrix.CC == 'gcc' }} with: env_vars: CC diff --git a/CMakeLists.txt b/CMakeLists.txt index 04d8f36..a08c21c 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -28,4 +28,10 @@ else () set(PLATFORM_SPECIFIC_LIBS rt) endif() -target_link_libraries(ecgen pthread pari parson sha1 ${PLATFORM_SPECIFIC_LIBS}) +if (STATIC) + # Find the static libpari library + find_library(PARI_STATIC NAMES libpari.a) + target_link_libraries(ecgen pthread ${PARI_STATIC} parson sha1 ${PLATFORM_SPECIFIC_LIBS}) +else () + target_link_libraries(ecgen pthread pari parson sha1 ${PLATFORM_SPECIFIC_LIBS}) +endif() @@ -38,7 +38,7 @@ PROJECT_NAME = "ecgen" # could be handy for archiving the generated documentation or if some version # control system is used. -PROJECT_NUMBER = 0.7.7 +PROJECT_NUMBER = 0.8.2 # Using the PROJECT_BRIEF tag one can provide an optional one line description # for a project that appears at the top of each page and should give viewer a @@ -50,7 +50,7 @@ Tool for generating Elliptic curve domain parameters. - `-d / --data-dir=DIR` Set PARI/GP data directory (containing seadata package). - `-m / --memory=SIZE` Use PARI stack of `SIZE` (can have suffix k/m/g). - - `--threads=NUM` Use `NUM` threads. + - `--threads=NUM` Use `NUM` threads (in PARI or invalid generation). - `--thread-stack=SIZE` Use PARI stack of `SIZE` (per thread, can have suffix k/m/g). - `--timeout=TIME` Timeout computation of a curve parameter after `TIME` (can have suffix s/m/h/d). diff --git a/src/cm/anomalous.c b/src/cm/anomalous.c index 70df8e4..36d6890 100644 --- a/src/cm/anomalous.c +++ b/src/cm/anomalous.c @@ -8,7 +8,7 @@ static disc_t **disc_table; -void anomalous_init() { +void anomalous_init(void) { disc_table = try_calloc(sizeof(disc_t *) * 5); for (int i = 0; i < 5; ++i) { disc_table[i] = try_calloc(sizeof(disc_t)); @@ -128,7 +128,7 @@ GENERATOR(anomalous_gen_order) { return 1; } -void anomalous_quit() { +void anomalous_quit(void) { if (disc_table) { for (int i = 0; i < 5; ++i) { if (disc_table[i]) { diff --git a/src/cm/anomalous.h b/src/cm/anomalous.h index 73b84fd..6e897d5 100644 --- a/src/cm/anomalous.h +++ b/src/cm/anomalous.h @@ -49,12 +49,12 @@ GENERATOR(anomalous_gen_order); /** * @brief Initialize anomalous generation, allocate and set the disc_table. */ -void anomalous_init(); +void anomalous_init(void); /** * @brief Deinitialize anomalous generation, free the discriminants from the * disc_table. */ -void anomalous_quit(); +void anomalous_quit(void); #endif // ECGEN_CM_ANOMALOUS_H diff --git a/src/cm/cm.c b/src/cm/cm.c index 9dffc1d..649df4d 100644 --- a/src/cm/cm.c +++ b/src/cm/cm.c @@ -69,12 +69,14 @@ static void cm_ginit(gen_f *generators, bool prime) { if (prime) { generators[OFFSET_CURVE] = &cm_gen_curve_prime; generators[OFFSET_POINTS] = &points_gen_prime; + } else if (GET_BOOL(unique)) { + generators[OFFSET_CURVE] = &cm_gen_curve_unique; } else { generators[OFFSET_CURVE] = &cm_gen_curve_any; } generators[OFFSET_ORDER] = &cm_gen_order; } else if (cfg->method == METHOD_ANOMALOUS) { - GET(random); // Used within the method. + GET(random); // Used within the method. generators[OFFSET_FIELD] = &anomalous_gen_field; generators[OFFSET_A] = &gen_skip; generators[OFFSET_B] = &anomalous_gen_equation; @@ -181,10 +183,15 @@ static int cm_init(exhaustive_t *setup) { for (long j = 1; j <= len; ++j) { GEN factor = gel(factors, j); if (isprime(factor)) { + debug_log("Adding prime factor %Pi", factor); addprimes(gtovec(factor)); } else { - GEN factored = Z_factor(order); - addprimes(gel(factored, 1)); + GEN factored = Z_factor(factor); + GEN primes = gel(factored, 1); + for (long k = 1; k <= glength(primes); ++k) { + debug_log("Adding prime factor %Pi", gel(primes, k)); + addprimes(gel(primes, k)); + } } order = mulii(order, factor); } @@ -195,6 +202,10 @@ static int cm_init(exhaustive_t *setup) { fprintf(err, "Order requested not a number: %s\n", cfg->cm_order); return 1; } + if (cmpiu(order, 5) < 0) { + pari_fprintf(err, "Order requested too small: %Pi\n", order); + return 1; + } long ord_log = logint0(order, gen_2, NULL); if (ord_log > cfg->bits) { pari_fprintf(err, @@ -226,10 +237,11 @@ static void cm_quit(exhaustive_t *setup) { if (cfg->method == METHOD_ANOMALOUS) { anomalous_quit(); } + cm_any_quit(); exhaustive_clear(setup); } -int cm_do() { +int cm_do(void) { debug_log_start("Starting Complex Multiplication method"); gen_f generators[OFFSET_END] = {NULL}; diff --git a/src/cm/cm.h b/src/cm/cm.h index b80d987..a130366 100644 --- a/src/cm/cm.h +++ b/src/cm/cm.h @@ -15,6 +15,6 @@ * * @return */ -int cm_do(); +int cm_do(void); #endif // ECGEN_CM_CM_H diff --git a/src/cm/cm_any.c b/src/cm/cm_any.c index f948ac1..0e5ed7c 100644 --- a/src/cm/cm_any.c +++ b/src/cm/cm_any.c @@ -16,17 +16,22 @@ */ static void good_qdisc_minimal(cm_any_qdisc_t *qdisc, GEN order) { pari_sp ltop = avma; - GEN d = stoi(2); - size_t j = 0; + GEN d; + if (qdisc->d) { + d = negi(subis(qdisc->d, 1)); + } else { + d = stoi(2); + } + size_t j = 1; while (true) { ++j; + if (j % 100 == 0) { + debug_log("d: %Ps", d); + } if (!issquarefree(d)) { d = addis(d, 1); continue; } - if (j % 100 == 0) { - debug_log("D: %Ps", d); - } GEN D = quaddisc(negi(d)); GEN K = Buchall(quadpoly(D), 0, DEFAULTPREC); GEN alphas = bnfisintnorm(K, order); @@ -52,7 +57,7 @@ static void good_qdisc_minimal(cm_any_qdisc_t *qdisc, GEN order) { } } -/** +/* * @brief Find a fundamental quadratic discriminant < d_range, start looking * at the sides of the inverted Hasse interval around order, upto p_range * @@ -114,9 +119,9 @@ static cm_any_qdisc_t *good_qdisc_brute_range(GEN order, GEN p_range, GEN d_rang 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. @@ -124,115 +129,105 @@ static cm_any_qdisc_t *good_qdisc_brute_range(GEN order, GEN p_range, GEN d_rang * @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 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) { +void cm_update_roots(GEN d, GEN p, cm_any_roots_t *roots) { + pari_sp ltop = avma; + GEN H = polclass(d, 0, 0); + GEN raw = FpX_roots(H, p); + if (roots->roots && isclone(roots->roots)) { + gunclone(roots->roots); + } + roots->roots = gclone(raw); + roots->total = glength(raw); + roots->used = 0; + avma = ltop; +} + +cm_any_roots_t *cm_make_roots(GEN d, GEN p) { + debug_log("Making roots, d = %Pi, p = %Pi", d, p); + cm_any_roots_t *roots = try_calloc(sizeof(cm_any_roots_t)); + cm_update_roots(d, p, roots); + return roots; +} + +void cm_free_roots(cm_any_roots_t *roots) { + if (roots) { + if (roots->roots && isclone(roots->roots)) { + gunclone(roots->roots); + } + try_free(roots); + } +} + +GEN cm_construct_curve(GEN order, GEN d, GEN p, cm_any_roots_t *roots, + 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))) { + debug_log("roots(%li/%li) = %Ps", roots->used, roots->total, roots->roots); + if (roots->total == 0 || roots->used == roots->total || + gequal(roots->roots, gtovec(gen_0))) { avma = ltop; return NULL; } - long rlen = glength(r); - for (long i = 1; i <= rlen; ++i) { - GEN root = gel(r, i); - debug_log("trying root = %Pi", root); + for (long i = roots->used; i < roots->total; ++i) { + roots->used = i + 1; + GEN root = gel(roots->roots, i + 1); + if (gequal(root, gen_0) || equaliu(root, 1728)) { + debug_log("skipping root = 0 or 1728"); + continue; + } + debug_log("trying root[%i] = %Pi", i + 1, root); - GEN e = ellinit(ellfromj(mkintmod(root, p)), p, 0); + GEN e1 = ellinit(ellfromj(mkintmod(root, p)), p, 0); pari_CATCH(e_TYPE) { continue; } - pari_TRY { checkell(e); }; + pari_TRY { checkell(e1); }; pari_ENDCATCH{}; + debug_log("ellinit done"); - 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)); - } + GEN ord = ellff_get_card(e1); + if (equalii(ord, order)) { + return gerepilecopy(ltop, e1); } 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); - } - } + GEN e2 = ellinit(elltwist(e1, NULL), p, 0); + return gerepilecopy(ltop, e2); } } avma = ltop; return NULL; } -GEN cm_construct_curve_subgroup(GEN r, GEN d, GEN p) { - debug_log("Constructing a curve with r = %Pi, d = %Pi, p = %Pi", r, d, - p); +GEN cm_construct_curve_subgroup(GEN r, GEN d, GEN p, cm_any_roots_t *roots) { + debug_log("Constructing a curve with r = %Pi, d = %Pi, p = %Pi", r, d, p); pari_sp ltop = avma; - GEN H = polclass(d, 0, 0); - debug_log("H = %Ps", H); - GEN roots = FpX_roots(H, p); - debug_log("roots = %Ps", roots); - if (gequal(roots, gtovec(gen_0))) { + debug_log("roots(%li/%li) = %Ps", roots->used, roots->total, roots->roots); + if (roots->total == 0 || roots->used == roots->total || + gequal(roots->roots, gtovec(gen_0))) { avma = ltop; return NULL; } - long rlen = glength(roots); pari_sp btop = avma; - for (long i = 1; i <= rlen; ++i) { - GEN root = gel(roots, i); - debug_log("trying root = %Pi", root); + for (long i = roots->used; i < roots->total; ++i) { + roots->used = i + 1; + GEN root = gel(roots->roots, i + 1); + debug_log("trying root[%i] = %Pi", i + 1, root); GEN e = ellinit(ellfromj(mkintmod(root, p)), p, 0); - pari_CATCH(e_TYPE) { avma = btop; continue; } + pari_CATCH(e_TYPE) { + avma = btop; + continue; + } pari_TRY { checkell(e); }; pari_ENDCATCH{}; @@ -247,21 +242,173 @@ GEN cm_construct_curve_subgroup(GEN r, GEN d, GEN p) { return NULL; } +static cm_any_qdisc_t *min_d = NULL; +static cm_any_roots_t *min_roots = NULL; +static curve_t *min_curve = NULL; + GENERATOR(cm_gen_curve_any) { HAS_ARG(args); pari_sp ltop = avma; const char *order_s = (const char *)args->args; GEN order = strtoi(order_s); - cm_any_qdisc_t min_disc = {0}; - good_qdisc_minimal(&min_disc, order); - debug_log("Got min D = %Pi", min_disc.d); - GEN e = cm_construct_curve(order, min_disc.d, min_disc.p, false); + GEN e; + if (min_d && min_roots && min_curve == curve && + min_roots->used < min_roots->total) { + debug_log("Reusing roots."); + // We can just use the roots we have stored and take some out. + e = cm_construct_curve(order, min_d->d, min_d->p, min_roots, false); + } else if (min_d && min_curve == curve) { + debug_log("Reusing min D = %Pi", min_d->d); + // We just have the discriminant but no roots (or they are used up), we + // need to continue + if (min_d->d && isclone(min_d->d)) { + gunclone(min_d->d); + } + if (min_d->p && isclone(min_d->p)) { + gunclone(min_d->p); + } + good_qdisc_minimal(min_d, order); + min_d->d = gclone(min_d->d); + min_d->p = gclone(min_d->p); + debug_log("Got min D = %Pi", min_d->d); + if (min_roots) { + cm_update_roots(min_d->d, min_d->p, min_roots); + } else { + min_roots = cm_make_roots(min_d->d, min_d->p); + } + e = cm_construct_curve(order, min_d->d, min_d->p, min_roots, false); + } else { + // We have nothing. Start fresh. + debug_log("Fresh start."); + if (!min_d) { + min_d = try_calloc(sizeof(cm_any_qdisc_t)); + } + if (min_d->d && isclone(min_d->d)) { + gunclone(min_d->d); + } + if (min_d->p && isclone(min_d->p)) { + gunclone(min_d->p); + } + good_qdisc_minimal(min_d, order); + min_d->d = gclone(min_d->d); + min_d->p = gclone(min_d->p); + debug_log("Got min D = %Pi", min_d->d); + min_roots = cm_make_roots(min_d->d, min_d->p); + min_curve = curve; + e = cm_construct_curve(order, min_d->d, min_d->p, min_roots, false); + } + + if (e == NULL) { + debug_log("Could not construct curve."); + avma = ltop; + return -3; + } + curve->field = gcopy(min_d->p); + curve->a = ell_get_a4(e); + curve->b = ell_get_a6(e); + curve->curve = e; + return 1; +} + +GENERATOR(cm_gen_curve_unique) { + HAS_ARG(args); + pari_sp ltop = avma; + const char *order_s = (const char *)args->args; + GEN order = strtoi(order_s); + GEN e; + if (min_d && min_curve == curve) { + debug_log("Reusing min D = %Pi", min_d->d); + // We have some discriminant, cannot use the roots because the D with + // walkdown was too large. + if (min_d->d && isclone(min_d->d)) { + gunclone(min_d->d); + } + if (min_d->p && isclone(min_d->p)) { + gunclone(min_d->p); + } + good_qdisc_minimal(min_d, order); + min_d->d = gclone(min_d->d); + min_d->p = gclone(min_d->p); + debug_log("Got min D = %Pi", min_d->d); + if (min_roots) { + cm_update_roots(min_d->d, min_d->p, min_roots); + } else { + min_roots = cm_make_roots(min_d->d, min_d->p); + } + e = cm_construct_curve(order, min_d->d, min_d->p, min_roots, false); + } else { + // We have nothing. Start fresh. + debug_log("Fresh start."); + if (!min_d) { + min_d = try_calloc(sizeof(cm_any_qdisc_t)); + } + if (min_d->d && isclone(min_d->d)) { + gunclone(min_d->d); + } + if (min_d->p && isclone(min_d->p)) { + gunclone(min_d->p); + } + good_qdisc_minimal(min_d, order); + min_d->d = gclone(min_d->d); + min_d->p = gclone(min_d->p); + debug_log("Got min D = %Pi", min_d->d); + min_roots = cm_make_roots(min_d->d, min_d->p); + min_curve = curve; + e = cm_construct_curve(order, min_d->d, min_d->p, min_roots, false); + } + if (e == NULL) { - fprintf(err, "Could not construct curve."); + debug_log("Could not construct curve."); avma = ltop; return -3; } - curve->field = min_disc.p; + + GEN group = ellff_get_group(e); + long len = glength(group); + if (len == 2) { + pari_sp btop = avma; + debug_log("Walking down with structure %Ps.", group); + GEN d = gcopy(min_d->d); + GEN one = gel(group, 1); + GEN two = gel(group, 2); + GEN towalk = cmpii(one, two) < 0 ? one : two; + GEN factored = Z_factor(towalk); + GEN primes = gel(factored, 1); + GEN powers = gel(factored, 2); + for (long i = 1; i <= glength(primes); ++i) { + GEN prime = gel(primes, i); + GEN power = gel(powers, i); + debug_log("Walking down with %Pi^(2*%Pi)", prime, power); + GEN exp = mulis(power, 2); + GEN mul = powii(prime, exp); + debug_log("%Pi^%Pi = %Pi", prime, exp, mul); + d = mulii(d, mul); + debug_log("d = %Pi", d); + } + long dsize = logint(d, gen_2); + if (dsize > 30) { + debug_log( + "Discriminant too large after walkdown (d = %Pi, %li bits).", d, + dsize); + avma = ltop; + return -3; + } + if (min_roots) { + cm_update_roots(d, min_d->p, min_roots); + } else { + min_roots = cm_make_roots(d, min_d->p); + } + e = cm_construct_curve(order, d, min_d->p, min_roots, false); + e = gerepilecopy(btop, e); + } + + if (e == NULL) { + debug_log("Could not construct curve."); + avma = ltop; + return -3; + } + + curve->field = gcopy(min_d->p); curve->a = ell_get_a4(e); curve->b = ell_get_a6(e); curve->curve = e; @@ -273,4 +420,19 @@ GENERATOR(cm_gen_order) { const char *order_s = (const char *)args->args; curve->order = strtoi(order_s); return 1; -}
\ No newline at end of file +} + +void cm_any_quit(void) { + if (min_d) { + if (min_d->d && isclone(min_d->d)) { + gunclone(min_d->d); + } + if (min_d->p && isclone(min_d->p)) { + gunclone(min_d->p); + } + try_free(min_d); + } + if (min_roots) { + cm_free_roots(min_roots); + } +} diff --git a/src/cm/cm_any.h b/src/cm/cm_any.h index a49fd7f..873b68f 100644 --- a/src/cm/cm_any.h +++ b/src/cm/cm_any.h @@ -12,22 +12,53 @@ typedef struct { GEN d; } cm_any_qdisc_t; +typedef struct { + GEN roots; + long used; + long total; +} cm_any_roots_t; + +/** + * + * @param d + * @param p + * @param roots + */ +void cm_update_roots(GEN d, GEN p, cm_any_roots_t *roots); + +/** + * + * @param d + * @param p + * @return + */ +cm_any_roots_t *cm_make_roots(GEN d, GEN p); + +void cm_free_roots(cm_any_roots_t *roots); + /** * @brief Construct an elliptic curve given its order, CM discriminant and field * order. * @param order * @param d * @param p + * @param roots * @param ord_prime * @return */ -GEN cm_construct_curve(GEN order, GEN d, GEN p, bool ord_prime); +GEN cm_construct_curve(GEN order, GEN d, GEN p, cm_any_roots_t *roots, + bool ord_prime); /** * @brief Construct an elliptic curve given a factor of its order, CM * discriminant and field order. + * + * @param r + * @param d + * @param p + * @param roots */ -GEN cm_construct_curve_subgroup(GEN r, GEN d, GEN p); +GEN cm_construct_curve_subgroup(GEN r, GEN d, GEN p, cm_any_roots_t *roots); /** * @brief @@ -45,6 +76,20 @@ GENERATOR(cm_gen_curve_any); * @param state * @return */ +GENERATOR(cm_gen_curve_unique); + +/** + * @brief + * @param curve + * @param args + * @param state + * @return + */ GENERATOR(cm_gen_order); +/** + * @brief Deinitialize. + */ +void cm_any_quit(void); + #endif // ECGEN_CM_ANY_H diff --git a/src/cm/cm_prime.c b/src/cm/cm_prime.c index 33d2a12..91c79c8 100644 --- a/src/cm/cm_prime.c +++ b/src/cm/cm_prime.c @@ -11,6 +11,11 @@ #include "obj/subgroup.h" #include "util/bits.h" +/* + * This file implements Algorithm 2.2 from + * "Constructing elliptic curves of prime order" + * https://pub.math.leidenuniv.nl/~stevenhagenp/bs.pdf + */ 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; @@ -44,8 +49,9 @@ static size_t add_primes(GEN r, GEN order, GEN **primes, size_t nprimes) { (*primes)[nprimes++] = pstar; } } - - *primes = try_realloc(*primes, sizeof(GEN) * nprimes); + if (nprimes) { + *primes = try_realloc(*primes, sizeof(GEN) * nprimes); + } return nprimes; } @@ -75,60 +81,75 @@ static void qdisc_next(cm_prime_qdisc_t *qdisc) { if (equalii(qdisc->i, imax) || qdisc->nprimes == 0) { qdisc->nprimes = add_primes(qdisc->r, qdisc->order, &(qdisc->Sp), qdisc->nprimes); + qdisc->i = gen_0; imax = int2n(qdisc->nprimes); } pari_sp btop = avma; while (true) { - while (cmpii(qdisc->i, imax) < 0) { + debug_log("Primes:"); + for (size_t j = 0; j < qdisc->nprimes; ++j) { + debug_log("%Pi", qdisc->Sp[j]); + } + + GEN i = qdisc->i; + while (cmpii(i, imax) < 0) { // debug_log("i %Pi", qdisc->i); GEN pprod = gen_1; - bits_t *ibits = bits_from_i_len(qdisc->i, qdisc->nprimes); + bits_t *ibits = bits_from_i_len(i, qdisc->nprimes); + char *b = bits_to_bin(ibits); + debug_log("bits: %s", b); + try_free(b); for (size_t j = 0; j < qdisc->nprimes; ++j) { if (GET_BIT(ibits->bits, j) == 1) { - // debug_log("multiplying %Pi", qdisc->Sp[j]); pprod = mulii(pprod, qdisc->Sp[j]); } } bits_free(&ibits); + debug_log("pprod = %Pi, rlog^2 = %Pi, m8 = %Pi", pprod, rlog2, + modis(pprod, 8)); GEN absp = absi(pprod); - long m4 = mod4(absp); - if (cmpii(absp, rlog2) < 0 && equalii(modis(pprod, 8), stoi(5)) && - m4 != 1 && m4 != 2) { + // long m4 = mod4(absp); + if (cmpii(absp, rlog2) < 0 && + equalii(modis(pprod, 8), stoi(5)) // && m4 != 1 && m4 != 2 + ) { debug_log("candidate D = %Pi", pprod); GEN x = NULL; GEN y = NULL; + // TODO: Check cornacchia -D vs +D if (!cornacchia2(absp, qdisc->order, &x, &y)) { - qdisc->i = gerepileupto(btop, addis(qdisc->i, 1)); - // debug_log("Cornacchia fail"); + i = gerepileupto(btop, addis(i, 1)); + debug_log("Cornacchia fail"); continue; } GEN pp1 = addii(addis(qdisc->order, 1), x); GEN pp2 = subii(addis(qdisc->order, 1), x); - if (isprime(pp1)) { + if (isprime(pp1) && cmpiu(pp1, 5) >= 0) { qdisc->p = pp1; qdisc->D = pprod; qdisc->t = x; - qdisc->i = addis(qdisc->i, 1); + qdisc->i = addis(i, 1); debug_log("good D %Pi", pprod); return; } - if (isprime(pp2)) { + if (isprime(pp2) && cmpiu(pp2, 5) >= 0) { qdisc->p = pp2; qdisc->D = pprod; qdisc->t = x; - qdisc->i = addis(qdisc->i, 1); + qdisc->i = addis(i, 1); debug_log("good D %Pi", pprod); return; } } - qdisc->i = gerepileupto(btop, addis(qdisc->i, 1)); + i = gerepileupto(btop, addis(i, 1)); } + // Another r loop qdisc->r = addis(qdisc->r, 1); qdisc->nprimes = add_primes(qdisc->r, qdisc->order, &(qdisc->Sp), qdisc->nprimes); + qdisc->i = gen_0; rlog2 = sqri(mulii(addis(qdisc->r, 1), logN)); imax = int2n(qdisc->nprimes); @@ -146,15 +167,18 @@ GENERATOR(cm_gen_curve_prime) { cm_prime_qdisc_t qdisc = {0}; qdisc_init(&qdisc, order); + cm_any_roots_t *roots = try_calloc(sizeof(cm_any_roots_t)); do { qdisc_next(&qdisc); - e = cm_construct_curve(order, qdisc.D, qdisc.p, true); + cm_update_roots(qdisc.D, qdisc.p, roots); + e = cm_construct_curve(order, qdisc.D, qdisc.p, roots, true); } while (e == NULL); qdisc_free(&qdisc); + cm_free_roots(roots); curve->field = qdisc.p; curve->a = ell_get_a4(e); curve->b = ell_get_a6(e); curve->curve = e; return 1; -}
\ No newline at end of file +} diff --git a/src/cm/p1363.c b/src/cm/p1363.c index fad2a05..90dcfd2 100644 --- a/src/cm/p1363.c +++ b/src/cm/p1363.c @@ -449,4 +449,4 @@ GEN p1363_polclass(GEN D) { GEN WD = p1363_poly(D, forms, nforms); p1363_free(&forms, nforms); return gerepileupto(ltop, WD); -}
\ No newline at end of file +} diff --git a/src/ecgen.c b/src/ecgen.c index 3c9b227..7e2074e 100644 --- a/src/ecgen.c +++ b/src/ecgen.c @@ -20,7 +20,7 @@ /** * @file ecgen.c * @author J08nY <johny@neuromancer.sk> - * @version 0.7.7 + * @version 0.8.2 * @copyright GPL v2.0 */ #include <pari/pari.h> @@ -38,11 +38,11 @@ #endif const char *argp_program_version = - "ecgen 0.7.7" GIT_VERSION + "ecgen 0.8.2" GIT_VERSION "\n" "Compiled with: " PARIVERSION "\n\n" - "Copyright (C) 2017-2018,2021,2024 J08nY\n" + "Copyright (C) 2017-2018,2021,2024,2025 J08nY\n" "License GPLv2: GNU GPL version 2 (or later) " "<http://gnu.org/licenses/gpl.html>\n" "This is free software: you are free to change and redistribute it.\n" @@ -67,6 +67,13 @@ bool init(void) { default0("datadir", cfg->datadir); } + // set threads limit for PARI + if (cfg->threads) { + char threads_s[30]; + snprintf(threads_s, 30, "%lu", cfg->threads); + default0("nbthreads", threads_s); + } + #ifdef PARI_DEBUG default0("debug", "2"); #endif diff --git a/src/exhaustive/ansi.c b/src/exhaustive/ansi.c index e369fb2..196a0a3 100644 --- a/src/exhaustive/ansi.c +++ b/src/exhaustive/ansi.c @@ -11,7 +11,7 @@ #include "util/memory.h" #include "util/str.h" -static seed_t *ansi_new() { +static seed_t *ansi_new(void) { seed_t *result = seed_new(); result->type = SEED_ANSI; return result; diff --git a/src/exhaustive/brainpool.c b/src/exhaustive/brainpool.c index 56c095d..584ef5b 100644 --- a/src/exhaustive/brainpool.c +++ b/src/exhaustive/brainpool.c @@ -13,7 +13,7 @@ #include "util/bits.h" #include "util/str.h" -static seed_t *brainpool_new() { +static seed_t *brainpool_new(void) { seed_t *result = seed_new(); result->type = SEED_BRAINPOOL; return result; @@ -272,4 +272,4 @@ CHECK(brainpool_check_order) { } else { return -4; } -}
\ No newline at end of file +} diff --git a/src/exhaustive/check.c b/src/exhaustive/check.c index 5fa1c17..050b430 100644 --- a/src/exhaustive/check.c +++ b/src/exhaustive/check.c @@ -32,4 +32,4 @@ void check_free(check_t **check) { try_free(*check); *check = NULL; } -}
\ No newline at end of file +} diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c index e8870f8..7833740 100644 --- a/src/exhaustive/exhaustive.c +++ b/src/exhaustive/exhaustive.c @@ -7,9 +7,8 @@ #include "arg.h" #include "brainpool.h" #include "brainpool_rfc.h" -#include "nums.h" -#include "family.h" #include "check.h" +#include "family.h" #include "gen/curve.h" #include "gen/equation.h" #include "gen/field.h" @@ -21,6 +20,7 @@ #include "gen/seed.h" #include "io/output.h" #include "misc/config.h" +#include "nums.h" #include "obj/curve.h" #include "util/memory.h" #include "util/timeout.h" @@ -129,7 +129,8 @@ static void exhaustive_ginit(gen_f *generators) { generators[OFFSET_SEED] = &gen_skip; generators[OFFSET_FIELD] = &nums_gen_field; generators[OFFSET_A] = &nums_gen_a; - generators[OFFSET_B] = &nums_gen_b; // TODO: Missing transformation from b -> -b. + generators[OFFSET_B] = + &nums_gen_b; // TODO: Missing transformation from b -> -b. generators[OFFSET_ORDER] = &nums_gen_order; generators[OFFSET_GENERATORS] = &nums_gen_gens; } break; @@ -144,7 +145,6 @@ static void exhaustive_ginit(gen_f *generators) { generators[OFFSET_SEED] = &family_gen_seed_random; } else { generators[OFFSET_SEED] = &family_gen_seed_input; - } generators[OFFSET_FIELD] = &family_gen_field; generators[OFFSET_A] = &gen_skip; @@ -154,7 +154,7 @@ static void exhaustive_ginit(gen_f *generators) { generators[OFFSET_B] = &family_gen_equation_iter; } - //TODO make the prime check optional, based on cfg->prime. + // TODO make the prime check optional, based on cfg->prime. generators[OFFSET_ORDER] = &family_gen_order; generators[OFFSET_GENERATORS] = &gens_gen_any; } else { @@ -487,7 +487,7 @@ int exhaustive_generate(exhaustive_t *setup) { return result; } -int exhaustive_do() { +int exhaustive_do(void) { debug_log_start("Starting Exhaustive method"); gen_f generators[OFFSET_END] = {NULL}; diff --git a/src/exhaustive/exhaustive.h b/src/exhaustive/exhaustive.h index 5abd03d..926836f 100644 --- a/src/exhaustive/exhaustive.h +++ b/src/exhaustive/exhaustive.h @@ -66,6 +66,6 @@ int exhaustive_generate(exhaustive_t *setup); * * @return */ -int exhaustive_do(); +int exhaustive_do(void); #endif // ECGEN_EXHAUSTIVE_EXHAUSTIVE_H diff --git a/src/exhaustive/family.c b/src/exhaustive/family.c index 08505b6..2dcc24c 100644 --- a/src/exhaustive/family.c +++ b/src/exhaustive/family.c @@ -6,10 +6,10 @@ #include "family.h" #include "cm/cm_any.h" #include "gen/seed.h" +#include "io/output.h" #include "misc/config.h" #include "util/bits.h" #include "util/random.h" -#include "io/output.h" #define FAMILIES (FAMILY_KSS40 + 1) @@ -20,7 +20,7 @@ static GEN tz_store[FAMILIES] = {0}; static GEN D_store[FAMILIES] = {0}; // clang-format off -void family_init() { +void family_init(void) { pari_sp ltop = avma; nz_store[FAMILY_BN] = gclone(closure_evalgen(compile_str("(z) -> z"))); pz_store[FAMILY_BN] = gclone(closure_evalgen(compile_str("(z) -> 36*z^4 + 36*z^3 + 24*z^2 + 6*z + 1"))); @@ -68,7 +68,7 @@ void family_init() { } // clang-format on -static seed_t *family_new_seed() { +static seed_t *family_new_seed(void) { seed_t *result = seed_new(); result->type = SEED_FAMILY; return result; @@ -143,7 +143,9 @@ GENERATOR(family_gen_equation_cm) { GEN n = closure_callgen1(nz_store[cfg->family], curve->seed->family.z); GEN rz = closure_callgen1(rz_store[cfg->family], n); GEN D = D_store[cfg->family]; - GEN e = cm_construct_curve_subgroup(rz, D, curve->field); + cm_any_roots_t *roots = cm_make_roots(D, curve->field); + GEN e = cm_construct_curve_subgroup(rz, D, curve->field, roots); + cm_free_roots(roots); if (e) { curve->a = ell_get_a4(e); curve->b = ell_get_a6(e); @@ -171,7 +173,7 @@ GENERATOR(family_gen_order) { } } -void family_quit() { +void family_quit(void) { for (int i = 0; i < FAMILIES; i++) { if (nz_store[i]) { gunclone(nz_store[i]); @@ -192,4 +194,4 @@ void family_quit() { if (b) { gunclone(b); } -}
\ No newline at end of file +} diff --git a/src/exhaustive/family.h b/src/exhaustive/family.h index 9b7deaa..5b398dc 100644 --- a/src/exhaustive/family.h +++ b/src/exhaustive/family.h @@ -22,9 +22,8 @@ GENERATOR(family_gen_equation_cm); GENERATOR(family_gen_order); -void family_init(); +void family_init(void); -void family_quit(); +void family_quit(void); - -#endif //ECGEN_EXHAUSTIVE_FAMILY_H +#endif // ECGEN_EXHAUSTIVE_FAMILY_H diff --git a/src/exhaustive/nums.c b/src/exhaustive/nums.c index 7e41938..1d3ae2a 100644 --- a/src/exhaustive/nums.c +++ b/src/exhaustive/nums.c @@ -22,7 +22,7 @@ GENERATOR(nums_gen_field) { } GENERATOR(nums_gen_a) { - curve-> a = gmodulo(stoi(-3), curve->field); + curve->a = gmodulo(stoi(-3), curve->field); return 1; } @@ -103,9 +103,8 @@ GENERATOR(nums_gen_gens) { return 1; } - void nums_quit(void) { if (b && isclone(b)) { gunclone(b); } -}
\ No newline at end of file +} diff --git a/src/exhaustive/nums.h b/src/exhaustive/nums.h index 40cb1b4..142f96a 100644 --- a/src/exhaustive/nums.h +++ b/src/exhaustive/nums.h @@ -55,6 +55,6 @@ GENERATOR(nums_gen_order); */ GENERATOR(nums_gen_gens); -void nums_quit(); +void nums_quit(void); #endif // ECGEN_EXHAUSTIVE_NUMS_H diff --git a/src/gen/gens.c b/src/gen/gens.c index a743e79..329149a 100644 --- a/src/gen/gens.c +++ b/src/gen/gens.c @@ -5,9 +5,9 @@ #include "gens.h" #include "exhaustive/arg.h" #include "math/subgroup.h" +#include "misc/compat.h" #include "obj/point.h" #include "obj/subgroup.h" -#include "misc/compat.h" static subgroup_t *gens_point(GEN point, const curve_t *curve) { subgroup_t *sub = subgroup_new(); @@ -37,13 +37,20 @@ GENERATOR(gens_gen_any) { GENERATOR(gens_gen_one) { pari_sp ltop = avma; + GEN group = ellff_get_group(curve->curve); + debug_log("Group structure %Ps.", group); + long len = glength(group); + if (len == 2) { + avma = ltop; + return -5; + } GEN generators = ellff_get_gens(curve->curve); - long len = glength(generators); + len = glength(generators); if (len == 2) { avma = ltop; return -5; } - return gens_put(curve, generators, len); + return gens_put(curve, gerepilecopy(ltop, generators), len); } GENERATOR(gens_gen_cofactor) { diff --git a/src/gen/hex.c b/src/gen/hex.c index 58250a0..559e86c 100644 --- a/src/gen/hex.c +++ b/src/gen/hex.c @@ -121,4 +121,4 @@ CHECK(hex_check_param) { } try_free(search_hex); return result; -}
\ No newline at end of file +} diff --git a/src/gen/metadata.c b/src/gen/metadata.c index b857ec7..7d455ef 100644 --- a/src/gen/metadata.c +++ b/src/gen/metadata.c @@ -28,7 +28,8 @@ GENERATOR(metadata_gen) { GEN d_f = coredisc2(subii(sqri(frobenius), mulis(q, 4))); cm_disc = gcopy(gel(d_f, 1)); conductor = gcopy(gel(d_f, 2)); - gerepileall(ltop, 6, &j, &disc, &embedding_degree, &frobenius, &cm_disc, &conductor); + gerepileall(ltop, 6, &j, &disc, &embedding_degree, &frobenius, &cm_disc, + &conductor); } else if (typ(curve->field) == t_FFELT) { cm_disc = NULL; conductor = NULL; diff --git a/src/gen/order.c b/src/gen/order.c index a9d22b2..64ef665 100644 --- a/src/gen/order.c +++ b/src/gen/order.c @@ -158,4 +158,4 @@ CHECK(order_check_discriminant) { } avma = ltop; return 1; -}
\ No newline at end of file +} diff --git a/src/invalid/invalid.c b/src/invalid/invalid.c index 3679c6b..6742148 100644 --- a/src/invalid/invalid.c +++ b/src/invalid/invalid.c @@ -289,8 +289,7 @@ static size_t invalid_curves_threaded(const curve_t *curve, pari_ulong *primes, } } - if (*generated == nprimes) - break; + if (*generated == nprimes) break; } pthread_mutex_unlock(&state_mutex); @@ -328,7 +327,7 @@ curve_t *invalid_original_curve(exhaustive_t *setup) { return curve; } -int invalid_do() { +int invalid_do(void) { debug_log_start("Starting Invalid curve method"); gen_f original_gens[OFFSET_END] = {NULL}; diff --git a/src/invalid/invalid.h b/src/invalid/invalid.h index 15d6441..41bea15 100644 --- a/src/invalid/invalid.h +++ b/src/invalid/invalid.h @@ -14,6 +14,6 @@ * * @return */ -int invalid_do(); +int invalid_do(void); #endif // ECGEN_INVALID_INVALID_H diff --git a/src/io/cli.c b/src/io/cli.c index d98a0c0..65524c9 100644 --- a/src/io/cli.c +++ b/src/io/cli.c @@ -88,7 +88,7 @@ struct argp_option cli_options[] = { {0, 0, 0, 0, "Other:", 5}, {"data-dir", OPT_DATADIR, "DIR", 0, "Set PARI/GP data directory (containing seadata package).", 5}, {"memory", OPT_MEMORY, "SIZE", 0, "Use PARI stack of SIZE (can have suffix k/m/g).", 5}, - {"threads", OPT_THREADS, "NUM", 0, "Use NUM threads.", 5}, + {"threads", OPT_THREADS, "NUM", 0, "Use NUM threads (in PARI or invalid generation).", 5}, {"thread-stack", OPT_TSTACK, "SIZE", 0, "Use PARI stack of SIZE (per thread, can have suffix k/m/g).", 5}, {"timeout", OPT_TIMEOUT, "TIME", 0, "Timeout computation of a curve parameter after TIME (can have suffix s/m/h/d).", 5}, {0} @@ -97,7 +97,7 @@ struct argp_option cli_options[] = { static regex_t re_cm_order; -bool cli_init() { +bool cli_init(void) { int error = regcomp( &re_cm_order, "((0[xX][0-9a-fA-F]+)|([0-9]+))(,((0[xX][0-9a-fA-F]+)|([0-9]+)))*", @@ -540,4 +540,4 @@ char *cli_filter(int key, const char *text, void *input) { return (char *)text; } -void cli_quit() { regfree(&re_cm_order); } +void cli_quit(void) { regfree(&re_cm_order); } diff --git a/src/io/cli.h b/src/io/cli.h index abeb6e6..a712c44 100644 --- a/src/io/cli.h +++ b/src/io/cli.h @@ -19,7 +19,7 @@ extern struct argp_option cli_options[]; /** * @brief */ -bool cli_init(); +bool cli_init(void); /** * @brief @@ -42,6 +42,6 @@ char *cli_filter(int key, const char *text, void *input); /** * */ -void cli_quit(); +void cli_quit(void); #endif // ECGEN_IO_CLI_H diff --git a/src/io/input.c b/src/io/input.c index 507bd59..4c23c28 100644 --- a/src/io/input.c +++ b/src/io/input.c @@ -93,7 +93,7 @@ GEN input_string(const char *prompt) { return result; } -bool input_init() { +bool input_init(void) { if (cfg->input) { in = fopen(cfg->input, "r"); delim = ','; diff --git a/src/io/input.h b/src/io/input.h index a56347a..c1ac88e 100644 --- a/src/io/input.h +++ b/src/io/input.h @@ -50,7 +50,7 @@ extern FILE *in; * @brief Initialize input based on cfg. * @return whether the initialization was successful */ -bool input_init(); +bool input_init(void); /** * @brief Deinitialize input. diff --git a/src/io/output.c b/src/io/output.c index c4704c1..a625446 100644 --- a/src/io/output.c +++ b/src/io/output.c @@ -10,9 +10,9 @@ #include "util/memory.h" char *(*output_s)(curve_t *curve); -char *(*output_s_separator)(); -char *(*output_s_begin)(); -char *(*output_s_end)(); +char *(*output_s_separator)(void); +char *(*output_s_begin)(void); +char *(*output_s_end)(void); FILE *out; FILE *err; @@ -165,8 +165,7 @@ static JSON_Value *output_jjson(curve_t *curve) { } if (curve->meta.conductor != NULL) { char *conductor = pari_sprintf("%Pi", curve->meta.conductor); - json_object_dotset_string(root_object, "meta.conductor", - conductor); + json_object_dotset_string(root_object, "meta.conductor", conductor); pari_free(conductor); } } @@ -183,11 +182,11 @@ char *output_sjson(curve_t *curve) { return result; } -char *output_sjson_separator() { return output_malloc(",\n"); } +char *output_sjson_separator(void) { return output_malloc(",\n"); } -char *output_sjson_begin() { return output_malloc("[\n"); } +char *output_sjson_begin(void) { return output_malloc("[\n"); } -char *output_sjson_end() { return output_malloc("]\n"); } +char *output_sjson_end(void) { return output_malloc("]\n"); } void output_f(FILE *output, curve_t *curve) { char *s = output_s(curve); @@ -207,7 +206,7 @@ void output_f_separator(FILE *output) { } } -void output_o_separator() { output_f_separator(out); } +void output_o_separator(void) { output_f_separator(out); } void output_f_begin(FILE *output) { char *s = output_s_begin(); @@ -217,7 +216,7 @@ void output_f_begin(FILE *output) { } } -void output_o_begin() { output_f_begin(out); } +void output_o_begin(void) { output_f_begin(out); } void output_f_end(FILE *output) { char *s = output_s_end(); @@ -227,9 +226,9 @@ void output_f_end(FILE *output) { } } -void output_o_end() { output_f_end(out); } +void output_o_end(void) { output_f_end(out); } -bool output_init() { +bool output_init(void) { json_set_allocation_functions(try_malloc, try_free); if (cfg->output) { diff --git a/src/io/output.h b/src/io/output.h index f68acfc..477def4 100644 --- a/src/io/output.h +++ b/src/io/output.h @@ -89,21 +89,21 @@ char *output_sjson(curve_t *curve); * format. * @return */ -char *output_sjson_separator(); +char *output_sjson_separator(void); /** * @brief Output JSON output header(a "[") to a malloc'ed string in CSV * format. * @return */ -char *output_sjson_begin(); +char *output_sjson_begin(void); /** * @brief Output JSON output footer(a "]") to a malloc'ed string in CSV * format. * @return */ -char *output_sjson_end(); +char *output_sjson_end(void); /** * @brief Output curve to a malloc'ed string in configured format. @@ -129,7 +129,7 @@ void output_o(curve_t *curve); * @brief Output separator to a malloc'ed string in configured format. * @return */ -extern char *(*output_s_separator)(); +extern char *(*output_s_separator)(void); /** * @brief Output separator to a FILE *out in configured format. @@ -140,13 +140,13 @@ void output_f_separator(FILE *out); /** * @brief Output separator to configured output in configured format. */ -void output_o_separator(); +void output_o_separator(void); /** * @brief Output header to a malloc'ed string in configured format. * @return */ -extern char *(*output_s_begin)(); +extern char *(*output_s_begin)(void); /** * @brief Output header to a FILE *out in configured format. @@ -157,13 +157,13 @@ void output_f_begin(FILE *out); /** * @brief Output header to configured output in configured format. */ -void output_o_begin(); +void output_o_begin(void); /** * @brief Output footer to a malloc'ed string in configured format. * @return */ -extern char *(*output_s_end)(); +extern char *(*output_s_end)(void); /** * @brief Output footer to a FILE *out in configured format. @@ -174,7 +174,7 @@ void output_f_end(FILE *out); /** * @brief Output header to configured output in configured format. */ -void output_o_end(); +void output_o_end(void); /** * @brief Configured output FILE*. @@ -195,7 +195,7 @@ extern FILE *verbose; * @brief Initialize output based on cfg. * @return whether the initialization was successful */ -bool output_init(); +bool output_init(void); /** * @brief Deinitialize output. diff --git a/src/math/koblitz.c b/src/math/koblitz.c index ca91160..903b4f7 100644 --- a/src/math/koblitz.c +++ b/src/math/koblitz.c @@ -70,4 +70,4 @@ GEN koblitz_get_order(unsigned long m, unsigned long a) { } else { return NULL; } -}
\ No newline at end of file +} diff --git a/src/math/subgroup.c b/src/math/subgroup.c index fdf45a5..cdf7acb 100644 --- a/src/math/subgroup.c +++ b/src/math/subgroup.c @@ -3,6 +3,7 @@ * Copyright (C) 2017-2018 J08nY */ #include "subgroup.h" +#include "io/output.h" /** * @brief All prime divisors of a given integer with multiplicity. @@ -46,6 +47,11 @@ static GEN subgroups_2n_factors(GEN factors, size_t min_bits) { long nprimes = glength(factors); if (nprimes == min_bits) return NULL; GEN amount = int2n(nprimes); + long abits = logint(amount, gen_2); + if (abits >= 64) { + fprintf(err, "Too many factors to generate points (%li bits).", abits); + return NULL; + } GEN groups = gtovec0(gen_0, itos(amount) - (min_bits * nprimes) - 1); size_t i = 0; @@ -140,4 +146,4 @@ static GEN subgroups_2n(const curve_t *curve, size_t min_bits) { return subgroups_2n_gens(curve, min_bits); } -*/
\ No newline at end of file +*/ diff --git a/src/math/twists.c b/src/math/twists.c index 0d4b14c..a4ae2b9 100644 --- a/src/math/twists.c +++ b/src/math/twists.c @@ -33,4 +33,4 @@ void twist_rand(curve_t *what) { twist_rand_to(what, what); seed_free(&what->seed); subgroups_free_deep(&what->generators, what->ngens); -}
\ No newline at end of file +} diff --git a/src/misc/compat.h b/src/misc/compat.h index 7e3d4e8..ccacb2e 100644 --- a/src/misc/compat.h +++ b/src/misc/compat.h @@ -12,17 +12,24 @@ #define PARI_VERSION_MINOR (((PARI_VERSION_CODE) >> 8) & 0xff) #define PARI_VERSION_MAJOR (PARI_VERSION_CODE >> 16) -#define PARI_VERSION_GT(a,b,c) ((PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR == b && PARI_VERSION_PATCH > c) || (PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR > b) || (PARI_VERSION_MAJOR > a)) -#define PARI_VERSION_EQ(a,b,c) (PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR == b && PARI_VERSION_PATCH == c) -#define PARI_VERSION_GE(a,b,c) (PARI_VERSION_GT(a,b,c) || PARI_VERSION_EQ(a,b,c)) -#define PARI_VERSION_LT(a,b,c) !(PARI_VERSION_GE(a,b,c)) -#define PARI_VERSION_LE(a,b,c) !(PARI_VERSION_GT(a,b,c)) +#define PARI_VERSION_GT(a, b, c) \ + ((PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR == b && \ + PARI_VERSION_PATCH > c) || \ + (PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR > b) || \ + (PARI_VERSION_MAJOR > a)) +#define PARI_VERSION_EQ(a, b, c) \ + (PARI_VERSION_MAJOR == a && PARI_VERSION_MINOR == b && \ + PARI_VERSION_PATCH == c) +#define PARI_VERSION_GE(a, b, c) \ + (PARI_VERSION_GT(a, b, c) || PARI_VERSION_EQ(a, b, c)) +#define PARI_VERSION_LT(a, b, c) !(PARI_VERSION_GE(a, b, c)) +#define PARI_VERSION_LE(a, b, c) !(PARI_VERSION_GT(a, b, c)) -#if PARI_VERSION_LT(2,12,1) +#if PARI_VERSION_LT(2, 12, 1) #define polisirreducible isirreducible #endif -#if PARI_VERSION_LT(2,15,0) +#if PARI_VERSION_LT(2, 15, 0) #define znorder(x, o) order(x); #endif diff --git a/src/misc/config.c b/src/misc/config.c index 155cbb4..9f66b51 100644 --- a/src/misc/config.c +++ b/src/misc/config.c @@ -15,7 +15,7 @@ config_names_t *cfg_used = &cfg_used_s; config_names_t cfg_set_s = {0}; config_names_t *cfg_set = &cfg_set_s; -void config_report_unused() { +void config_report_unused(void) { bool unused = false; if (cfg_set->field && !cfg_used->field) { fprintf( @@ -120,4 +120,4 @@ void config_report_unused() { #else (void)unused; #endif -}
\ No newline at end of file +} diff --git a/src/misc/config.h b/src/misc/config.h index 3272190..b4fbc79 100644 --- a/src/misc/config.h +++ b/src/misc/config.h @@ -129,7 +129,7 @@ typedef struct { char *datadir; /** @brief How much memory to allocate for the PARI stack. */ unsigned long memory; - /** @brief How many threads to use, only useful for invalid generation(atm). + /** @brief How many threads to use (or limit PARI to use). */ unsigned long threads; /** @brief How much memory to allocate for the PARI stack, per thread. */ @@ -191,6 +191,6 @@ extern config_names_t *cfg_set; #define GET_BOOL(x) ((cfg_used->x = true) && cfg->x) #define SET(x) cfg_set->x = true -void config_report_unused(); +void config_report_unused(void); #endif // ECGEN_MISC_CONFIG_H diff --git a/src/obj/curve.c b/src/obj/curve.c index 4821442..10b720e 100644 --- a/src/obj/curve.c +++ b/src/obj/curve.c @@ -62,4 +62,4 @@ void curve_free(curve_t **curve) { try_free(*curve); *curve = NULL; } -}
\ No newline at end of file +} diff --git a/src/obj/obj.h b/src/obj/obj.h index 5a7f9ab..86a8d1d 100644 --- a/src/obj/obj.h +++ b/src/obj/obj.h @@ -5,15 +5,15 @@ #include "misc/types.h" #include "util/memory.h" -#define OBJ(obj_name, obj_type, copy_func, clone_func) \ - obj_type *obj_name##_new() { return try_calloc(sizeof(obj_type)); } \ - obj_type *obj_name##_new_copy(const obj_type *src) { \ - obj_type *result = obj_name##_new(); \ - return copy_func(src, result); \ - } \ - obj_type *obj_name##_new_clone(const obj_type *src) { \ - obj_type *result = obj_name##_new(); \ - return clone_func(src, result); \ +#define OBJ(obj_name, obj_type, copy_func, clone_func) \ + obj_type *obj_name##_new(void) { return try_calloc(sizeof(obj_type)); } \ + obj_type *obj_name##_new_copy(const obj_type *src) { \ + obj_type *result = obj_name##_new(); \ + return copy_func(src, result); \ + } \ + obj_type *obj_name##_new_clone(const obj_type *src) { \ + obj_type *result = obj_name##_new(); \ + return clone_func(src, result); \ } #define OBJS(obj_name, obj_type, copy_func, clone_func) \ @@ -44,7 +44,7 @@ } #define OBJ_H(obj_name, obj_type) \ - obj_type *obj_name##_new(); \ + obj_type *obj_name##_new(void); \ obj_type *obj_name##_new_copy(const obj_type *src); \ obj_type *obj_name##_new_clone(const obj_type *src); diff --git a/src/obj/point.c b/src/obj/point.c index 2b709dd..4722bad 100644 --- a/src/obj/point.c +++ b/src/obj/point.c @@ -48,4 +48,4 @@ void points_free_deep(point_t ***points, unsigned long npoints) { } points_free(points); } -}
\ No newline at end of file +} diff --git a/src/util/bits.c b/src/util/bits.c index 0d60c26..b73a55d 100644 --- a/src/util/bits.c +++ b/src/util/bits.c @@ -174,16 +174,18 @@ char *bits_to_hex(const bits_t *bits) { // else // 0 0 | a b | c d | e // ^-----^ (8-offset zero bits, offset bits from first byte) - // ^-----^ (8-offset bits from first byte, offset bits from second byte) + // ^-----^ (8-offset bits from first byte, offset bits from second + // byte) // .... - // ^-----^ (8-offset bits from second to last byte, offset bits from last byte) + // ^-----^ (8-offset bits from second to last byte, offset bits + // from last byte) for (size_t i = 0; i < BYTE_LEN(bits->bitlen); ++i) { size_t pos = (i * 2) + (bits->sign ? 1 : 0); unsigned char value; if (offset) { value = bits->bits[i] >> (8 - offset); if (i != 0) { - value |= (bits->bits[i-1] & ~(1 << (8 - offset))) << offset; + value |= (bits->bits[i - 1] & ~(1 << (8 - offset))) << offset; } } else { value = bits->bits[i]; diff --git a/src/util/memory.c b/src/util/memory.c index f05efae..b84a4c4 100644 --- a/src/util/memory.c +++ b/src/util/memory.c @@ -72,4 +72,4 @@ void set_mem_funcs(void *(*malloc_fun)(size_t), void *(*calloc_fun)(size_t), calloc_func = calloc_fun; realloc_func = realloc_fun; free_func = free_fun; -}
\ No newline at end of file +} diff --git a/src/util/random.c b/src/util/random.c index b88bb50..844e0f6 100644 --- a/src/util/random.c +++ b/src/util/random.c @@ -5,8 +5,8 @@ #define _POSIX_C_SOURCE 200809L #include "random.h" -#include <time.h> #include <stdint.h> +#include <time.h> void random_reseed(void) { pari_ulong seed = 0; @@ -15,7 +15,8 @@ void random_reseed(void) { if (rand) { size_t read = 0; while (read < sizeof(pari_ulong)) { - read += fread(((uint8_t*) &seed) + read, 1, sizeof(pari_ulong) - read, rand); + read += fread(((uint8_t *)&seed) + read, 1, + sizeof(pari_ulong) - read, rand); } fclose(rand); diff --git a/src/util/str.c b/src/util/str.c index ff075f2..ade97a9 100644 --- a/src/util/str.c +++ b/src/util/str.c @@ -68,7 +68,6 @@ char *str_concat(char **strings, size_t len) { size_t str_cnt(const char *str, const char c) { size_t result = 0; - for (; str[result]; str[result] == c ? result++ : *str++) - ; + for (; str[result]; str[result] == c ? result++ : *str++); return result; } diff --git a/src/util/timeout.c b/src/util/timeout.c index 6fdbf16..5cfa552 100644 --- a/src/util/timeout.c +++ b/src/util/timeout.c @@ -19,17 +19,17 @@ void timeout_handle(int signum, siginfo_t *siginfo, void *other) { if (timeout_in) siglongjmp(timeout_ptr, 1); } -void timeout_thread_init() { +void timeout_thread_init(void) { timeout_timer = try_calloc(sizeof(timer_t)); sevp = try_calloc(sizeof(struct sigevent)); } -void timeout_thread_quit() { +void timeout_thread_quit(void) { try_free(timeout_timer); try_free(sevp); } -bool timeout_init() { +bool timeout_init(void) { // init for the main thread. timeout_thread_init(); struct sigaction new_action; @@ -42,7 +42,7 @@ bool timeout_init() { return true; } -void timeout_quit() { +void timeout_quit(void) { // deinit the main thread. timeout_thread_quit(); } diff --git a/src/util/timeout.h b/src/util/timeout.h index 57e3d22..6f6805b 100644 --- a/src/util/timeout.h +++ b/src/util/timeout.h @@ -69,19 +69,19 @@ extern __thread struct sigevent *sevp; } \ } -void timeout_thread_init(); +void timeout_thread_init(void); -void timeout_thread_quit(); +void timeout_thread_quit(void); /** * @brief Initialize the timeout system. * @return whether the initalization was successful */ -bool timeout_init(); +bool timeout_init(void); /** * @brief Deinitialize the timeout system. */ -void timeout_quit(); +void timeout_quit(void); #endif // ECGEN_UTIL_TIMEOUT_H diff --git a/test/common.sh b/test/common.sh index 42978a3..7d1ea22 100644 --- a/test/common.sh +++ b/test/common.sh @@ -7,7 +7,6 @@ #### ecgen="../ecgen" -econvert="../econvert" ASSERT="lib/assert.sh/assert.sh" JSON="lib/JSON.sh/JSON.sh" @@ -41,3 +40,10 @@ canonical_num() { num=$(strip_num "$1") echo "ibase=16;${num^^}" | bc } + +get_pari_order() { + p=$(canonical_num $(echo $1 | ${JSON} -x field\",\"p | cut -f 2)) + a=$(canonical_num $(echo $1 | ${JSON} -x \"a | cut -f 2)) + b=$(canonical_num $(echo $1 | ${JSON} -x \"b | cut -f 2)) + echo "ellcard(ellinit([${a}, ${b}], ${p}))" | gp -f -q | tr -cd [:digit:] 2>/dev/null +}
\ No newline at end of file diff --git a/test/ecgen.sh b/test/ecgen.sh index 38670bc..96dacb3 100755 --- a/test/ecgen.sh +++ b/test/ecgen.sh @@ -101,20 +101,24 @@ function nums() { function anomalous() { start_test assert_raises "${ecgen} --fp --anomalous -r 20" - out=$(${ecgen} --fp --anomalous -r 20 2>/dev/null) - p=$(echo $out | ${JSON} -x field\",\"p | cut -f 2) - order=$(echo $out | ${JSON} -x ^0,\"order\" | cut -f 2) - assert "strip_num $p" $(strip_num $order) + for i in $(seq 10); do + out=$(${ecgen} --fp --anomalous -r 20 2>/dev/null) + p=$(echo $out | ${JSON} -x field\",\"p | cut -f 2) + order=$(echo $out | ${JSON} -x ^0,\"order\" | cut -f 2) + assert "strip_num $p" $(strip_num $order) + done } function supersingular() { start_test assert_raises "${ecgen} --fp --supersingular -r -c 5 20" - out=$(${ecgen} --fp --supersingular -r 20 2>/dev/null) - p=$(echo $out | ${JSON} -x field\",\"p | cut -f 2) - order=$(echo $out | ${JSON} -x ^0,\"order\" | cut -f 2) - order_m1=$(echo $(canonical_num $order) - 1 | bc) - assert "canonical_num $p" $order_m1 + for i in $(seq 10); do + out=$(${ecgen} --fp --supersingular -r 20 2>/dev/null) + p=$(echo $out | ${JSON} -x field\",\"p | cut -f 2) + order=$(echo $out | ${JSON} -x ^0,\"order\" | cut -f 2) + order_m1=$(echo $(canonical_num $order) - 1 | bc) + assert "canonical_num $p" $order_m1 + done assert_raises "${ecgen} --fp --supersingular --input=data/prime.in 64" @@ -187,12 +191,42 @@ function hex() { function cm() { start_test assert_raises "${ecgen} --fp --order=2147483723 32" - assert_raises "${ecgen} --fp --order=123456789012345678901234567890123456789012345678901234568197 196" + assert_raises "${ecgen} --fp --order=123456789012345678901234567890123456789012345678901234568197 --threads=5 196" assert_raises "${ecgen} --fp --order=46874566546,3546,3125 64" + assert_raises "${ecgen} --fp -u --order=46874566546,3546,3125 64" assert_raises "${ecgen} --fp --order=0 16" 1 assert_raises "${ecgen} --fp --order=0x1000 8" 1 } +function cm_orders() { + start_test + for i in $(seq 5 100); do + out=$(timeout -k 4 3 ${ecgen} --fp -n $i --points=none 6 2>/dev/null) + if [[ -z "$out" || "$out" = "[" ]]; then + continue + fi + order=$(echo $out | ${JSON} -x ^0,\"order\" | cut -f 2) + pari_order=$(get_pari_order "$out") + assert "canonical_num $order" "$pari_order" + done + + prime_orders=(45678945611413 47889465415131 78246132456157 3879641663983 134537095890397 3790687732807) + for ord in "${prime_orders[@]}"; do + out=$(${ecgen} --fp -r --order=$ord 64 2>/dev/null) + p=$(echo $out | ${JSON} -x field\",\"p | cut -f 2) + order=$(echo $out | ${JSON} -x ^0,\"order\" | cut -f 2) + assert "canonical_num $order" $ord + done + + composite_orders=(106618070007935 32268705670290 78286235471710 93953327960423 17042092126557 43615536370894) + for ord in "${composite_orders[@]}"; do + out=$(${ecgen} --fp -r --order=$ord 64 2>/dev/null) + p=$(echo $out | ${JSON} -x field\",\"p | cut -f 2) + order=$(echo $out | ${JSON} -x ^0,\"order\" | cut -f 2) + assert "canonical_num $order" $ord + done +} + function secg() { function test_order() { name="${1}" @@ -235,5 +269,6 @@ twist cli hex cm +cm_orders secg end_suite ecgen diff --git a/test/src/util/test_bits.c b/test/src/util/test_bits.c index 269d1f6..e5a2f73 100644 --- a/test/src/util/test_bits.c +++ b/test/src/util/test_bits.c @@ -243,14 +243,14 @@ Test(bits, test_bits_or) { bits_t *other_bits = bits_new(6); other_bits->bits[0] = 0b10000000; - bits_t * or = bits_or(bits, other_bits); + bits_t *or = bits_or(bits, other_bits); cr_assert_not_null(or, ); cr_assert_eq(or->bitlen, 10, ); cr_assert_eq(or->bits[0], 0b00001000, ); cr_assert_eq(or->bits[1], 0b11000000, ); bits_free(&bits); bits_free(&other_bits); - bits_free(& or); + bits_free(&or); } Test(bits, test_bits_and) { |