英文:
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 < 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
}
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
,其中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
。
英文:
> 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=183269
,a<p,b<p,c<p
,那么a*b*c
可能会导致整数溢出。如果p
更大(比如998244353
),那么a*b
可能会简单地导致溢出。对于这种情况,在两个数a
和b
相乘之前,你应该将它们转换为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 < 0 { // 不允许负数
// 下面这行是错误的!(a % p)==(a % p + p)% p当a < 0时,但不是-a
// a = a * -1
a = ((a % p) + p) % p
}
for i := 1; i < p; i++ {
if ((a % p) * (i % p)) % p == 1 {
return i
}
}
// 我怀疑你是否应该在这里报告错误,而不是返回p
return p
}
顺便说一下,mod_inverse
的时间复杂度是O(p)
,在大多数情况下可能效率较低。你可以使用扩展欧几里得算法来在O(log p)
的时间内计算x
对p
的乘法逆元。此外,当p
是素数时,x
对p
的乘法逆元可以简单地计算为(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<p,b<p,c<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 < 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
}
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论