Chương trình tìm nghịch đảo của đa thức

Ai đó có thể cho tôi biết cách tìm nghịch đảo của một đa thức đã cho bằng lập trình python không? Ví dụ: đầu vào đã cho là để tìm nghịch đảo của (x^2 + 1) modulo (x^4 + x + 1). đầu ra phải là: (x^3 + x + 1).

Để tính nghịch đảo của $P$ modulo $Q$ với $Q$ bằng cấp $n+1$, một giải pháp dễ dàng có thể là giải một hệ thống tuyến tính chưa biết: $\lambda_0, \dots, \lambda_n$ như vậy mà $P^{-1}= \sum \lambda_i X^i$.

Sau đó, chúng tôi biết $(P \cdot(\sum \lambda_i X^i) )\mod Q = 1$. Và bằng cách tìm sự bằng nhau cho mọi tọa độ, chúng ta có $n+1$ phương trình với $n+1$ không biết. Và các phương trình là độc lập khi và chỉ khi $P$ là nghịch đảo trong $\mathbb{Z}_p[X]/(Q\mathbb{Z}_p[X])$.

Với ví dụ của bạn $n=3$. \begin{align}((X^2 +1) \cdot( \lambda_0 + \lambda_1 X + \lambda_2 X^2 + \lambda_3 X^3) )\mod (X^4 + X + 1) = 1 \ \ \lambda_0 + \lambda_1 X + (\lambda_2+\lambda_0) X^2 + (\lambda_3+ \lambda_1) X^3 + (\lambda_2 + \lambda_3X) X^4= 1 \ \lambda_0 + \lambda_1 X + (\lambda_2+\lambda_0) X^2 + (\lambda_3+ \lambda_1) X^3 + (\lambda_2 + \lambda_3X) (-X-1)= 1 \ (\lambda_0-\lambda_2) + (\lambda_1- \lambda_2 - \lambda_3) X + (\lambda_2+\lambda_0-\lambda_3) X^2 + (\lambda_3+ \lambda_1) X^3 = 1 \end{align}

Nếu bạn giải hệ phương trình tuyến tính, bạn sẽ tìm được nghiệm $\lambda_2=0$ và $\lambda_1=\lambda_3=\lambda_0=1$.

Chà, Sagemath có thể giải quyết vấn đề này và như chúng ta biết SageMath sử dụng Python. Điều ngược lại cũng có thể xảy ra! Cài đặt gói bằng cách;

cài đặt pip3 sagemath

Bây giờ chúng tôi đã sẵn sàng để sử dụng mã SageMath

k = GF(2)
R.<x> = k[]
k.extension(x^4 + x + 1, 'a')
in(k)

p = (x^2 + 1)

in(p)

q = p.inverse_mod(x^4 + x + 1)

in(q)

Tuy nhiên, các R.<x> = k[] không thể phân tích cú pháp bằng python. chúng ta phải sử dụng chuẩn bị để tạo mã python.

preparse('R.<x> = k[]')
"R = k['x']; (x,) = R._first_ngens(1)"

Vì vậy, mã python là

từ sage.all nhập *

F = GF(2)
R = F['x']; (x,) = R._first_ngens(1)
K = F.extension(x**4 + x + 1, 'a')

in(K)

p = (x**2 + 1)
in(p)
q = p.inverse_mod(x**4 + x + 1)
in(q)

Điều này xuất ra;

Trường hữu hạn có kích thước 2^4
x^2 + 1
x^3 + x + 1

Cảm ơn John Palmieri trên chuẩn bị