拉格朗日插值法
对某个多项式函数,已知有给定的k + 1个取值点:(x0,y0)...(xk,yk)
假设任意两个不同的xj都互不相同,那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为:
1 | l0 = (((x-x1)(x-x2)...(x-xk))/((x0-x1)(x0-x2)...(x0-xk)))*y0 |
f(x) = l0+l1...+lk
即可求出多项式
example
1 | 已知3个点(4,10)(5,5.25)(6,1) |
Shamir 秘密共享
生成
- 设需要生成w个密钥,至少需要t个密钥才能算出真实密钥
- 选择一个数P,之后所有数都需要进行模运算
- 设置真实密钥K
- 随机选择t-1个不大于P的数
a0,a1...at-1
- 得到多项式
f(x)=K+a0x+a1x^2...+at-1x^t
- 将
x=1.x=2...x=w
带入多项式即可获得多个密钥(1,k1)(2,k2)...(w,kw)
解密
- 利用拉格朗日插值法即可算出多项式
- 需要带上模计算多项式,如果计算多项式时有除法需要进行计算模乘逆元
- 因为只需要K所以计算的时候可以直接x=0
eg1
1 | w=4,t=3,K=2,p=23,选择随机数 a0=3, a1=2 |
eg2
1 | w=5,t=3,k=13,p=17,选择随机数a0=10,a1=2 |
中国剩余定理
example
1 | w=5,t=3,K=117 |