2 回答

TA貢獻(xiàn)1820條經(jīng)驗(yàn) 獲得超9個(gè)贊
我是否只是在正常計(jì)算完公式后修改p?
不。首先,您必須計(jì)算模的乘法逆。這是有效實(shí)施的棘手部分。其余的確實(shí)只是乘法和求和模。x[m] - x[j]
p
p
請(qǐng)記住,浮點(diǎn)運(yùn)算不能在有限域中工作。那里的一切都是精確的整數(shù)。
PS:為了解決有關(guān)除法的問題,這就是除法在有限領(lǐng)域中的工作方式:
y/x
實(shí)際上哪里是 的乘法逆,即 。例如,讓我們使用 7 表示 。比方 2 的乘法逆比是 4:。這意味著 ,即 。y * z
z
x
x * z = 1 mod p
p
2 * 4 == 8 (== 1 mod 7)
3/2 mod 7
3 * 4 mod 7
5

TA貢獻(xiàn)1775條經(jīng)驗(yàn) 獲得超8個(gè)贊
您應(yīng)該記住,在將兩個(gè)數(shù)字相乘后,始終要對(duì)結(jié)果進(jìn)行取模。 如果 為,則可能導(dǎo)致整型溢出。如果較大(如),則可簡(jiǎn)單地導(dǎo)致溢出。對(duì)于這種情況,在將兩個(gè)數(shù)字和 相乘之前,您應(yīng)該將它們轉(zhuǎn)換為并將結(jié)果取模,最后將其轉(zhuǎn)換回。a*b*ca<p,b<p,c<pp=183269p998244353a*babint64pint
這里的另一點(diǎn):并不總是等價(jià)于當(dāng)模。實(shí)際上,在大多數(shù)情況下,這是錯(cuò)誤的。您應(yīng)該改用。a-apa = (a % p + p) % p
以下是可以產(chǎn)生正確結(jié)果的修改代碼(我剛剛學(xué)習(xí)了這個(gè)問題的golang,所以請(qǐng)?jiān)徫铱赡艿牟划?dāng)代碼):
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
}
順便說一句,的時(shí)間復(fù)雜度是 ,在大多數(shù)情況下可能是低效的。您可以使用擴(kuò)展歐幾里得算法來計(jì)算時(shí)間上模的乘法逆。此外,模的乘法逆值只是當(dāng)是素?cái)?shù)時(shí),你可以使用平方的冪快速計(jì)算。這兩種方法都很復(fù)雜,但后一種方法更容易實(shí)現(xiàn)。mod_inverseO(p)xpO(log p)xp(x^(p-2)) % ppO(log p)
對(duì)不起我的英語不好。隨時(shí)指出我的拼寫錯(cuò)誤和錯(cuò)誤。
- 2 回答
- 0 關(guān)注
- 126 瀏覽
添加回答
舉報(bào)