Как получить коэффициенты полинома степени n mod p?

Question

F (x) = a ₀ + a ₁ x + a ₂ x ² +. , , + a _n x ⁿ - полиномиальная функция степени n, существует достаточно методов для нахождения коэффициентов полиномиального уравнения F (x). (то есть нахождение значений a ₀ , a ₁ , a ₂ , ... a _n ) Однако мне было интересно, как получить коэффициенты уравнения F (x) = (a ₀ + a ₁ x + a ₂ x ² +... + A _n x ⁿ )% p . Где р простое число. Например, рассмотрим уравнение F (x) = (a ₀ + a ₁ x + a ₂ x ² )% p Пусть a ₀ = 5, a ₁ = 3 и a ₃ = 2, и P = 71 , затем F (10) = 22 * ​​1054 *, F (20) = 13 , F (30) = 49 для х = 10, 20, 30. Есть ли способ найти такие же коэффициенты F (x) (т.е. ₀ , ₁ и ₂ ) из данные P (= 71) , F (10) , F (20) , F (30) для x = 10 , 20, 30?

Answer 1

Вы можете решить это как набор линейных уравнений. Для сложения вычитания и умножения выполните операции по модулю n. Для деления умножьте на обратное умножение. Возьмите пример, приведенный в вопросе. Уравнения получаются:

(Все рассчитано по модулю 71)

1. a0 + 10a1 + 29a2 == 22 
2. a0 + 20a1 + 45a2 == 13 
3. a0 + 30a1 + 48a2 == 49

Вычитать уравнения 1 из 2

4. 10a1 + 16a2 == 62    

Вычитать уравнения 2 из 3

5. 10a1 + 3a2 == 36 

Вычтите 5 из 4, чтобы получить

13a2 == 26
=>a2 == 26/13 == 26*11 == 2

Те же методы, которые применяются к общим полиномам, могут быть изменены. Например, мы можем использовать матрицу для программного решения системы линейных уравнений.