commit 7cf093214ac397783eb99ad3ef2b332f19884ddb
parent 20da4581548b938779b55a217bf98bd060d9fae7
Author: olikru <olikru@tkruger.se>
Date: Mon, 18 Sep 2023 17:59:47 +0200
started hidden number problem
Diffstat:
| A | Makefile | | | 31 | +++++++++++++++++++++++++++++++ |
| M | README | | | 4 | +++- |
| A | examples/hnpsolve.c | | | 87 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | hnp.c | | | 80 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | hnp.h | | | 13 | +++++++++++++ |
5 files changed, 214 insertions(+), 1 deletion(-)
diff --git a/Makefile b/Makefile
@@ -0,0 +1,31 @@
+.SUFFIXES: .o .c
+
+CC=clang
+OBJS=\
+hnp.o
+DEPS=hnp.h
+CFLAGS+=-std=c99 -pedantic -Wall -Werror -Wstrict-prototypes
+CFLAGS+=-Wmissing-prototypes -Wmissing-declarations -Wshadow
+CFLAGS+=-Wpointer-arith -Wcast-qual -Wsign-compare -O2
+CFLAGS+=-fstack-protector-all -Wtype-limits -fno-common
+CFLAGS+=-fno-builtin
+CFLAGS+=-I/usr/local/include/flint -I/usr/local/include
+LDFLAGS=-L/usr/local/lib -lflint -lgmp
+BUILDDIR=build
+EXAMPLES=\
+hnpsolve
+
+all: $(BUILDDIR) $(OBJS) $(EXAMPLES)
+
+$(BUILDDIR):
+ mkdir -p $(BUILDDIR)
+ mkdir -p $(BUILDDIR)/examples
+
+.c.o: $(DEPS)
+ $(CC) $(CFLAGS) -c $< -o $(BUILDDIR)/$@
+
+hnpsolve: examples/hnpsolve.c
+ $(CC) $(CFLAGS) -I./ -o $(BUILDDIR)/examples/hnpsolve examples/hnpsolve.c $(BUILDDIR)/*.o $(LDFLAGS)
+
+clean:
+ rm -rf $(BUILDDIR)
diff --git a/README b/README
@@ -1,4 +1,6 @@
NeoCNT: New C Number Theory
===========================
-This is the new playground for C Number Theory.
+This is the new playground for C Number Theory. It is a way to expolore
+the FLINT library. This is just a playground. Never use this for
+anything.
diff --git a/examples/hnpsolve.c b/examples/hnpsolve.c
@@ -0,0 +1,87 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <flint.h>
+#include <nmod_mat.h>
+#include <nmod_poly.h>
+#include <nmod_poly_factor.h>
+#include <gr_mat.h>
+#include <hnp.h>
+
+int main(int argc, char* argv[])
+{
+ nmod_mat_t m;
+ nmod_mat_init(m, 4, 4, 13);
+
+ flint_rand_t state;
+ flint_randinit(state);
+
+ nmod_mat_randtest(m, state);
+
+ flint_randclear(state);
+
+ nmod_mat_print_pretty(m);
+
+ nmod_mat_t h;
+ nmod_mat_init(h, 4, 4, 13);
+
+ gr_ctx_t ctx;
+ gr_ctx_init_nmod(ctx, 13);
+
+ if(gr_mat_hessenberg((gr_mat_struct*) h, (gr_mat_struct*) m, ctx)) {
+ printf("Failed to compute Hessenberg matrix...\n");
+ exit(1);
+ }
+
+ nmod_mat_print_pretty(h);
+
+ nmod_mat_t j, p;
+ nmod_mat_init(j, 4, 4, 13);
+ nmod_mat_init(p, 4, 4, 13);
+
+ if(gr_mat_jordan_form((gr_mat_struct*) j, (gr_mat_struct*) p,
+ (gr_mat_struct*) m, ctx)) {
+ printf("Failed to compute jordan form\n");
+ exit(1);
+ }
+
+ printf("J = \n");
+ nmod_mat_print_pretty(j);
+ printf("P = \n");
+ nmod_mat_print_pretty(p);
+
+ nmod_poly_t poly;
+ nmod_poly_init(poly, 13);
+ nmod_mat_charpoly(poly, m);
+
+ printf("poly = \n");
+ nmod_poly_print_pretty(poly, "x");
+ printf("\n");
+
+ nmod_poly_factor_t facts;
+ nmod_poly_factor_init(facts);
+
+ nmod_poly_factor(facts, poly);
+ printf("factors = \n");
+ nmod_poly_factor_print_pretty(facts, "z");
+
+ nmod_mat_clear(m);
+ nmod_mat_clear(h);
+ gr_ctx_clear(ctx);
+
+ fmpz_t n, B;
+ fmpz_init_set_ui(n, 123);
+ fmpz_init_set_ui(B, 12);
+
+ fmpz_t t[3];
+ fmpz_t a[3];
+ size_t i;
+ for(i = 0; i < 3; i++) {
+ fmpz_init_set_ui(t[i], 3*(i+1));
+ fmpz_init_set_ui(a[i], 4*(i+1));
+ }
+ fmpz_t res[4];
+
+ hidden_number_problem(res, 4, t, a, 3, n, B);
+
+ return 0;
+}
diff --git a/hnp.c b/hnp.c
@@ -0,0 +1,80 @@
+#include "hnp.h"
+
+/**
+ * Solve the hidden number problem
+ * t[i]*alpha - a[i] == b[i] (mod n), i = 0,1,...,m-1
+ * for
+ * b[i], i = 0,1,...,m-1, and
+ * alpha
+ * where |b[i]| < B.
+ *
+ * @param res
+ * an already initialised vector that has size nres, this vector
+ * may be overwritten even if the result is not verified
+ * @return
+ * -1 if failure (ex. res too small to fit m+1 values)
+ * 1 if reduction okay, but solution fails to verify
+ * 0 if solution found
+ */
+int hidden_number_problem(fmpz_t* res, const slong nres, const fmpz_t* t,
+ const fmpz_t* a, const slong m, const fmpz_t n, const fmpz_t B)
+{
+ if(nres < m + 1) return(-1);
+
+ // initialise a zero matrix
+ fmpz_mat_t A;
+ fmpz_mat_init(A, m+2, m+2);
+ fmpz_mat_zero(A);
+
+ // set up n^2's on the diagonal
+ slong i;
+ fmpz_t n_squared;
+ fmpz_init_set(n_squared, n);
+ fmpz_pow_ui(n_squared, n_squared, 2);
+ for(i = 0; i < m; i++) {
+ fmpz* m_i_i = fmpz_mat_entry(A, i, i);
+ fmpz_set(m_i_i, n_squared);
+ }
+ fmpz_clear(n_squared);
+
+ // setting up last two diagonal entries
+ fmpz* m_i_i = fmpz_mat_entry(A, m, m);
+ fmpz_set(m_i_i, B);
+ m_i_i = fmpz_mat_entry(A, m+1, m+1);
+ fmpz_mul(m_i_i, B, n);
+
+ // columnwise setup
+ for(i = 0; i < m; i++) {
+ // t[i]*n
+ fmpz* tmp = fmpz_mat_entry(A, m, i);
+ fmpz_mul(tmp, t[i], n);
+
+ // a[i]*n
+ tmp = fmpz_mat_entry(A, m+1, i);
+ fmpz_mul(tmp, a[i], n);
+ }
+
+ printf("[+] Pre-reduction matrix:\n");
+ fmpz_mat_print_pretty(A); printf("\n");
+
+ // use LLL for lattice reduction (delta = 0.99, eta = 0.501)
+ fmpq_t delta, eta;
+ fmpq_init(delta); fmpq_init(eta);
+ fmpq_set_ui(delta, 99, 100);
+ fmpq_set_ui(eta, 501, 1000);
+
+ fmpz_mat_lll_original(A, delta, eta);
+
+ fmpq_clear(delta); fmpq_clear(eta);
+
+ printf("[+] Post-reduction matrix:\n");
+ fmpz_mat_print_pretty(A); printf("\n");
+
+ // extract the potential solution
+
+ fmpz_mat_clear(A);
+
+ // test that the solution is a solution to original HNP
+
+ return 0;
+}
diff --git a/hnp.h b/hnp.h
@@ -0,0 +1,13 @@
+#ifndef _HNP_H_
+#define _HNP_H_
+
+#include <flint.h>
+#include <gmp.h>
+#include <fmpz.h>
+#include <fmpq.h>
+#include <fmpz_mat.h>
+
+int hidden_number_problem(fmpz_t* res, const slong nres, const fmpz_t* t,
+ const fmpz_t* a, const slong m, const fmpz_t n, const fmpz_t B);
+
+#endif
