Мажоритарный принцип

Замечание 1. Известно, что n - разрядными равновесными кодами веса q называют двоичные n - разрядные комбинации, содержащие ровно q единиц и

n - q нулей. Полным равновесным кодом длины n веса q будем называть набор всех кодов, отвечающих данным условиям и обозначать R(n,q).

Замечание 2. P(a,b) - обозначают количество перестановок из a объектов 1-го вида и b объектов второго, это число равно:

P (a,b)= = С =С , (3)

Для R(n,q) число комбинаций равно P(n-q,q).

Рассмотрим поставленную задачу в случае, когда n - нечетное число, а порог

h = (n+1)/2.

Теорема 1. Если n - нечетное число и порог h = (n+1)/2, тогда количество фрагментов ключа k равно числу n разрядных двоичных кодов веса h, а именно

k = P( )= , (4)

а правило распределения ключей между сотрудниками соответствует столбцам полного равновесного кода R(n,q).

Доказательство необходимости и достаточности приведено ниже.

Пример 1. Пусть n = 5 и h = 3. Построим таблицу равновесных 5 -и разрядных кодов веса 3, т.е. R (5,3)

Таблица 1

1 2 3 4 5

----------------------

1) 1 1 1 0 0

2) 1 1 0 1 0

3) 1 1 0 0 1

4) 1 0 1 1 0

5) 1 0 1 0 1

6) 1 0 0 1 1

7) 0 1 1 1 0

8) 0 1 1 0 1

9) 0 1 0 1 1

10) 0 0 1 1 1

В таблице цифрами 1,2,3,4,5 обозначены члены приемной команды, а 1),2),3),... обозначены номера фрагментов. Возьмем для примера 3- го члена команды. Он имеет фрагменты с номерами 1),4),5),7),8),10). Любая тройка членов приемной команды имеет полный набор фрагментов и может составить полный секретный ключ S. При этом никакие пары членов приемной команды не имеют полного набора. Количество фрагментов в данном примере равно 10. Единицы в вертикальном коде соответствуют номерам фрагментов, которые имеет данный член команды.