10#include <botan/mceliece.h>
12#include <botan/internal/bit_ops.h>
19double binomial(
size_t n,
size_t k) {
22 for(
size_t i = 0; i != k; ++i) {
30double log_binomial(
size_t n,
size_t k) {
33 for(
size_t i = 0; i != k; ++i) {
38 return x / std::log(2);
41double nb_iter(
size_t n,
size_t k,
size_t w,
size_t p,
size_t l) {
42 double x = 2 * log_binomial(k / 2, p);
43 x += log_binomial(n - k - l, w - 2 * p);
44 x = log_binomial(n, w) - x;
48double cout_iter(
size_t n,
size_t k,
size_t p,
size_t l) {
49 double x = binomial(k / 2, p);
50 const size_t i =
static_cast<size_t>(std::log(x) / std::log(2));
51 double res = 2 * p * (n - k - l) * std::ldexp(x * x, -
static_cast<int>(l));
59 res += x + k * ((n - k) / 2.0);
61 return std::log(res) / std::log(2);
64double cout_total(
size_t n,
size_t k,
size_t w,
size_t p,
size_t l) {
65 return nb_iter(n, k, w, p, l) + cout_iter(n, k, p, l);
68double best_wf(
size_t n,
size_t k,
size_t w,
size_t p) {
73 double min = cout_total(n, k, w, p, 0);
75 for(
size_t l = 1; l < n - k; ++l) {
76 const double lwf = cout_total(n, k, w, p, l);
92 double min = cout_total(n, k, t, 0, 0);
93 for(
size_t p = 0; p != t / 2; ++p) {
94 double lwf = best_wf(n, k + 1, t, p);
99 min = std::min(min, lwf);
102 return static_cast<size_t>(min);
size_t mceliece_work_factor(size_t n, size_t t)
constexpr uint8_t ceil_log2(T x)