cangrepp

commit a57758a0daaeadc9b665bb79fde015d3ff4cb814
parent e74118b42eedf51b6420cc85840e19db82a9b909
Author: olikru <olikru@tkruger.se>
Date:   Thu,  7 Mar 2024 12:11:56 +0100

added fermat factoris

Diffstat:
M
Makefile
 | 
9
+++++++--
A
pierre.c
 | 
37
+++++++++++++++++++++++++++++++++++++
A
pierre.h
 | 
6
++++++
M
tools/dbcreate.c
 | 
2
+-
A
tools/pierre.c
 | 
28
++++++++++++++++++++++++++++

5 files changed, 79 insertions(+), 3 deletions(-)
diff --git a/Makefile b/Makefile
@@ -19,11 +19,13 @@ HEADERS=smallfactor.h
 OBJS=\
 smallfactor.o\
 hnp.o\
-cyclefind.o
+cyclefind.o\
+pierre.o
 TOOLS=\
 hnpsolve\
 lcgfloyd\
-dbcreate
+dbcreate\
+pierre
 PRECOMPUTERS=\
 primorial16bit
 SHARED=angrepp.so
@@ -58,6 +60,9 @@ hnpsolve: build $(OBJS)
 lcgfloyd: build $(OBJS)
 	$(CC) -I. $(CFLAGS) -o $(BUILD)/tools/lcgfloyd $(TOOLS_DIR)/lcgfloyd.c $(BUILD_OBJS) $(LDFLAGS)
 
+pierre: build $(OBJS)
+	$(CC) -I. $(CFLAGS) -o $(BUILD)/tools/pierre $(TOOLS_DIR)/pierre.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/pierre.c b/pierre.c
@@ -0,0 +1,37 @@
+#include <fmpz.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "pierre.h"
+
+void
+fermat_factor(fmpz_t r, fmpz_t n, size_t limit)
+{
+  size_t i;
+  uint64_t inc = 1;
+  int found = 0;
+  fmpz_set(r, n);
+
+  for (i = 0; i < limit; i++) {
+    if (fmpz_is_square(r)) {
+      found = 1;
+      break;
+    }
+
+    fmpz_add_ui(r, r, inc);
+    inc += 2;
+  }
+
+  if (found) {
+    fmpz_t tmp;
+    fmpz_init_set(tmp, n);
+    fmpz_sub(tmp, r, n); // tmp = b^2
+    fmpz_sqrt(tmp, tmp); // tmp = b
+    fmpz_sqrt(r, r);     // r = a
+    fmpz_add(r, r, tmp);
+    fmpz_clear(tmp);
+  } else {
+    fmpz_set_ui(r, 0);
+  }
+}
diff --git a/pierre.h b/pierre.h
@@ -0,0 +1,6 @@
+#ifndef _PIERRE_H_
+#define _PIERRE_H_
+
+void fermat_factor(fmpz_t r, fmpz_t n, size_t limit);
+
+#endif
diff --git a/tools/dbcreate.c b/tools/dbcreate.c
@@ -13,7 +13,7 @@ usage(char *c)
 {
   printf("Usage: %s <db>\n"
          "  where\n"
-         "<db>   path to database to create\n", );
+         "<db>   path to database to create\n");
   exit(1);
 }
 
diff --git a/tools/pierre.c b/tools/pierre.c
@@ -0,0 +1,28 @@
+#include <stdlib.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <fmpz.h>
+
+#include "pierre.h"
+
+#define DEFAULT_LIMIT 100000000
+
+int main(int argc, char* argv[])
+{
+	if(argc != 2) {
+		printf("Usage: %s <modulus>\n", argv[0]);
+		return(-1);
+	}
+
+	fmpz_t n, r;
+  fmpz_init(n);
+	fmpz_set_str(n, argv[1], 10);
+	fmpz_init(r);
+
+	fermat_factor(r, n, DEFAULT_LIMIT);
+
+	fmpz_print(r);
+  printf("\n");
+
+	return(0);
+}