โปรแกรมหาผกผันของพหุนาม

ใครช่วยบอกวิธีหาค่าผกผันของพหุนามที่กำหนดโดยใช้โปรแกรมหลามได้บ้าง ตัวอย่าง: ข้อมูลที่ป้อนคือการหาค่าผกผันของ (x^2 + 1) โมดูโล (x^4 + x + 1) ผลลัพธ์ควรเป็น: (x^3 + x + 1)

Sagemath สามารถแก้ปัญหานี้ได้ และอย่างที่เราทราบกันว่า SageMath ใช้ Python ย้อนกลับได้! ติดตั้งแพ็คเกจโดย;

pip3 ติดตั้ง sagemath

ตอนนี้เราพร้อมที่จะใช้รหัส SageMath แล้ว

k = GF(2)
ร.<x> = k[]
k.extension(x^4 + x + 1, 'ก')
พิมพ์ (k)

พี = (x^2 + 1)

พิมพ์(หน้า)

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

พิมพ์ (คิว)

อย่างไรก็ตาม ร.<x> = k[] ไม่สามารถแยกวิเคราะห์โดย python เราต้องใช้ เตรียม เพื่อสร้างรหัสหลาม

เตรียมการ ('R.<x> = k[]')
"R = k['x']; (x,) = R._first_ngens(1)"

ดังนั้นรหัสหลามคือ

จากการนำเข้า sage.all *

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

พิมพ์(K)

พี = (x**2 + 1)
พิมพ์(หน้า)
q = p.inverse_mod(x**4 + x + 1)
พิมพ์ (คิว)

ผลลัพธ์นี้

ฟิลด์จำกัดในขนาด 2^4
x^2 + 1
x^3 + x + 1

ขอบคุณ John Palmieri ที่ เตรียม

เพื่อคำนวณการกลับด้านของ $พี$ โมดูโล $คิว$ กับ $คิว$ ของปริญญา $n+1$วิธีแก้ปัญหาง่ายๆ คือการแก้ระบบเชิงเส้นที่ไม่รู้จัก: $\lambda_0, \จุด, \lambda_n$ ดังนั้น $P^{-1}= \sum \lambda_i X^i$.

แล้วเรารู้ $(P \cdot(\sum \lambda_i X^i) )\mod Q = 1$. และจากการดูความเท่าเทียมกันของทุกๆ พิกัด เราก็มี $n+1$ สมการด้วย $n+1$ ไม่ทราบ และสมการจะเป็นอิสระต่อกันก็ต่อเมื่อ $พี$ กลับด้านได้ $\mathbb{Z}_p[X]/(Q\mathbb{Z}_p[X])$.

ด้วยตัวอย่างของคุณ $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{แนว}

หากคุณแก้ระบบเชิงเส้นได้ คุณจะพบวิธีแก้ปัญหา $\lambda_2=0$ และ $\lambda_1=\lambda_3=\lambda_0=1$.