cangrepp

Some cryptographic attacks
Log | Files | Refs | README

cyclefind.c (849B)

      1 #include "cyclefind.h"
      2 
      3 uint64_t
      4 cyclefind_floyd(uint64_t *mu, uint64_t x0, uint64_t (*f)(uint64_t))
      5 {
      6   uint64_t t = f(x0);
      7   uint64_t h = f(t);
      8   uint64_t lam = 1;
      9 
     10   while (h != t) {
     11     t = f(t);
     12     h = f(f(h));
     13   }
     14 
     15   *mu = 0;
     16   t = x0;
     17   while (t != h) {
     18     t = f(t);
     19     h = f(h);
     20     (*mu)++;
     21   }
     22 
     23   h = f(t);
     24   while (t != h) {
     25     h = f(h);
     26     lam++;
     27   }
     28 
     29   return lam;
     30 }
     31 
     32 uint64_t
     33 cyclefind_brent(uint64_t *mu, uint64_t x0, uint64_t (*f)(uint64_t))
     34 {
     35   size_t i;
     36   uint64_t power = 1;
     37   uint64_t lam = 1;
     38   uint64_t t = x0;
     39   uint64_t h = f(x0);
     40 
     41   while (t != h) {
     42     if (power == lam) {
     43       t = h;
     44       power <<= 1;
     45       lam = 0;
     46     }
     47 
     48     h = f(h);
     49     lam++;
     50   }
     51 
     52   h = x0;
     53   t = h;
     54 
     55   for (i = 0; i < lam; i++) {
     56     h = f(h);
     57   }
     58 
     59   *mu = 0;
     60   while (t != h) {
     61     t = f(t);
     62     h = f(h);
     63     (*mu)++;
     64   }
     65 
     66   return lam;
     67 }