wiener.h (1425B)
1 #ifndef _WIENER_H_ 2 #define _WIENER_H_ 3 4 #include <fmpq.h> 5 #include <fmpz.h> 6 #include <assert.h> 7 8 #include "context.h" 9 10 /** 11 * Wiener factorisation with general k/d approximation. 12 * 13 * This uses the Wiener method (continued fraction expansion) for 14 * finding a factor of N, where (N, e) is assumed to be an RSA-modulus 15 * and the corresponding public exponent, when the quotient k/d is 16 * "close enough" to x. Here we assume that 17 * d : the corresponding private exponent 18 * k : (e*d-1)/((p-1)*(q-1)). 19 * 20 * @param ctx context used for temporary variables 21 * @param res the result fmpz_t 22 * @param x approximation of k/d 23 * @param e public exponent 24 * @param N public RSA-modulus 25 * @returns 26 * 1 if a factor is found 27 * 0 otherwise 28 */ 29 int wiener_factor(ctx_t *ctx, fmpz_t res, const fmpq_t x, 30 const fmpz_t e, const fmpz_t N); 31 32 /** 33 * Wiener factorisation for small private exponent. 34 * 35 * Standard version of the Wiener factorisation method, which works when 36 * e/N is a "close enough" approximation of k/d. This "close enough" 37 * happens when d < (1/3) N^(1/4). 38 * 39 * @param ctx context used for temporary variables 40 * @param res the result fmpz_t 41 * @param e public exponent e 42 * @param N public RSA-modulus 43 * @returns 44 * 1 if a factor is found 45 * 0 otherwise 46 */ 47 int wiener_factor_small_d(ctx_t *ctx, fmpz_t res, const fmpz_t e, 48 const fmpz_t N); 49 50 #endif