commit 6b0e23ea580b02f04e6fd7a7de40a9fcb49f7d0a
parent 59fb30b24cf6820587882a348ee993fc4d244180
Author: olikru <olikru@tkruger.se>
Date: Thu, 7 Mar 2024 18:20:54 +0100
weiner
Diffstat:
6 files changed, 190 insertions(+), 5 deletions(-)
diff --git a/Makefile b/Makefile
@@ -21,12 +21,14 @@ smallfactor.o\
hnp.o\
cyclefind.o\
pierre.o\
-fmpzio.o
+fmpzio.o\
+wiener.o
TOOLS=\
hnpsolve\
lcgfloyd\
dbcreate\
-pierre
+pierre\
+varmkorv
PRECOMPUTERS=\
primorial16bit
SHARED=angrepp.so
@@ -64,6 +66,9 @@ lcgfloyd: build $(OBJS)
pierre: build $(OBJS)
$(CC) -I. $(CFLAGS) -o $(BUILD)/tools/pierre $(TOOLS_DIR)/pierre.c $(BUILD_OBJS) $(LDFLAGS)
+varmkorv: build $(OBJS)
+ $(CC) -I. $(CFLAGS) -o $(BUILD)/tools/varmkorv $(TOOLS_DIR)/varmkorv.c $(BUILD_OBJS) $(LDFLAGS)
+
dbcreate: build $(OBJS)
$(CC) -I. $(CFLAGS) -o $(BUILD)/tools/dbcreate $(TOOLS_DIR)/dbcreate.c $(BUILD_OBJS) $(LDFLAGS) -lsqlite3
diff --git a/examples/varmkorv.txt b/examples/varmkorv.txt
@@ -0,0 +1 @@
+32193226917433121 8403467516040173
diff --git a/tools/pierre.c b/tools/pierre.c
@@ -4,12 +4,10 @@
#include <stdlib.h>
#include "fmpzio.h"
-
#include "pierre.h"
#define DEFAULT_LIMIT 100000000
-
int
main()
{
@@ -17,7 +15,7 @@ main()
fmpz_init(factor);
fmpz_init(read);
- while(read_next_hex_fmpz(read) == 0) {
+ while (read_next_hex_fmpz(read) == 0) {
fermat_factor(factor, read, DEFAULT_LIMIT);
fmpz_print(factor);
printf("\n");
diff --git a/tools/varmkorv.c b/tools/varmkorv.c
@@ -0,0 +1,39 @@
+#include <fmpz.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "fmpzio.h"
+#include "wiener.h"
+
+int
+main()
+{
+ fmpz_t e, N, res;
+ fmpz_init(e);
+ fmpz_init(N);
+ fmpz_init(res);
+
+ while (1) {
+ if (read_next_fmpz(N) != 0) {
+ break;
+ }
+
+ if (read_next_fmpz(e) != 0) {
+ break;
+ }
+
+ if(wiener_factor_small_d(res, e, N)) {
+ fmpz_print(res);
+ printf("\n");
+ } else {
+ printf("0\n");
+ }
+ }
+
+ fmpz_clear(e);
+ fmpz_clear(N);
+ fmpz_clear(res);
+
+ return 0;
+}
diff --git a/wiener.c b/wiener.c
@@ -0,0 +1,130 @@
+#include "wiener.h"
+
+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;
+ fmpz_t phi, t, it, tmp;
+
+ if (fmpz_cmp_ui(k, 0) == 0) {
+ return 0;
+ }
+
+ fmpz_init(phi);
+ fmpz_init(t);
+ fmpz_init(it);
+ fmpz_init(tmp);
+
+ 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;
+ }
+ }
+ }
+
+ fmpz_clear(phi);
+ fmpz_clear(t);
+ fmpz_clear(it);
+ fmpz_clear(tmp);
+
+ return res;
+}
+
+int
+wiener_factor(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;
+ 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);
+
+ while (!fmpq_is_zero(xn[1])) {
+ fmpq_div(tmp, xn[0], xn[1]);
+ fmpz_fdiv_q(tmpz, fmpq_numref(tmp), fmpq_denref(tmp));
+
+ fmpq_mul_fmpz(xp, xn[1], tmpz);
+ fmpq_sub(xp, xn[0], xp);
+ fmpq_set(xn[0], xn[1]);
+ fmpq_set(xn[1], xp);
+
+ fmpz_mul(xpz, tmpz, q[1]);
+ fmpz_add(xpz, xpz, q[0]);
+ fmpz_set(q[0], q[1]);
+ fmpz_set(q[1], xpz);
+
+ fmpz_mul(xpz, tmpz, p[1]);
+ fmpz_add(xpz, xpz, p[0]);
+ fmpz_set(p[0], p[1]);
+ fmpz_set(p[1], xpz);
+
+ ret = test_kd(res, p[1], q[1], e, N);
+
+ 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)
+{
+ 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);
+
+ return ret;
+}
diff --git a/wiener.h b/wiener.h
@@ -0,0 +1,12 @@
+#ifndef _WIENER_H_
+#define _WIENER_H_
+
+#include <fmpq.h>
+#include <fmpz.h>
+
+int wiener_factor(fmpz_t res, const fmpq_t x, const fmpz_t e,
+ const fmpz_t N);
+
+int wiener_factor_small_d(fmpz_t res, const fmpz_t e, const fmpz_t N);
+
+#endif
