commit b09f9d502737ffd1bb850a4a737319c18cf7a62d
parent 4d0d581701c661d98c56b9d77b0c061c2ca11821
Author: olikru <olikru@tkruger.se>
Date: Thu, 11 Jan 2024 13:43:09 +0100
smallfactor_euclidean implemented
Diffstat:
3 files changed, 85 insertions(+), 4 deletions(-)
diff --git a/Makefile b/Makefile
@@ -38,7 +38,7 @@ build:
mkdir -p $(BUILD)/precomputers
.c.o:
- $(CC) $(CFLAGS) -c $< -o $(BUILD)/$@
+ $(CC) -fPIC $(CFLAGS) -c $< -o $(BUILD)/$@
$(SHARED):
$(CC) -shared -fPIC $(BUILD_OBJS) -o $(BUILD)/$(SHARED) $(LDFLAGS)
diff --git a/smallfactor.c b/smallfactor.c
@@ -1,5 +1,61 @@
#include "smallfactor.h"
-int smallfactor(int x, int y) {
- return x * y;
+#define N_EIGHT_BIT_PRIMES 54
+const uint64_t EIGHT_BIT_PRIMES[N_EIGHT_BIT_PRIMES] = {
+ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
+ 31, 37, 41, 43, 47, 53, 59, 61, 67,
+ 71, 73, 79, 83, 89, 97, 101, 103,
+ 107, 109, 113, 127, 131, 137, 139,
+ 149, 151, 157, 163, 167, 173, 179,
+ 181, 191, 193, 197, 199, 211, 223,
+ 227, 229, 233, 239, 241, 251};
+
+size_t smallfactor_euclidean(fmpz_t out, fmpz_t n) {
+ size_t i;
+ fmpz_t r;
+ FILE* primorial_file = fopen(SMALLFACTOR_PRIMORIAL_FILENAME, "rb");
+
+ if(primorial_file == NULL) {
+ fprintf(stderr, "Error! smallfactor_euclidean: "
+ "could not open asset file %s\n", SMALLFACTOR_PRIMORIAL_FILENAME);
+ exit(EXIT_FAILURE);
+ }
+
+ fmpz_t primorial;
+ fmpz_init(primorial);
+
+ if(fmpz_inp_raw(primorial, primorial_file) == 0) {
+ fprintf(stderr, "Error! smallfactor_euclidean: "
+ "could not read primorial from asset file\n");
+ exit(EXIT_FAILURE);
+ }
+
+ fmpz_gcd(out, n, primorial);
+
+ if(fmpz_cmp_ui(out, 1) > 0 && fmpz_cmp(out, n) < 0) {
+ // 1 < g < n
+ return SMALLFACTOR_FOUND;
+ } else if(fmpz_cmp(out, n) == 0) {
+ // g = n, so n divides p
+ if(fmpz_cmp_ui(n, 1) == 0) {
+ // 1 only has trivial factors
+ return SMALLFACTOR_NOT_FOUND;
+ } else {
+ // n is either prime or has an 8-bit prime factor, trial divide
+ fmpz_init(r);
+ for(i = 0; i < N_EIGHT_BIT_PRIMES; i++) {
+ fmpz_set_ui(r, EIGHT_BIT_PRIMES[i]);
+ fmpz_tdiv_qr(out, r, n, r);
+
+ if (fmpz_cmp_ui(r, 0) == 0)
+ break;
+ }
+ fmpz_clear(r);
+
+ if(i < N_EIGHT_BIT_PRIMES)
+ return SMALLFACTOR_FOUND;
+ }
+ }
+
+ return SMALLFACTOR_NOT_FOUND;
}
diff --git a/smallfactor.h b/smallfactor.h
@@ -2,7 +2,32 @@
#define SMALLFACTOR_H
#include <stdlib.h>
+#include <flint.h>
+#include <fmpz.h>
-int smallfactor(int x, int y);
+#define SMALLFACTOR_PRIMORIAL_FILENAME ("assets/primorial16b.bin")
+#define SMALLFACTOR_FOUND 1
+#define SMALLFACTOR_NOT_FOUND 0
+
+/**
+ * Euclidean small factor finder
+ *
+ * Try to find a small, non-trivial, factor of the number n. This is
+ * done by computing gcd(n, p) where p is the product of all primes less
+ * than 2^16. If SMALLFACTOR_FOUND is returned the out variable is set
+ * to a non-trivial factor of n. If this does not find a non-trivial
+ * factor SMALLFACTOR_NOT_FOUND is returned.
+ *
+ * This is often quicker than trial division if we want a cheap way of
+ * filtering out composite numbers with small factors form a list of
+ * composite numbers where most of the numbers only have large factors.
+ *
+ * @param out where to write the output
+ * @param n the number to try to find factors of
+ * @returns
+ * SMALLFACTOR_FOUND if out was set to a nontrivial factor of n
+ * SMALLFACTOR_NOT_FOUND otherwise
+ */
+size_t smallfactor_euclidean(fmpz_t out, fmpz_t n);
#endif
