dlog_fmpz.c (1724B)
1 #include "dlog_fmpz.h" 2 3 /** 4 * Solve the discrete logarithm problem a = b^x in mod N where N is as 5 * given by the mod context ctx using brute force. Only looks for 6 * discrete logarithms below the bound bd. This function returns the 7 * number bd if no discrete logarithm could be found. 8 * 9 * Note that this is slow for large N, but may be useful for small N 10 * because of it having very little overhead. 11 * 12 * @return 13 * bd if there is no integer x, 0 <= x < bd such that b^x = a in the 14 * mod context ctx 15 * x such that 0 <= x < bd and b^x = a otherwise 16 */ 17 ulong dlog_brute(const fmpz_t a, const fmpz_t b, const ulong bd, 18 const fmpz_mod_ctx_t ctx) { 19 fmpz_t c; 20 fmpz_init_set_ui(c, 1); 21 22 ulong i; 23 for (i = 0; i < bd; i++) { 24 if (fmpz_cmp(a, c) == 0) { 25 fmpz_clear(c); 26 return i; 27 } 28 29 fmpz_mod_mul(c, c, b, ctx); 30 } 31 32 return bd; 33 } 34 35 /** 36 * Solve the discrete logaritm problem a = b^x in mod N where N is as 37 * given by the mod context ctx using the so called Shanks' 38 * baby-step-giant-step algorithm. 39 * 40 * This function will find such an x, if there is one of the form 41 * x = i*m + j, where 0 <= i < bd0 and 0 <= j < bd1. 42 * Note that to be sure that the algorithm succeeds in finding the root 43 * we would use set m, bd0 and bd1 all to the square root of the order 44 * of b mod N (rounded up to the closest integer). 45 * 46 * This function sets the x argument to the result and retuns 0 on 47 * success, and -1 otherwise. 48 * 49 * @return 50 * 0 if an x on the above form solving the discrete logarithm was 51 * found. 52 * -1 otherwise 53 */ 54 int dlog_bsgs(fmpz_t x, const fmpz_t a, const fmpz_t b, const fmpz_t m, 55 const ulong bd0, const ulong bd1) { 56 return -1; 57 }