我正在嘗試將公式轉換為該公式的有限域等效物。公式如下：現在我已經實現了它并且它工作正常，但是我在有限域中需要它，這意味著我引入了一個p，讓我們說并采取，但是上面的公式究竟是如何變化的？我是否只是在正常計算完公式之后？p = 183269mod pmod p例：我有多項式：我生成了6個隨機點：f(x) = 1234 + 631x + 442x^2(x, f(x) mod p)1. (108, 93338)2. (413, 146507)3. (260, 171647)4. (819, 98605)5. (359, 13237)6. (894, 118490)現在，我想要的是使用上面的公式在給定任何3個點的情況下重建1234，但它給了我不正確的值。這是我的代碼：// x_input = [108, 413, 260] var reconstructed float64 = 0.0 for _, k := range x_input { var y float64 = float64(points[k]) var pr_x float64 = 1.0 for _, l := range x_input { if l != k { var aux_k float64 = float64(k) var aux_l float64 = float64(l) pr_x *= (aux_l / (aux_l - aux_k)) } } y *= pr_x reconstructed += y }我正在嘗試實現 SSSS編輯正如我所指出的，我在代碼和對有限域的理解中犯了一些錯誤。我設法重寫了我的公式，它看起來像這樣：@user58697reconstructed := 0 for _, k := range x_input { y := points[k] pr_x := 1 for _, l := range x_input { if l != k { inv := mod_inverse(l - k, p) pr_x *= inv } } y *= pr_x reconstructed += y } return reconstructed % pfunc mod_inverse(a, p int) int { if a < 0 { // negative numbers are not allowed a = a * -1 } for i := 1; i < p; i++ { if ((a % p) * (i % p)) % p == 1 { return i } } return p} 不幸的是，它仍然有一個或多個錯誤，因為它不會產生f(0)
2 回答
慕妹3146593
TA貢獻1820條經驗 獲得超9個贊
我是否只是在正常計算完公式后修改p？
不。首先，您必須計算模的乘法逆。這是有效實施的棘手部分。其余的確實只是乘法和求和模。x[m] - x[j]pp
請記住，浮點運算不能在有限域中工作。那里的一切都是精確的整數。
PS：為了解決有關除法的問題，這就是除法在有限領域中的工作方式：
y/x實際上哪里是 的乘法逆，即 。例如，讓我們使用 7 表示 。比方 2 的乘法逆比是 4：。這意味著 ，即 。y * zzxx * z = 1 mod pp2 * 4 == 8 (== 1 mod 7)3/2 mod 73 * 4 mod 75
www說
TA貢獻1775條經驗 獲得超8個贊
您應該記住，在將兩個數字相乘后，始終要對結果進行取模。 如果 為，則可能導致整型溢出。如果較大（如），則可簡單地導致溢出。對于這種情況，在將兩個數字和 相乘之前，您應該將它們轉換為并將結果取模，最后將其轉換回。a*b*ca<p,b<p,c<pp=183269p998244353a*babint64pint
這里的另一點：并不總是等價于當模。實際上，在大多數情況下，這是錯誤的。您應該改用。a-apa = (a % p + p) % p
以下是可以產生正確結果的修改代碼（我剛剛學習了這個問題的golang，所以請原諒我可能的不當代碼）：
reconstructed := 0
for _, k := range x_input {
y := points[k]
pr_x := 1
for _, l := range x_input {
if l != k {
inv := mod_inverse(l - k, p)
// You forgot to multiply pr_x by l
// pr_x *= inv
pr_x = pr_x * inv % p * l % p
}
}
y = y * pr_x % p
reconstructed += y
}
return reconstructed % p
func mod_inverse(a, p int) int {
if a < 0 { // negative numbers are not allowed
// The following line is wrong! (a % p) == (a % p + p) % p when a < 0, but not -a
// a = a * -1
a = ((a % p) + p) % p
}
for i := 1; i < p; i++ {
if ((a % p) * (i % p)) % p == 1 {
return i
}
}
// I suspect whether you should report an error here instead of returning p
return p
}
順便說一句，的時間復雜度是 ，在大多數情況下可能是低效的。您可以使用擴展歐幾里得算法來計算時間上模的乘法逆。此外，模的乘法逆值只是當是素數時，你可以使用平方的冪快速計算。這兩種方法都很復雜，但后一種方法更容易實現。mod_inverseO(p)xpO(log p)xp(x^(p-2)) % ppO(log p)
對不起我的英語不好。隨時指出我的拼寫錯誤和錯誤。
- 2 回答
- 0 關注
- 121 瀏覽
添加回答
舉報
0/150
提交
取消