cangrepp

commit d162e6c2fb73d96c9ee2c09f23595fd12e144364
parent 97570040f0f6a08e47108aa21cd9d493893d603d
Author: olikru <olikru@tkruger.se>
Date:   Tue, 16 Apr 2024 12:27:06 +0200

added some documentation

Diffstat:
M
pierre.h
 | 
13
+++++++++++++
M
test_angrepp.c
 | 
3
++-
M
wiener.h
 | 
32
++++++++++++++++++++++++++++++++

3 files changed, 47 insertions(+), 1 deletion(-)
diff --git a/pierre.h b/pierre.h
@@ -1,6 +1,19 @@
 #ifndef _PIERRE_H_
 #define _PIERRE_H_
 
+/**
+ * Fermat factorisation of an integer.
+ *
+ * Tries to perform Fermat factorisation of the n with an iteration
+ * limit. Finds a factor if
+ *   n + i^2
+ * is a perfect square for some i in [1, limit]. If no factor is found
+ * it sets res to 0.
+ *
+ * @param res   the output fmpz_t
+ * @param n     the number to attempt to Fermat factorise
+ * @param limit iteration limit bound
+ */
 void fermat_factor(fmpz_t r, fmpz_t n, size_t limit);
 
 #endif
diff --git a/test_angrepp.c b/test_angrepp.c
@@ -62,8 +62,9 @@ test_wiener_factor_small_d(void)
   fmpz_set_str(N, "32193226917433121", 10);
   fmpz_set_str(e, "8403467516040173", 10);
 
-  wiener_factor_small_d(res, e, N);
+  int ret = wiener_factor_small_d(res, e, N);
 
+  assert(ret == 1);
   assert(fmpz_divisible(N, res));
   assert(fmpz_cmp_ui(res, 1) > 0);
 
diff --git a/wiener.h b/wiener.h
@@ -4,9 +4,41 @@
 #include <fmpq.h>
 #include <fmpz.h>
 
+/**
+ * Wiener factorisation with general k/d approximation.
+ *
+ * This uses the Wiener method (continued fraction expansion) for
+ * finding a factor of N, where (N, e) is assumed to be an RSA-modulus
+ * and the corresponding public exponent, when the quotient k/d is
+ * "close enough" to x. Here we assume that
+ *   d : the corresponding private exponent
+ *   k : (e*d-1)/((p-1)*(q-1)).
+ *
+ * @param res the result fmpz_t
+ * @param x   approximation of k/d
+ * @param e   public exponent
+ * @param N   public RSA-modulus
+ * @returns
+ *   1 if a factor is found
+ *   0 otherwise
+ */
 int wiener_factor(fmpz_t res, const fmpq_t x, const fmpz_t e,
                   const fmpz_t N);
 
+/**
+ * Wiener factorisation for small private exponent.
+ *
+ * Standard version of the Wiener factorisation method, which works when
+ * e/N is a "close enough" approximation of k/d. This "close enough"
+ * happens when d < (1/3) N^(1/4).
+ *
+ * @param res the result fmpz_t
+ * @param e   public exponent e
+ * @param N   public RSA-modulus
+ * @returns
+ *   1 if a factor is found
+ *   0 otherwise
+ */
 int wiener_factor_small_d(fmpz_t res, const fmpz_t e, const fmpz_t N);
 
 #endif