cangrepp

commit ace98028e9d3891ff28dce38464e739b79b34b8d
parent 0d004f8dc08eaf883f8a5d98b531b5dbd2662924
Author: olikru <olikru@tkruger.se>
Date:   Mon, 15 Jan 2024 17:05:53 +0100

basic floyd cyclefinder added

Diffstat:
M
Makefile
 | 
9
+++++++--
A
cyclefind.c
 | 
30
++++++++++++++++++++++++++++++
A
cyclefind.h
 | 
8
++++++++
A
tools/lcgfloyd.c
 | 
43
+++++++++++++++++++++++++++++++++++++++++++

4 files changed, 88 insertions(+), 2 deletions(-)
diff --git a/Makefile b/Makefile
@@ -18,9 +18,11 @@ TEST_SOURCE=test_angrepp.c
 HEADERS=smallfactor.h
 OBJS=\
 smallfactor.o\
-hnp.o
+hnp.o\
+cyclefind.o
 TOOLS=\
-hnpsolve
+hnpsolve\
+lcgfloyd
 PRECOMPUTERS=\
 primorial16bit
 SHARED=angrepp.so
@@ -51,6 +53,9 @@ test: $(TEST_SOURCE)
 hnpsolve: build $(OBJS)
 	$(CC) -I. $(CFLAGS) -o $(BUILD)/tools/hnpsolve $(TOOLS_DIR)/hnpsolve.c $(BUILD_OBJS) $(LDFLAGS)
 
+lcgfloyd: build $(OBJS)
+	$(CC) -I. $(CFLAGS) -o $(BUILD)/tools/lcgfloyd $(TOOLS_DIR)/lcgfloyd.c $(BUILD_OBJS) $(LDFLAGS)
+
 # -- precomputers
 
 primorial16bit: build $(OBJS)
diff --git a/cyclefind.c b/cyclefind.c
@@ -0,0 +1,30 @@
+#include "cyclefind.h"
+
+#include <stdio.h>
+
+uint64_t cyclefind_floyd(uint64_t *mu, uint64_t x0, uint64_t (*f)(uint64_t)) {
+  uint64_t t = f(x0);
+  uint64_t h = f(t);
+  uint64_t lam = 1;
+
+  while (h != t) {
+    t = f(t);
+    h = f(f(h));
+  }
+
+  *mu = 0;
+  t = x0;
+  while (t != h) {
+    t = f(t);
+    h = f(h);
+    (*mu)++;
+  }
+
+  h = f(t);
+  while (t != h) {
+    h = f(h);
+    lam++;
+  }
+
+  return lam;
+}
diff --git a/cyclefind.h b/cyclefind.h
@@ -0,0 +1,8 @@
+#ifndef CYCLEFIND_H
+#define CYCLEFIND_H
+
+#include <stdlib.h>
+
+uint64_t cyclefind_floyd(uint64_t *mu, uint64_t x0, uint64_t (*f)(uint64_t));
+
+#endif
diff --git a/tools/lcgfloyd.c b/tools/lcgfloyd.c
@@ -0,0 +1,43 @@
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <cyclefind.h>
+
+uint64_t a;
+uint64_t b;
+uint64_t M;
+
+static uint64_t f(uint64_t x) { return (a * x + b) % M; }
+
+static void print_usage(char *argv[]) {
+  printf("Usage: %s <a> <b> <x0> <M>\n"
+         "   a  : multiplier constant\n"
+         "   b  : additive constant\n"
+         "   x0 : starting value\n"
+         "   M  : modulus\n",
+         argv[0]);
+}
+
+int main(int argc, char *argv[]) {
+  if (argc != 5) {
+    print_usage(argv);
+    exit(EXIT_FAILURE);
+  }
+
+  errno = 0;
+  a = strtoull(argv[1], NULL, 10);
+  b = strtoull(argv[2], NULL, 10);
+  uint64_t x0 = strtoull(argv[3], NULL, 10);
+  M = strtoull(argv[4], NULL, 10);
+
+  if (errno != 0) {
+    fprintf(stderr, "Error! Could not interpret command line arguments\n");
+    exit(EXIT_FAILURE);
+  }
+
+  uint64_t mu;
+  uint64_t lambda = cyclefind_floyd(&mu, x0, &f);
+
+  printf("mu = %llu, lambda = %llu\n", mu, lambda);
+}