10#include <botan/mceliece.h>
11#include <botan/internal/bit_ops.h>
18double binomial(
size_t n,
size_t k)
22 for(
size_t i = 0; i != k; ++i)
31double log_binomial(
size_t n,
size_t k)
35 for(
size_t i = 0; i != k; ++i)
41 return x / std::log(2);
44double nb_iter(
size_t n,
size_t k,
size_t w,
size_t p,
size_t l)
46 double x = 2 * log_binomial(k / 2, p);
47 x += log_binomial(n - k - l, w - 2 * p);
48 x = log_binomial(n, w) - x;
52double cout_iter(
size_t n,
size_t k,
size_t p,
size_t l)
54 double x = binomial(k / 2, p);
55 const size_t i =
static_cast<size_t>(std::log(x) / std::log(2));
56 double res = 2 * p * (n - k - l) * std::ldexp(x * x, -
static_cast<int>(l));
64 res += x + k * ((n - k) / 2.0);
66 return std::log(res) / std::log(2);
69double cout_total(
size_t n,
size_t k,
size_t w,
size_t p,
size_t l)
71 return nb_iter(n, k, w, p, l) + cout_iter(n, k, p, l);
74double best_wf(
size_t n,
size_t k,
size_t w,
size_t p)
79 double min = cout_total(n, k, w, p, 0);
81 for(
size_t l = 1; l < n - k; ++l)
83 const double lwf = cout_total(n, k, w, p, l);
99 double min = cout_total(n, k, t, 0, 0);
100 for(
size_t p = 0; p != t / 2; ++p)
102 double lwf = best_wf(n, k + 1, t, p);
106 min = std::min(min, lwf);
109 return static_cast<size_t>(min);
size_t mceliece_work_factor(size_t n, size_t t)
constexpr uint8_t ceil_log2(T x)