计算有限域中的公式

Question

我正在尝试将公式转换为该公式的有限域等价物。

公式如下：

现在我已经实现了它并且它可以正常工作，但是我需要在有限域中使用它，这意味着我引入了一个 p，比方说 p = 183269 andd 取 mod p 但是上面的公式究竟是如何变化的呢？我是不是在正常计算完公式后就mod p？

示例：

我有多项式：f(x) = 1234 + 631x + 442x^2 我生成了 6 个随机点：(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

Do I just mod p after i'm done calculating the formula normally?

没有。首先，您必须计算 x[m] - x[j] 模 p 的乘法逆元。这是有效实施的棘手部分。剩下的确实只是乘法和求和模 p.

请记住，浮点运算不能在有限域中进行。那里的一切在整数意义上都是精确的。

PS：为了解决关于除法的问题，这是除法在有限域中的工作方式：

y/x 实际上是 y * z，其中 z 是 x 的乘法逆元，即 x * z = 1 mod p。例如，让我们使用 7 表示 p。例如 2 的乘法逆是 4：2 * 4 == 8 (== 1 mod 7)。这意味着3/2 mod 7是3 * 4 mod 7，即5.

Answer 2

您应该牢记，始终对两个数相乘后的结果求模。如果 a<p,b<p,c<p for p=183269，a*b*c 会导致 int 溢出。如果 p 较大（如 998244353），a*b 会导致溢出。对于这种情况，在将两个数字 a 和 b 相乘之前，您应该将它们转换为 int64 并将结果乘以 p，最后将其转换回 int.

这里还有一点：a 在模 p 时并不总是等同于 -a。实际上，在大多数情况下这是错误的。您应该改用 a = (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_inverse 的时间复杂度是 O(p)，在大多数情况下效率很低。您可以使用 Extended Euclidean Algorithm to calculate the multiplicative inverse of x modulo p in O(log p) time. Also, the multiplicative inverse of x modulo p is simply (x^(p-2)) % p when p is prime, and you can calculate that fast using Exponentiation by squaring。这两种方法都有 O(log p) 的复杂性，但后一种更容易实现。

抱歉我的英语不好。欢迎指出我的错别字和错误。

计算有限域中的公式

Calculate a formula in a Finite Field

algorithm

go

secret-key

modular-arithmetic