Как ускорить генерацию секрета Шамира?

Допустим, нам нужно сгенерировать секретную долю Шамира для n точек данных. Есть ли способ ускорить реализацию, кроме использования правила Хорнера для полиномиальной оценки?

Если вы используете типичную настройку, где общие ресурсы $f(1), f(2),\ldots f(n)$ куда $f(x)=c_kx^k+\cdots+c_0$ является полиномом степени $к$, то вы можете использовать исчисление конечных разностей. Пропуская этап инициализации на данный момент

для j=1,...,n 
    обновить f = (f + Deltaf[1]) mod p
    для i=1,...,k-1 
        обновить Deltaf[i] = (Deltaf[i] + Deltaf[i+1]) mod p
    вывести переменную f как f(j)
КОНЕЦ

Основной цикл занимает $kn$ дополнения и приращения (вы можете сохранить $ О (к ^ 2) $ дополнения, если вы чувствуете себя очень скупым), что очень эффективно.

Начальное значение $ф$ является $ф(0)$. Начальные значения $\Дельта^если$ немного сумбурны: $\Delta^if(0)=i!\sum_{j=i}^kc_jS(j,i)$ куда $S(j,i)$ это Число Стирлинга второго рода. В качестве альтернативы вы можете оценить первый $к$ условия $ф$ и непосредственно вычислить повторяющиеся различия для вычисления следующего $nk$.