在有限域中计算一个公式。

huangapple go评论81阅读模式
英文:

Calculate a formula in a Finite Field

问题

我正在尝试将一个公式转换为有限域中的等效公式。

下面是该公式的形式:
在有限域中计算一个公式。

我已经实现了这个公式,并且它可以正常工作,但是我需要将其转换为有限域中的形式,也就是引入一个p,假设p = 183269,然后对其进行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 { // 不允许负数
		a = a * -1
	}

	for i := 1; i < p; i++ {
		if ((a % p) * (i % p)) % p == 1 {
			return i
		}
	}

	return p
} 

不幸的是,它仍然存在一个或多个错误,因为它不能产生f(0)

英文:

I am trying to transform a formula over to a finite-field equivalent of that formula.

The formula can be seen below:
在有限域中计算一个公式。

Now I have this implemented and it works correctly, but I need this in a finite-field, which means that I introduce a p, let's say p = 183269 andd take mod p but how exactly does the above formula change? Do I just mod p after i'm done calculating the formula normally?

Example:

I have the polynomial: f(x) = 1234 + 631x + 442x^2
I generated 6 random points: (x, f(x) mod p)

1. (108, 93338)
2. (413, 146507)
3. (260, 171647)
4. (819, 98605)
5. (359, 13237)
6. (894, 118490)

Now, what I want is to reconstruct 1234 given any 3 points using the above formula, but it gives me incorrect value.

here is my code:

// 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
	}

I'm trying to implement SSSS

EDIT

As pointed out by @user58697 I had some mistakes in my code and understanding of finite fields. I managed to rewrite my formula and it looks like this:

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 &lt; 0 { // negative numbers are not allowed
		a = a * -1
	}

	for i := 1; i &lt; p; i++ {
		if ((a % p) * (i % p)) % p == 1 {
			return i
		}
	}

	return p
} 

Unfortunately, it still has one or more bugs because it doesn't produce f(0)

答案1

得分: 4

在计算完公式后,我需要对p取模吗?

不需要。首先,你需要计算x[m] - x[j]p的乘法逆元。这是一个需要高效实现的棘手部分。其余部分确实只涉及乘法和求和,模p运算。

请记住,在有限域中无法进行浮点运算。在这里,一切都是精确的整数。

附注:为了解决关于除法的疑虑,有限域中的除法工作原理如下:

y/x实际上是y * z,其中zx的乘法逆元,即x * z = 1 mod p。例如,假设我们使用7作为p。例如,2的乘法逆元是4:2 * 4 == 8 (== 1 mod 7)。这意味着3/2 mod 7等于3 * 4 mod 7,即5

英文:

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

No. First you have to compute a multiplicative inverse of x[m] - x[j] modulo p. That is a tricky part to implement efficiently. The rest is indeed just multiplications and summation modulo p.

Keep in mind that floating point operations cannot work in the finite field. Everything there is precise in a sense of integers.

PS: to address a concerns about division, this is how division works in a finite field:

y/x is in fact y * z where z is a multiplicative inverse of x, that is x * z = 1 mod p. For example, let's use 7 for p. A multiplicative inverse of, say 2 is 4: 2 * 4 == 8 (== 1 mod 7). This means that 3/2 mod 7 is 3 * 4 mod 7, that is 5.

答案2

得分: 1

你应该记住,在两个数相乘之后,始终要对结果取模。如果对于p=183269a&lt;p,b&lt;p,c&lt;p,那么a*b*c可能会导致整数溢出。如果p更大(比如998244353),那么a*b可能会简单地导致溢出。对于这种情况,在两个数ab相乘之前,你应该将它们转换为int64类型,并对结果取模p,最后再将其转换回int类型。

还有一个要注意的地方:当对p取模时,a并不总是等价于-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)
				// 你忘记了将pr_x乘以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 &lt; 0 { // 不允许负数
		// 下面这行是错误的!(a % p)==(a % p + p)% p当a &lt; 0时,但不是-a
		// a = a * -1
		a = ((a % p) + p) % p
	}

	for i := 1; i &lt; p; i++ {
		if ((a % p) * (i % p)) % p == 1 {
			return i
		}
	}

	// 我怀疑你是否应该在这里报告错误,而不是返回p
	return p
}

顺便说一下,mod_inverse的时间复杂度是O(p),在大多数情况下可能效率较低。你可以使用扩展欧几里得算法来在O(log p)的时间内计算xp的乘法逆元。此外,当p是素数时,xp的乘法逆元可以简单地计算为(x^(p-2)) % p,你可以使用平方取幂算法来快速计算。这两种方法的复杂度都是O(log p),但后一种方法更容易实现。

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

英文:

You should keep it in mind that always to modulo the result after multiplying two numbers. a*b*c can cause int overflow if a&lt;p,b&lt;p,c&lt;p for p=183269. And if p is larger (like 998244353), a*b can simply cause overflow. For this case, before multiplying two numbers a and b, you should cast them into int64 and modulo the result by p and finally cast it back to int.

And another point here: a is not always equivalent with -a when modulo p. Actually this is false in most cases. You should use a = (a % p + p) % p instead.

Below are the modified code that could produce the correct result (I just learned golang for this question so forgive me for possible improper code):

	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 &lt; 0 { // negative numbers are not allowed
		// The following line is wrong! (a % p) == (a % p + p) % p when a &lt; 0, but not -a
		// a = a * -1
		a = ((a % p) + p) % p
	}

	for i := 1; i &lt; 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
}

BTW, the time complexity of mod_inverse is O(p), which can be inefficient in most cases. You can use 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. Both methods has O(log p) complexity, but the later one is easier to implement.

Sorry for my poor English. Feel free to point out my typos and mistakes.

huangapple
  • 本文由 发表于 2021年6月18日 01:54:48
  • 转载请务必保留本文链接:https://go.coder-hub.com/68024344.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定