cangrepp

Some cryptographic attacks
Log | Files | Refs | README

prodtree.c (1005B)

      1 #include "prodtree.h"
      2 
      3 static inline slong
      4 upper_bound_2pow(const slong x)
      5 {
      6   slong r = 1;
      7 
      8   while (r < x) {
      9     r <<= 1;
     10 
     11     if (r == 0) {
     12       err(EXIT_FAILURE, "upper bound 2pow failure");
     13     }
     14   }
     15 
     16   return r;
     17 }
     18 
     19 slong
     20 prodtree_compute(fmpz **res, const fmpz *v, slong nv)
     21 {
     22   slong ubound = upper_bound_2pow(nv);
     23   slong tree_size = 2 * ubound - 1;
     24   slong i, j;
     25 
     26   *res = _fmpz_vec_init(tree_size);
     27 
     28   // row 0, v and padded with ones
     29   for (i = 0; i < nv; i++) {
     30     fmpz_set(&(*res)[i], &v[i]);
     31   }
     32   for (i = nv; i < ubound; i++) {
     33     fmpz_set_ui(&(*res)[i], 1);
     34   }
     35 
     36   // rest
     37   j = 0;
     38   for (i = ubound; i < tree_size; i++) {
     39     fmpz_mul(&(*res)[i], &(*res)[j], &(*res)[j + 1]);
     40     j += 2;
     41   }
     42 
     43   return tree_size;
     44 }
     45 
     46 void
     47 prodtree_pprint(const fmpz *v, const slong nv)
     48 {
     49   slong i, j = 0, row_len = (nv + 1) >> 1;
     50 
     51   for (i = 0; i < nv; i++) {
     52     fmpz_print(&v[i]);
     53     printf(" ");
     54 
     55     j++;
     56 
     57     if (j == row_len) {
     58       printf("\n");
     59       row_len >>= 1;
     60       j = 0;
     61     }
     62   }
     63 }