cangrepp

Some cryptographic attacks
Log | Files | Refs | README

batchgcd.c (2355B)

      1 #include <err.h>
      2 #include <fmpz.h>
      3 #include <fmpz_vec.h>
      4 #include <stdio.h>
      5 #include <stdlib.h>
      6 
      7 #include "prodtree.h"
      8 #include "batchgcd.h"
      9 
     10 static inline void
     11 remtree_compute(fmpz *tree, const slong tree_size)
     12 {
     13   slong i = tree_size - 2;
     14   slong parent_distance = 1;
     15 
     16   while (1) {
     17     fmpz_mul(&tree[i], &tree[i], &tree[i]);
     18     fmpz_mod(&tree[i], &tree[i + parent_distance], &tree[i]);
     19     parent_distance++;
     20     i--;
     21 
     22     fmpz_mul(&tree[i], &tree[i], &tree[i]);
     23     fmpz_mod(&tree[i], &tree[i + parent_distance], &tree[i]);
     24     if(i == 0) break;
     25     i--;
     26   }
     27 }
     28 
     29 void
     30 batch_gcd(fmpz *r, const fmpz *v, slong n)
     31 {
     32   fmpz *tree;
     33   slong tree_size, i;
     34   
     35   tree_size = prodtree_compute(&tree, v, n);
     36   remtree_compute(tree, tree_size);
     37 
     38   for(i = 0; i < n; i++) {
     39     fmpz_fdiv_q(&r[i], &tree[i], &v[i]);
     40     fmpz_gcd(&r[i], &r[i], &v[i]);
     41   }
     42 
     43   free(tree);
     44 }
     45 
     46 static inline slong
     47 upper_bound_2pow(const slong x)
     48 {
     49   slong r = 1;
     50 
     51   while (r < x) {
     52     r <<= 1;
     53 
     54     if (r == 0) {
     55       err(EXIT_FAILURE, "upper bound 2pow failure");
     56     }
     57   }
     58 
     59   return r;
     60 }
     61 
     62 // incomplete prodtree is like a prodtree, just that we do not compute
     63 // the root
     64 static inline slong
     65 incomplete_prodtree_compute(fmpz** res, const fmpz *v, slong nv)
     66 {
     67   slong ubound = upper_bound_2pow(nv);
     68   slong tree_size = 2 * ubound - 1;
     69   slong i, j;
     70 
     71   *res = _fmpz_vec_init(tree_size);
     72 
     73   // row 0, v and padded with ones
     74   for (i = 0; i < nv; i++) {
     75     fmpz_set(&(*res)[i], &v[i]);
     76   }
     77   for (i = nv; i < ubound; i++) {
     78     fmpz_set_ui(&(*res)[i], 1);
     79   }
     80 
     81   // rest, not root
     82   j = 0;
     83   for (i = ubound; i < tree_size-1; i++) {
     84     fmpz_mul(&(*res)[i], &(*res)[j], &(*res)[j + 1]);
     85     j += 2;
     86   }
     87 
     88   return tree_size;
     89 }
     90 
     91 void
     92 pelofske_gcd(fmpz *r, const fmpz *v, slong n)
     93 {
     94   fmpz *tree;
     95   fmpz *bvec;
     96   fmpz *bbtree;
     97   slong tree_size, i, ninb, bbtree_size;
     98 
     99   tree_size = incomplete_prodtree_compute(&tree, v, n);
    100 
    101   bvec = _fmpz_vec_init(tree_size);
    102   ninb = 0;
    103 
    104   for(i = 0; i < tree_size-1; i+=2) {
    105     fmpz_gcd(&bvec[ninb], &tree[i], &tree[i+1]);
    106     if (fmpz_cmp_ui(&bvec[ninb], 1) != 0) {
    107       ninb++;
    108     } 
    109   }
    110 
    111   bbtree_size = prodtree_compute(&bbtree, bvec, ninb); 
    112 
    113   for(i = 0; i < n; i++) {
    114     fmpz_gcd(&r[i], &bbtree[bbtree_size-1], &v[i]);
    115   }
    116 
    117   _fmpz_vec_clear(tree, tree_size);
    118   _fmpz_vec_clear(bvec, tree_size);
    119   _fmpz_vec_clear(bbtree, bbtree_size);
    120 }