cangrepp

commit 16a8af17350efd4f61cdd6d763f803c68ead9e9f
parent 2cca8591901bbd1e7df71c669c29c1400b69d1b2
Author: olikru <olikru@tkruger.se>
Date:   Sat,  1 Jun 2024 23:34:46 +0200

added test case for hnp

Diffstat:
M
batchgcd.c
 | 
4
++--
M
fmpzio.c
 | 
36
++++++++++++++++++++++++------------
M
fmpzio.h
 | 
6
++++++
M
hnp.c
 | 
6
++++--
M
prodtree.c
 | 
6
------
M
prodtree.h
 | 
6
++++++
M
test_angrepp.c
 | 
39
+++++++++++++++++++++++++++++++++++++++

7 files changed, 81 insertions(+), 22 deletions(-)
diff --git a/batchgcd.c b/batchgcd.c
@@ -59,7 +59,8 @@ upper_bound_2pow(const slong x)
   return r;
 }
 
-
+// incomplete prodtree is like a prodtree, just that we do not compute
+// the root
 static inline slong
 incomplete_prodtree_compute(fmpz** res, const fmpz *v, slong nv)
 {
@@ -87,7 +88,6 @@ incomplete_prodtree_compute(fmpz** res, const fmpz *v, slong nv)
   return tree_size;
 }
 
-// see: https://github.com/epelofske65537/binary_tree_Batch_GCD
 void
 pelofske_gcd(fmpz *r, const fmpz *v, slong n)
 {
diff --git a/fmpzio.c b/fmpzio.c
@@ -1,11 +1,3 @@
-#include <assert.h>
-#include <err.h>
-#include <fmpz.h>
-#include <fmpz_vec.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
 #include "fmpzio.h"
 
 #define BASE_ALLOC 1024
@@ -96,6 +88,27 @@ read_all_stdin(const size_t base_alloc)
   return buffer;
 }
 
+static inline char *
+whitespace_sep(char **s)
+{
+  char *orig = *s;
+
+  if (**s == '\0') {
+    return NULL;
+  }
+
+  while (**s != '\0') {
+    if (**s == ' ' || **s == '\t' || **s == '\n') {
+      **s = '\0';
+      (*s)++;
+      break;
+    }
+    (*s)++;
+  }
+
+  return orig;
+}
+
 slong
 read_hex_lines(fmpz **v)
 {
@@ -112,7 +125,7 @@ read_hex_lines(fmpz **v)
   slong ntokens = 0, tokens_alloc = BASE_ALLOC;
   char **tokens = malloc(tokens_alloc * sizeof(*tokens));
 
-  while ((tokens[ntokens] = strsep(&s, " \n\t")) != NULL) {
+  while ((tokens[ntokens] = whitespace_sep(&s)) != NULL) {
     ntokens++;
 
     if (ntokens == tokens_alloc) {
@@ -125,9 +138,8 @@ read_hex_lines(fmpz **v)
     }
   }
 
-  // ignore last if it is the empty string
-  if (tokens[ntokens][0] == '\0') {
-    ntokens--;
+  if (ntokens == 0) {
+    err(EXIT_FAILURE, "nothing to read for read_hex_lines");
   }
 
   *v = _fmpz_vec_init(ntokens);
diff --git a/fmpzio.h b/fmpzio.h
@@ -1,7 +1,13 @@
 #ifndef _FMPZIO_H_
 #define _FMPZIO_H_
 
+#include <assert.h>
+#include <err.h>
 #include <fmpz.h>
+#include <fmpz_vec.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
 
 /**
  * Read next fmpz from stdin (in base 10).
diff --git a/hnp.c b/hnp.c
@@ -61,9 +61,11 @@ hidden_number_problem(fmpz *res, const slong nres, const fmpz *t,
     if (fmpz_cmpabs(fmpz_mat_entry(A, i, m + 1), Bn) == 0)
       break;
   }
-  if (i >= m + 2)
-    return 1;
   fmpz_clear(Bn);
+  if (i >= m + 2) {
+    fmpz_mat_clear(A);
+    return 1;
+  }
 
   slong r = i;
 
diff --git a/prodtree.c b/prodtree.c
@@ -1,9 +1,3 @@
-#include <err.h>
-#include <fmpz.h>
-#include <fmpz_vec.h>
-#include <stdio.h>
-#include <stdlib.h>
-
 #include "prodtree.h"
 
 static inline slong
diff --git a/prodtree.h b/prodtree.h
@@ -1,6 +1,12 @@
 #ifndef _PRODTREE_H_
 #define _PRODTREE_H_
 
+#include <err.h>
+#include <fmpz.h>
+#include <fmpz_vec.h>
+#include <stdio.h>
+#include <stdlib.h>
+
 /**
  * Compute a prodtree from a vector.
  *
diff --git a/test_angrepp.c b/test_angrepp.c
@@ -10,6 +10,7 @@
 #include "prodtree.h"
 #include "smallfactor.h"
 #include "wiener.h"
+#include "hnp.h"
 
 static uint64_t
 test_f(uint64_t x)
@@ -140,6 +141,43 @@ test_prodtree(void)
   fmpz_clear(sju);
 }
 
+static void
+test_hidden_number_problem(void)
+{
+  fmpz *r, *t, *a;
+  fmpz_t n, B;
+
+  fmpz_init_set_ui(n, 131101);
+  fmpz_init_set_ui(B, 11);
+
+  r = _fmpz_vec_init(4);
+  t = _fmpz_vec_init(3);
+  a = _fmpz_vec_init(3);
+
+  fmpz_set_ui(&t[0], 46396);
+  fmpz_set_ui(&t[1], 3185);
+  fmpz_set_ui(&t[2], 30618);
+
+  fmpz_set_ui(&a[0], 65911);
+  fmpz_set_ui(&a[1], 5049);
+  fmpz_set_ui(&a[2], 56983);
+
+  int ret = hidden_number_problem(r, 4, t, a, 3, n, B);
+
+  assert(ret == 0);
+  assert(fmpz_cmp_si(&r[0], -4) == 0);
+  assert(fmpz_cmp_si(&r[1], -10) == 0);
+  assert(fmpz_cmp_si(&r[2], -6) == 0);
+  assert(fmpz_cmp_si(&r[3], -42028) == 0);
+
+  _fmpz_vec_clear(r, 4);
+  _fmpz_vec_clear(t, 3);
+  _fmpz_vec_clear(a, 3);
+
+  fmpz_clear(n);
+  fmpz_clear(B);
+}
+
 int
 main(void)
 {
@@ -149,6 +187,7 @@ main(void)
   test_wiener_factor_small_d();
   test_smallfactor_euclidean();
   test_prodtree();
+  test_hidden_number_problem();
 
   printf("test ok\n");
 }