计算有限域中的公式

Question

我正在尝试将公式转换为该公式的有限域等效物。公式如下：现在我已经实现了它并且它工作正常，但是我在有限域中需要它，这意味着我引入了一个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)

Answer 1

我是否只是在正常计算完公式后修改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

Answer 2

您应该记住，在将两个数字相乘后，始终要对结果进行取模。 如果 为，则可能导致整型溢出。如果较大（如），则可简单地导致溢出。对于这种情况，在将两个数字和 相乘之前，您应该将它们转换为并将结果取模，最后将其转换回。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)

对不起我的英语不好。随时指出我的拼写错误和错误。