Блог

Я пытаюсь преобразовать формулу в эквивалент этой формулы в конечном поле.

Формулу можно увидеть ниже:

Теперь у меня это реализовано, и это работает правильно, но мне это нужно в конечном поле, что означает, что я ввожу 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)
 

Теперь я хочу восстановить 1234, учитывая любые 3 точки, используя приведенную выше формулу, но она дает мне неверное значение.

вот мой код:

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

Могу ли я просто изменить p после того, как я обычно рассчитываю формулу?

Нет. Сначала вы должны вычислить мультипликативную обратную 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 .

Вы должны иметь в виду, что всегда нужно умножать результат по модулю после умножения двух чисел. a*b*c может вызвать переполнение int, если a<p,b<p,c<p для p=183269 . А если p больше (например 998244353 ), a*b может просто вызвать переполнение. В этом случае, прежде чем умножать два числа a и b , вы должны привести их к int64 результату по модулю p и, наконец, привести его обратно int .

И еще один момент здесь: a не всегда эквивалентно, -a когда по модулю p . На самом деле в большинстве случаев это ложь. Вы должны использовать 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 is O(p) , которая в большинстве случаев может быть неэффективной. Вы можете использовать расширенный евклидов алгоритм для вычисления мультипликативной обратной x зависимости по модулю p во O(log p) времени. Кроме того, мультипликативная обратная x величина по модулю p просто (x^(p-2)) % p p равна простому числу, и вы можете быстро вычислить это, используя возведение в степень путем возведения в квадрат. Оба метода O(log p) сложны, но более поздний проще в реализации.

Извините за мой плохой английский. Не стесняйтесь указывать на мои опечатки и ошибки.