commit 91c42bb981e3febfccdc46a998cdf80260d6c473
parent 16a8af17350efd4f61cdd6d763f803c68ead9e9f
Author: olikru <olikru@tkruger.se>
Date: Fri, 12 Jul 2024 08:55:20 +0200
context for wiener
Diffstat:
5 files changed, 95 insertions(+), 37 deletions(-)
diff --git a/context.c b/context.c
@@ -20,11 +20,15 @@ ctx_require(ctx_t *ctx, const slong nzs, const slong nqs)
if (ctx->zs_alloc < nzs) {
ctx->zs = flint_realloc(ctx->zs, sizeof(*ctx->zs) * nzs);
memset(&(ctx->zs[ctx->zs_alloc]), 0, sizeof(*ctx->zs) * (nzs - ctx->zs_alloc));
+
+ ctx->zs_alloc = nzs;
}
if (ctx->qs_alloc < nqs) {
ctx->qs = flint_realloc(ctx->qs, sizeof(*ctx->qs) * nqs);
memset(&(ctx->qs[ctx->qs_alloc]), 0, sizeof(*ctx->qs) * (nqs - ctx->qs_alloc));
+
+ ctx->qs_alloc = nqs;
}
}
diff --git a/test_angrepp.c b/test_angrepp.c
@@ -11,6 +11,7 @@
#include "smallfactor.h"
#include "wiener.h"
#include "hnp.h"
+#include "context.h"
static uint64_t
test_f(uint64_t x)
@@ -64,15 +65,20 @@ static void
test_wiener_factor_small_d(void)
{
fmpz_t N, e, res;
+ ctx_t ctx;
int ret;
+
fmpz_init(N);
fmpz_init(e);
fmpz_init(res);
+ ctx_init(&ctx);
+ ctx_require(&ctx, 10, 5);
+
fmpz_set_str(N, "32193226917433121", 10);
fmpz_set_str(e, "8403467516040173", 10);
- ret = wiener_factor_small_d(res, e, N);
+ ret = wiener_factor_small_d(&ctx, res, e, N);
assert(ret == 1);
assert(fmpz_divisible(N, res));
@@ -81,6 +87,8 @@ test_wiener_factor_small_d(void)
fmpz_clear(N);
fmpz_clear(e);
fmpz_clear(res);
+
+ ctx_clear(&ctx);
}
static void
diff --git a/tools/varmkorv.c b/tools/varmkorv.c
@@ -5,15 +5,21 @@
#include "fmpzio.h"
#include "wiener.h"
+#include "context.h"
int
main(void)
{
fmpz_t e, N, res;
+ ctx_t ctx;
+
fmpz_init(e);
fmpz_init(N);
fmpz_init(res);
+ ctx_init(&ctx);
+ ctx_require(&ctx, 10, 5);
+
while (1) {
if (read_next_fmpz(N) != 0) {
break;
@@ -23,7 +29,7 @@ main(void)
break;
}
- if (wiener_factor_small_d(res, e, N)) {
+ if (wiener_factor_small_d(&ctx, res, e, N)) {
fmpz_print(res);
printf("\n");
} else {
@@ -35,5 +41,7 @@ main(void)
fmpz_clear(N);
fmpz_clear(res);
+ ctx_clear(&ctx);
+
return 0;
}
diff --git a/wiener.c b/wiener.c
@@ -2,6 +2,48 @@
static int
test_kd(fmpz_t r, const fmpz_t k, const fmpz_t d, const fmpz_t e,
+ const fmpz_t N, fmpz_t phi, fmpz_t t, fmpz_t it, fmpz_t tmp)
+{
+ int res = 0;
+
+ if (fmpz_cmp_ui(k, 0) == 0) {
+ return 0;
+ }
+
+ fmpz_mul(phi, e, d);
+ fmpz_sub_ui(phi, phi, 1);
+ fmpz_fdiv_q(phi, phi, k);
+
+ fmpz_add_ui(t, N, 1);
+ fmpz_sub(t, t, phi);
+ fmpz_pow_ui(t, t, 2);
+ fmpz_mul_ui(tmp, N, 4);
+ fmpz_sub(t, t, tmp);
+
+ if (fmpz_cmp_ui(t, 0) >= 0) {
+ fmpz_sqrt(it, t);
+ fmpz_pow_ui(tmp, it, 2);
+
+ if (fmpz_cmp(tmp, t) == 0) {
+ fmpz_add_ui(tmp, N, 1);
+ fmpz_sub(tmp, tmp, phi);
+ fmpz_add(tmp, tmp, it);
+ fmpz_fdiv_q_ui(r, tmp, 2);
+
+ fmpz_mod(tmp, N, r);
+
+ if (fmpz_is_zero(tmp)) {
+ res = 1;
+ }
+ }
+ }
+
+ return res;
+}
+
+/*
+static int
+test_kd(fmpz_t r, const fmpz_t k, const fmpz_t d, const fmpz_t e,
const fmpz_t N)
{
int res = 0;
@@ -51,28 +93,31 @@ test_kd(fmpz_t r, const fmpz_t k, const fmpz_t d, const fmpz_t e,
return res;
}
+*/
int
-wiener_factor(fmpz_t res, const fmpq_t x, const fmpz_t e,
+wiener_factor(ctx_t *ctx, fmpz_t res, const fmpq_t x, const fmpz_t e,
const fmpz_t N)
{
- fmpq_t xn[2], tmp, xp;
- fmpz_t p[2], q[2], tmpz, xpz;
+ assert(ctx->zs_alloc >= 10);
+ assert(ctx->qs_alloc >= 4);
+
+ fmpq_t xn[2] = {{ctx->qs[0]}, {ctx->qs[1]}};
+ fmpq_t tmp = {ctx->qs[2]};
+ fmpq_t xp = {ctx->qs[3]};
+ fmpz_t p[2] = {{ctx->zs[0]}, {ctx->zs[1]}};
+ fmpz_t q[2] = {{ctx->zs[2]}, {ctx->zs[3]}};
+ fmpz_t tmpz = {ctx->zs[4]};
+ fmpz_t xpz = {ctx->zs[5]};
int ret = 0;
- fmpq_init(xn[0]);
fmpq_set(xn[0], x);
- fmpq_init(xn[1]);
fmpq_one(xn[1]);
- fmpq_init(tmp);
- fmpq_init(xp);
- fmpz_init(tmpz);
- fmpz_init(xpz);
- fmpz_init_set_ui(p[0], 0);
- fmpz_init_set_ui(p[1], 1);
- fmpz_init_set_ui(q[0], 1);
- fmpz_init_set_ui(q[1], 0);
+ fmpz_set_ui(p[0], 0);
+ fmpz_set_ui(p[1], 1);
+ fmpz_set_ui(q[0], 1);
+ fmpz_set_ui(q[1], 0);
while (!fmpq_is_zero(xn[1])) {
fmpq_div(tmp, xn[0], xn[1]);
@@ -93,38 +138,25 @@ wiener_factor(fmpz_t res, const fmpq_t x, const fmpz_t e,
fmpz_set(p[0], p[1]);
fmpz_set(p[1], xpz);
- ret = test_kd(res, p[1], q[1], e, N);
+ ret = test_kd(res, p[1], q[1], e, N, &ctx->zs[6], &ctx->zs[7],
+ &ctx->zs[8], &ctx->zs[9]);
if (ret != 0)
break;
}
- fmpq_clear(xn[0]);
- fmpq_clear(xn[1]);
- fmpq_clear(tmp);
- fmpq_clear(xp);
-
- fmpz_clear(tmpz);
- fmpz_clear(xpz);
- fmpz_clear(p[0]);
- fmpz_clear(p[1]);
- fmpz_clear(q[0]);
- fmpz_clear(q[1]);
-
return ret;
}
int
-wiener_factor_small_d(fmpz_t res, const fmpz_t e, const fmpz_t N)
+wiener_factor_small_d(ctx_t* ctx, fmpz_t res, const fmpz_t e, const fmpz_t N)
{
+ assert(ctx->qs_alloc >= 5);
+ fmpq_t x = {ctx->qs[4]};
int ret;
- fmpq_t x;
- fmpq_init(x);
fmpq_set_fmpz_frac(x, e, N);
- ret = wiener_factor(res, x, e, N);
-
- fmpq_clear(x);
+ ret = wiener_factor(ctx, res, x, e, N);
return ret;
}
diff --git a/wiener.h b/wiener.h
@@ -3,6 +3,9 @@
#include <fmpq.h>
#include <fmpz.h>
+#include <assert.h>
+
+#include "context.h"
/**
* Wiener factorisation with general k/d approximation.
@@ -14,6 +17,7 @@
* d : the corresponding private exponent
* k : (e*d-1)/((p-1)*(q-1)).
*
+ * @param ctx context used for temporary variables
* @param res the result fmpz_t
* @param x approximation of k/d
* @param e public exponent
@@ -22,8 +26,8 @@
* 1 if a factor is found
* 0 otherwise
*/
-int wiener_factor(fmpz_t res, const fmpq_t x, const fmpz_t e,
- const fmpz_t N);
+int wiener_factor(ctx_t *ctx, fmpz_t res, const fmpq_t x,
+ const fmpz_t e, const fmpz_t N);
/**
* Wiener factorisation for small private exponent.
@@ -32,6 +36,7 @@ int wiener_factor(fmpz_t res, const fmpq_t x, const fmpz_t e,
* e/N is a "close enough" approximation of k/d. This "close enough"
* happens when d < (1/3) N^(1/4).
*
+ * @param ctx context used for temporary variables
* @param res the result fmpz_t
* @param e public exponent e
* @param N public RSA-modulus
@@ -39,6 +44,7 @@ int wiener_factor(fmpz_t res, const fmpq_t x, const fmpz_t e,
* 1 if a factor is found
* 0 otherwise
*/
-int wiener_factor_small_d(fmpz_t res, const fmpz_t e, const fmpz_t N);
+int wiener_factor_small_d(ctx_t *ctx, fmpz_t res, const fmpz_t e,
+ const fmpz_t N);
#endif
