0
$\begingroup$

Hi this is for the Shamir Secret Sharing algorithm.

How do I create a polynomial of degree k-1 such that P(0) = s (mod m).

where k-1 is just an integer, s is just an integer, m is a large prime.

2 Answers 2

2

It is rather important to pick a polynomial satisfying the given condition randomly for the algorithm to work. Since the polynomial is then used to calculate the different $s_i = f(i) \mod m$ for the different shares.

In particular, choosing a random polynomial f over $Z_m$ of degree k-1 satisfying f(0) = s is equivalent to choosing $a_1, \dots, a_{k-1} \in \mathbb{Z}_m$ at random, with $a_{k-1}\neq 0 \mod m$ and letting f(x) be the polynomial $f(x) = s+a_1x+a_2x^2+\dots+a_{k-1}x^{k-1}$.

  • 0
    To the contrary, it still works. Please read the second article I cited.2011-07-11
1

Am I missing something?

$p(x)=x^{k-1}+s$?

  • 0
    I am not familiar with the algoritm, so I do not know how the polynomials pop-up there. Maybe there are other constraints?2011-07-11