计算有限域中的公式

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

编辑

正如我所指出的，我在代码和对有限域的理解中犯了一些错误。我设法重写了我的公式，它看起来像这样：@user58697

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)

                pr_x *= inv

            }

        }

        y *= pr_x

        reconstructed += y

    }

    return reconstructed % p

func 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，所以请原谅我可能的不当代码）：&nbsp; &nbsp; reconstructed := 0&nbsp; &nbsp; for _, k := range x_input {&nbsp; &nbsp; &nbsp; &nbsp; y := points[k]&nbsp; &nbsp; &nbsp; &nbsp; pr_x := 1&nbsp; &nbsp; &nbsp; &nbsp; for _, l := range x_input {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if l != k {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; inv := mod_inverse(l - k, p)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // You forgot to multiply pr_x by l&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // pr_x *= inv&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pr_x = pr_x * inv % p * l % p&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; y = y * pr_x % p&nbsp; &nbsp; &nbsp; &nbsp; reconstructed += y&nbsp; &nbsp; }&nbsp; &nbsp; return reconstructed % pfunc mod_inverse(a, p int) int {&nbsp; &nbsp; if a < 0 { // negative numbers are not allowed&nbsp; &nbsp; &nbsp; &nbsp; // The following line is wrong! (a % p) == (a % p + p) % p when a < 0, but not -a&nbsp; &nbsp; &nbsp; &nbsp; // a = a * -1&nbsp; &nbsp; &nbsp; &nbsp; a = ((a % p) + p) % p&nbsp; &nbsp; }&nbsp; &nbsp; for i := 1; i < p; i++ {&nbsp; &nbsp; &nbsp; &nbsp; if ((a % p) * (i % p)) % p == 1 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return i&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // I suspect whether you should report an error here instead of returning p&nbsp; &nbsp; return p}顺便说一句，的时间复杂度是 ，在大多数情况下可能是低效的。您可以使用扩展欧几里得算法来计算时间上模的乘法逆。此外，模的乘法逆值只是当是素数时，你可以使用平方的幂快速计算。这两种方法都很复杂，但后一种方法更容易实现。mod_inverseO(p)xpO(log p)xp(x^(p-2)) % ppO(log p)对不起我的英语不好。随时指出我的拼写错误和错误。