Решение для переменных, равных сумме кодировок

Question

Проблема от здесь

Предпочтительным способом работы с несколькими кандидатами является использование метода, так как Baudron et al.[16]: предположим, что у нас есть n избирателей, выберите m так, чтобы m было наименьшим целым числом, таким, что 2 ^ m> n.Теперь голосование за кандидата 1 кодируется как 2 ^ 0, за кандидата 2 - 2 ^ m, за кандидата 3 - 2 ^ (2 * m) и так далее.Другими словами, переопределите (1) как

Табуляция такая же, как и раньше: Π (g^xi*yi)*g^vi = g^Σvi.Голоса суммируются, и сверхрасходный характер кодирования гарантирует, что итоговая сумма может быть однозначно разделена на итоговые значения для кандидатов.Следовательно, Σvi = 2^0 * c1 + 2^m * c2 + ... + 2^(k-1)m * ck, где c1 - ck являются подсчетами голосов для k кандидатов соответственно.Как и прежде, это разрешение требует поиска возможных комбинаций, но, конечно, предварительное вычисление по (более вероятным) комбинациям может ускорить это.

В основном заданная сумма v, как найти c так, чтобыэто уравнение верно:

, где k - количество кандидатов, а m - наименьшее целое число, такое что 2 ^ m> max # голосов.

Некоторые вещи, которые могут быть полезны при ограничении пространства поиска:

• max (c) = число зарегистрированных голосов
• существует уникальный набор c, которыйравно некоторой сумме, v
• сумма c's <= число записанных голосов </li>

Answer 1

Условие 2^m > n необходимо, чтобы сделать формулу

Σvi = 2^0 * c1 + 2^m * c2 + ... + 2^(k-1)m * ck

обратимой из суммы в ci.Вы не указали свою среду, поэтому я буду использовать некоторый псевдокод в стиле C

tmp = sum;
p = power(2,m);
for(i = 0; i< k; i++) {
    c[i] = tmp % p; // i.e. calculate reminder, often also called mod
    tmp = tmp / p;  // whole division on (big) integers
}

Это должно работать, потому что условие 2^m > n гарантирует, что с ci <= n так транзитивно ci < 2^m и, таким образом,не может быть "переполнения".По сути, идея состоит в том, чтобы представить подсчет голосов как число в системе с огромным числом 2^m, а каждая цифра - это просто число голосов за соответствующего кандидата.