hnp.c (2590B)
1 #include "hnp.h" 2 3 /** 4 * Solve the hidden number problem 5 * t[i]*alpha - a[i] == b[i] (mod n), i = 0,1,...,m-1 6 * for 7 * b[i], i = 0,1,...,m-1, and 8 * alpha 9 * where |b[i]| < B. 10 * 11 * @param res 12 * an already initialised vector that has size nres, this vector 13 * may be overwritten even if the result is not verified 14 * @return 15 * -1 if failure (ex. res too small to fit m+1 values) 16 * 1 if reduction okay, but solution fails to verify 17 * 0 if solution found 18 */ 19 int hidden_number_problem(fmpz *res, const slong nres, const fmpz *t, 20 const fmpz *a, const slong m, const fmpz_t n, 21 const fmpz_t B) { 22 if (nres < m + 1) 23 return (-1); 24 25 // initialise a zero matrix 26 fmpz_mat_t A; 27 fmpz_mat_init(A, m + 2, m + 2); 28 fmpz_mat_zero(A); 29 30 // set up n^2's on the diagonal 31 slong i; 32 fmpz_t n_squared; 33 fmpz_init_set(n_squared, n); 34 fmpz_pow_ui(n_squared, n_squared, 2); 35 for (i = 0; i < m; i++) { 36 fmpz *m_i_i = fmpz_mat_entry(A, i, i); 37 fmpz_set(m_i_i, n_squared); 38 } 39 fmpz_clear(n_squared); 40 41 // setting up last two diagonal entries 42 fmpz *m_i_i = fmpz_mat_entry(A, m, m); 43 fmpz_set(m_i_i, B); 44 m_i_i = fmpz_mat_entry(A, m + 1, m + 1); 45 fmpz_mul(m_i_i, B, n); 46 47 // columnwise setup 48 for (i = 0; i < m; i++) { 49 // t[i]*n 50 fmpz *tmp = fmpz_mat_entry(A, m, i); 51 fmpz_mul(tmp, &t[i], n); 52 53 // a[i]*n 54 tmp = fmpz_mat_entry(A, m + 1, i); 55 fmpz_mul(tmp, &a[i], n); 56 } 57 58 // use LLL for lattice reduction (delta = 0.99, eta = 0.501) 59 fmpq_t delta, eta; 60 fmpq_init(delta); 61 fmpq_init(eta); 62 fmpq_set_ui(delta, 99, 100); 63 fmpq_set_ui(eta, 501, 1000); 64 65 fmpz_mat_lll_original(A, delta, eta); 66 67 fmpq_clear(delta); 68 fmpq_clear(eta); 69 70 // extract the potential solution 71 fmpz_t Bn; 72 fmpz_init(Bn); 73 fmpz_mul(Bn, B, n); 74 for (i = 0; i < m + 2; i++) { 75 if (fmpz_cmpabs(fmpz_mat_entry(A, i, m + 1), Bn) == 0) 76 break; 77 } 78 if (i >= m + 2) 79 return 1; 80 fmpz_clear(Bn); 81 82 slong r = i; 83 84 for (i = 0; i < m; i++) { 85 fmpz *tmp = fmpz_mat_entry(A, r, i); 86 fmpz_tdiv_q(&res[i], tmp, n); 87 } 88 fmpz_tdiv_q(&res[m], fmpz_mat_entry(A, r, m), B); 89 90 fmpz_mat_clear(A); 91 92 // test that the solution is a solution to original HNP 93 fmpz_t tmp; 94 fmpz_init(tmp); 95 96 for (i = 0; i < m; i++) { 97 // tmp <- t[i]*alpha - a[i] mod n 98 fmpz_mul(tmp, &t[i], &res[m]); 99 fmpz_add(tmp, tmp, &a[i]); 100 fmpz_sub(tmp, tmp, &res[i]); 101 fmpz_mod(tmp, tmp, n); 102 103 if (fmpz_cmp_ui(tmp, 0) != 0) { 104 fmpz_clear(tmp); 105 return 1; 106 } 107 } 108 109 fmpz_clear(tmp); 110 111 return 0; 112 }