Cum să accelerezi generarea de acțiuni secrete Shamir?

Să presupunem că trebuie să generăm cota secretă a lui Shamir pentru n puncte de date. Există o modalitate de a accelera implementarea în afară de utilizarea regulii lui Horner pentru evaluarea polinomului?

Dacă utilizați configurația tipică unde sunt acțiunile $f(1), f(2),\ldots f(n)$ Unde $f(x)=c_kx^k+\cdots+c_0$ este un polinom de grad $k$, atunci puteți folosi calculul diferențelor finite. Sari peste pasul de inițializare pentru moment

pentru j=1,...,n 
    actualizare f = (f + Deltaf[1]) mod p
    pentru i=1,..., k-1 
        actualizare Deltaf[i] = (Deltaf[i] + Deltaf[i+1]) mod p
    scoateți variabila f ca f(j)
Sfârşit

Bucla principală ia $kn$ adăugiri și o creștere (puteți salva $O(k^2)$ adaosuri dacă te simți cu adevărat zgârcit) ceea ce este foarte eficient.

Valoarea inițială a $f$ este $f(0)$. Valorile inițiale ale $\Delta^dacă$ sunt cam dezordonate: $\Delta^if(0)=i!\sum_{j=i}^kc_jS(j,i)$ Unde $S(j,i)$ este o Număr Stirling de al doilea fel. Alternativ, îl puteți evalua pe primul $k$ termenii de $f$ și calculează direct diferențele repetate pentru a calcula următoarea $n-k$.