commit 06129e0ebdc2d60c2250f893b0d318a75d58085a
parent 548ef6908f3a946809715784da57453d6b20089a
Author: olikru <olikru@tkruger.se>
Date: Fri, 1 Dec 2023 21:17:32 +0100
playin
Diffstat:
6 files changed, 106 insertions(+), 26 deletions(-)
diff --git a/.clangd b/.clangd
@@ -0,0 +1,2 @@
+CompileFlags:
+ Add: [-xc, -std=c99, -std=c99, -pedantic, -Wall, -Werror, -Wstrict-prototypes, -Wmissing-prototypes, -Wmissing-declarations, -Wshadow, -Wpointer-arith, -Wcast-qual, -Wsign-compare, -O2, -fstack-protector-all, -Wtype-limits, -fno-common, -fno-builtin, -I/usr/local/include, -I/usr/local/include/flint ]
diff --git a/Makefile b/Makefile
@@ -2,7 +2,8 @@
CC=clang
OBJS=\
-hnp.o
+ hnp.o \
+ dlog_fmpz.o
DEPS=hnp.h
CFLAGS+=-std=c99 -pedantic -Wall -Werror -Wstrict-prototypes
CFLAGS+=-Wmissing-prototypes -Wmissing-declarations -Wshadow
diff --git a/dlog_fmpz.c b/dlog_fmpz.c
@@ -0,0 +1,57 @@
+#include "dlog_fmpz.h"
+
+/**
+ * Solve the discrete logarithm problem a = b^x in mod N where N is as
+ * given by the mod context ctx using brute force. Only looks for
+ * discrete logarithms below the bound bd. This function returns the
+ * number bd if no discrete logarithm could be found.
+ *
+ * Note that this is slow for large N, but may be useful for small N
+ * because of it having very little overhead.
+ *
+ * @return
+ * bd if there is no integer x, 0 <= x < bd such that b^x = a in the
+ * mod context ctx
+ * x such that 0 <= x < bd and b^x = a otherwise
+ */
+ulong dlog_brute(const fmpz_t a, const fmpz_t b, const ulong bd,
+ const fmpz_mod_ctx_t ctx) {
+ fmpz_t c;
+ fmpz_init_set_ui(c, 1);
+
+ ulong i;
+ for (i = 0; i < bd; i++) {
+ if (fmpz_cmp(a, c) == 0) {
+ fmpz_clear(c);
+ return i;
+ }
+
+ fmpz_mod_mul(c, c, b, ctx);
+ }
+
+ return bd;
+}
+
+/**
+ * Solve the discrete logaritm problem a = b^x in mod N where N is as
+ * given by the mod context ctx using the so called Shanks'
+ * baby-step-giant-step algorithm.
+ *
+ * This function will find such an x, if there is one of the form
+ * x = i*m + j, where 0 <= i < bd0 and 0 <= j < bd1.
+ * Note that to be sure that the algorithm succeeds in finding the root
+ * we would use set m, bd0 and bd1 all to the square root of the order
+ * of b mod N (rounded up to the closest integer).
+ *
+ * This function sets the x argument to the result and retuns 0 on
+ * success, and -1 otherwise.
+ *
+ * @return
+ * 0 if an x on the above form solving the discrete logarithm was
+ * found.
+ * -1 otherwise
+ */
+int dlog_bsgs(fmpz_t x, const fmpz_t a, const fmpz_t b, const fmpz_t m,
+ const ulong bd0, const ulong bd1) {
+ return -1;
+}
diff --git a/dlog_fmpz.h b/dlog_fmpz.h
@@ -0,0 +1,14 @@
+#ifndef _DLOG_FMPZ_H_
+#define _DLOG_FMPZ_H_
+
+#include <flint.h>
+#include <fmpz.h>
+#include <fmpz_mod.h>
+#include <gmp.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+ulong dlog_brute(const fmpz_t a, const fmpz_t b, const ulong bd,
+ const fmpz_mod_ctx_t ctx);
+
+#endif
diff --git a/hnp.c b/hnp.c
@@ -16,14 +16,15 @@
* 1 if reduction okay, but solution fails to verify
* 0 if solution found
*/
-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);
+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);
// initialise a zero matrix
fmpz_mat_t A;
- fmpz_mat_init(A, m+2, m+2);
+ fmpz_mat_init(A, m + 2, m + 2);
fmpz_mat_zero(A);
// set up n^2's on the diagonal
@@ -31,53 +32,57 @@ int hidden_number_problem(fmpz* res, const slong nres, const fmpz* t,
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);
+ 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 *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);
+ 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++) {
+ for (i = 0; i < m; i++) {
// t[i]*n
- fmpz* tmp = fmpz_mat_entry(A, m, i);
+ 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);
+ tmp = fmpz_mat_entry(A, m + 1, i);
fmpz_mul(tmp, &a[i], n);
}
// use LLL for lattice reduction (delta = 0.99, eta = 0.501)
fmpq_t delta, eta;
- fmpq_init(delta); fmpq_init(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);
+ fmpq_clear(delta);
+ fmpq_clear(eta);
// 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;
+ 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;
+ 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);
+ 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);
@@ -88,14 +93,14 @@ int hidden_number_problem(fmpz* res, const slong nres, const fmpz* t,
fmpz_t tmp;
fmpz_init(tmp);
- for(i = 0; i < m; i++) {
+ 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) {
+ if (fmpz_cmp_ui(tmp, 0) != 0) {
fmpz_clear(tmp);
return 1;
}
diff --git a/hnp.h b/hnp.h
@@ -2,12 +2,13 @@
#define _HNP_H_
#include <flint.h>
-#include <gmp.h>
-#include <fmpz.h>
#include <fmpq.h>
+#include <fmpz.h>
#include <fmpz_mat.h>
+#include <gmp.h>
-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);
+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
