第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全,請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問題,去搜搜看,總會(huì)有你想問的

計(jì)算有限域中的公式

計(jì)算有限域中的公式

Go
料青山看我應(yīng)如是 2022-09-05 17:56:17
我正在嘗試將公式轉(zhuǎn)換為該公式的有限域等效物。公式如下:現(xiàn)在我已經(jīng)實(shí)現(xiàn)了它并且它工作正常,但是我在有限域中需要它,這意味著我引入了一個(gè)p,讓我們說并采取,但是上面的公式究竟是如何變化的?我是否只是在正常計(jì)算完公式之后?p = 183269mod pmod p例:我有多項(xiàng)式:我生成了6個(gè)隨機(jī)點(diǎn):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)現(xiàn)在,我想要的是使用上面的公式在給定任何3個(gè)點(diǎn)的情況下重建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    }我正在嘗試實(shí)現(xiàn) SSSS編輯正如我所指出的,我在代碼和對(duì)有限域的理解中犯了一些錯(cuò)誤。我設(shè)法重寫了我的公式,它看起來像這樣:@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} 不幸的是,它仍然有一個(gè)或多個(gè)錯(cuò)誤,因?yàn)樗粫?huì)產(chǎn)生f(0)
查看完整描述

2 回答

?
慕妹3146593

TA貢獻(xiàn)1820條經(jīng)驗(yàn) 獲得超9個(gè)贊

我是否只是在正常計(jì)算完公式后修改p?

不。首先,您必須計(jì)算模的乘法逆。這是有效實(shí)施的棘手部分。其余的確實(shí)只是乘法和求和模。x[m] - x[j]pp

請(qǐng)記住,浮點(diǎn)運(yùn)算不能在有限域中工作。那里的一切都是精確的整數(shù)。

PS:為了解決有關(guān)除法的問題,這就是除法在有限領(lǐng)域中的工作方式:

y/x實(shí)際上哪里是 的乘法逆,即 。例如,讓我們使用 7 表示 。比方 2 的乘法逆比是 4:。這意味著 ,即 。y * zzxx * z = 1 mod pp2 * 4 == 8 (== 1 mod 7)3/2 mod 73 * 4 mod 75


查看完整回答
反對(duì) 回復(fù) 2022-09-05
?
www說

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ò)誤。


查看完整回答
反對(duì) 回復(fù) 2022-09-05
  • 2 回答
  • 0 關(guān)注
  • 126 瀏覽

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)