commit 10a878adc54289a28911c9014bb2aba109f99c59
parent 7cf093214ac397783eb99ad3ef2b332f19884ddb
Author: olikru <olikru@tkruger.se>
Date: Tue, 19 Sep 2023 13:52:08 +0200
sort of working hnp solver
Diffstat:
5 files changed, 120 insertions(+), 72 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+build/
diff --git a/examples/hnp_instance.txt b/examples/hnp_instance.txt
@@ -0,0 +1,4 @@
+3 11 131101
+46396 65911
+3185 5049
+30618 56983
diff --git a/examples/hnpsolve.c b/examples/hnpsolve.c
@@ -1,87 +1,103 @@
#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 <fmpz_vec.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);
+#define LINE_SIZE_MAX 4096
- nmod_mat_randtest(m, state);
+static int read_next_fmpz(fmpz_t res)
+{
+ char buffer[LINE_SIZE_MAX];
+ size_t i;
- flint_randclear(state);
+ int next_char = getchar();
+ while(next_char == '\n' || next_char == ' ')
+ next_char = getchar();
- nmod_mat_print_pretty(m);
+ if(next_char == EOF)
+ return -1;
- nmod_mat_t h;
- nmod_mat_init(h, 4, 4, 13);
+ buffer[0] = next_char;
+ i = 1;
+ while(i < LINE_SIZE_MAX-1) {
+ next_char = getchar();
+ if(next_char == EOF || next_char == '\n' || next_char == ' ')
+ break;
- gr_ctx_t ctx;
- gr_ctx_init_nmod(ctx, 13);
+ buffer[i] = (char) next_char;
- if(gr_mat_hessenberg((gr_mat_struct*) h, (gr_mat_struct*) m, ctx)) {
- printf("Failed to compute Hessenberg matrix...\n");
- exit(1);
+ i++;
}
+ buffer[i] = '\0';
- nmod_mat_print_pretty(h);
+ return fmpz_set_str(res, buffer, 10);
+}
- nmod_mat_t j, p;
- nmod_mat_init(j, 4, 4, 13);
- nmod_mat_init(p, 4, 4, 13);
+static int read_stdin_instance(fmpz** a, fmpz** t, slong* m, fmpz_t* B, fmpz_t* n)
+{
+ flint_scanf("%wd", m);
- 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);
- }
+ if(read_next_fmpz(*B))
+ return -1;
- printf("J = \n");
- nmod_mat_print_pretty(j);
- printf("P = \n");
- nmod_mat_print_pretty(p);
+ if(read_next_fmpz(*n))
+ return -1;
- 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");
+ *a = _fmpz_vec_init(*m);
+ *t = _fmpz_vec_init(*m);
- 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");
+ slong i;
+ int fail = 0;
+ for(i = 0; i < *m; i++) {
+ if(read_next_fmpz(&(*t)[i])) {
+ fail = 1;
+ break;
+ }
- nmod_mat_clear(m);
- nmod_mat_clear(h);
- gr_ctx_clear(ctx);
+ if(read_next_fmpz(&(*a)[i])) {
+ fail = 1;
+ break;
+ }
+ }
- fmpz_t n, B;
- fmpz_init_set_ui(n, 123);
- fmpz_init_set_ui(B, 12);
+ if(fail) {
+ _fmpz_vec_clear(*a, *m);
+ _fmpz_vec_clear(*t, *m);
+ return -1;
+ }
- 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));
+ return 0;
+}
+
+int main(int argc, char* argv[])
+{
+ slong m;
+ fmpz* a;
+ fmpz* t;
+ fmpz_t B, n;
+ fmpz_init(B);
+ fmpz_init(n);
+
+ if(read_stdin_instance(&a, &t, &m, &B, &n) != 0) {
+ fprintf(stderr, "ERROR! Bad input format?\n");
+ exit(1);
}
- fmpz_t res[4];
- hidden_number_problem(res, 4, t, a, 3, n, B);
+ fmpz res[m+1];
+ slong i;
+ for(i = 0; i < m+1; i++) fmpz_init(&res[i]);
+
+ int ret = hidden_number_problem(res, m+1, t, a, m, n, B);
+ if(ret == 0) {
+ for(i = 0; i < m; i++) {
+ fmpz_print(&res[i]);
+ printf(" ");
+ }
+ fmpz_print(&res[m]);
+ printf("\n");
+ }
return 0;
}
diff --git a/hnp.c b/hnp.c
@@ -16,8 +16,8 @@
* 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)
+int hidden_number_problem(fmpz* res, const slong nres, const fmpz* t,
+ const fmpz* a, const slong m, const fmpz_t n, const fmpz_t B)
{
if(nres < m + 1) return(-1);
@@ -47,16 +47,13 @@ int hidden_number_problem(fmpz_t* res, const slong nres, const fmpz_t* t,
for(i = 0; i < m; i++) {
// t[i]*n
fmpz* tmp = fmpz_mat_entry(A, m, i);
- fmpz_mul(tmp, t[i], n);
+ fmpz_mul(tmp, &t[i], n);
// a[i]*n
tmp = fmpz_mat_entry(A, m+1, i);
- fmpz_mul(tmp, a[i], n);
+ 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);
@@ -67,14 +64,44 @@ int hidden_number_problem(fmpz_t* res, const slong nres, const fmpz_t* t,
fmpq_clear(delta); fmpq_clear(eta);
- printf("[+] Post-reduction matrix:\n");
- fmpz_mat_print_pretty(A); printf("\n");
-
// extract the potential solution
+ fmpz_t Bn;
+ fmpz_init(Bn);
+ fmpz_mul(Bn, B, n);
+ for(i = 0; i < m+2; i++) {
+ if(fmpz_cmpabs(fmpz_mat_entry(A, i, m+1), Bn) == 0) break;
+ }
+ if(i >= m+2) return 1;
+ fmpz_clear(Bn);
+
+ slong r = i;
+
+ for(i = 0; i < m; i++) {
+ fmpz* tmp = fmpz_mat_entry(A, r, i);
+ fmpz_tdiv_q(&res[i], tmp, n);
+ }
+ fmpz_tdiv_q(&res[m], fmpz_mat_entry(A, r, m), B);
fmpz_mat_clear(A);
// test that the solution is a solution to original HNP
+ fmpz_t tmp;
+ fmpz_init(tmp);
+
+ for(i = 0; i < m; i++) {
+ // tmp <- t[i]*alpha - a[i] mod n
+ fmpz_mul(tmp, &t[i], &res[m]);
+ fmpz_add(tmp, tmp, &a[i]);
+ fmpz_sub(tmp, tmp, &res[i]);
+ fmpz_mod(tmp, tmp, n);
+
+ if(fmpz_cmp_ui(tmp, 0) != 0) {
+ fmpz_clear(tmp);
+ return 1;
+ }
+ }
+
+ fmpz_clear(tmp);
return 0;
}
diff --git a/hnp.h b/hnp.h
@@ -7,7 +7,7 @@
#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);
+int hidden_number_problem(fmpz* res, const slong nres, const fmpz* t,
+ const fmpz* a, const slong m, const fmpz_t n, const fmpz_t B);
#endif
