Схема интерполяционных полиномов Лагранжа

Интернет магазин китайских планшетных компьютеров

Компьютеры - Схема интерполяционных полиномов Лагранжа - Описание

23 января 2011

Оглавление:
1. Схема интерполяционных полиномов Лагранжа
2. Описание
3. Пример

Пусть нужно разделить секрет M между n сторонами таким образом, чтобы любые k участников могли бы восстановить секрет-пороговую схему).

Выберем некоторое простое число p > M. Это число можно открыто сказать всем участникам. Оно задаёт конечное поле размера p. Над этим полем построим многочлен степени k − 1:

$F \left = \left \mod p$

В этом многочлене M — это разделяемый секрет, а остальные коэффициенты $a_{k-1}, a_{k-2}, \dots, a_1$ — некоторые случайные числа, которые нужно будет «забыть» после того, как процедура разделения секрета будет завершена.

Теперь вычисляем координаты различных n точек:

$\begin{align} k_1 &=& F \left &=& \left &\mod p \\ k_2 &=& F \left &=& \left &\mod p \\ && \dots \\ k_i &=& F \left &=& \left &\mod p \\ && \dots \\ k_n &=& F \left &=& \left &\mod p \\ \end{align}$

Аргументы не обязательно должны идти по порядку, главное - чтобы все они были различны по модулю p.

После этого секреты раздаются сторонам. Случайные коэффициенты $a_{k-1}, a_{k-2}, \dots, a_1$ и сам секрет M «забываются».

Теперь любые k участников, зная координаты k различных точек многочлена, смогут восстановить многочлен и все его коэффициенты, включая последний из них — разделённый секрет.

Особенностью схемы является то, что даже k − 1 сторон, собравшихся вместе, не смогут найти секрет даже методом полного перебора всех возможных вариантов.

Прямолинейное восстановление коэффициентов многочлена через решение системы уравнений можно заменить на вычисление интерполяционного многочлена Лагранжа. Формула многочлена будет выглядеть следующим образом:

$\begin{align} F\left &=& \sum\limits_i {l_i \lefty_i } &\mod p \\ l_i \left &=& \prod\limits_{i \ne j} {\frac{{x - x_j }}{{x_i - x_j }}} &\mod p \\ \end{align}$

где $\left$ — координаты точек многочлена. Все операции выполняются также в конечном поле p.

<<< Схема Блэкли

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие