Điểm:0

Tìm nghịch đảo nhân trong trường Galois $2^8$ sử dụng thuật toán Euclides mở rộng

lá cờ sx

Tôi đang xử lý các trường Galois $GF(2^{8})$ và cần giúp tìm một đa thức $r^{-1}(x)$ như vậy mà $r^{-1}(x) r(x) \equiv 1 \mod m(x)$, ở đâu:

  • $m(x) = x^{8} + x^{4} + x^{3} + x + 1$
  • $r(x) = u(x) - q(x) \cdot m(x)$
  • $u(x) = s(x) \cdot t(x)$
  • $s(x) = x^{7} + x^{5} + x^{4} + x$
  • $t(x) = x^{4} + x^{2} + 1$

Như vậy:

  • $u(x) = x^{11} + x^{8} + x^{6} + x^{4} + x^{3} + x$
  • $q(x) = x^{3} + 1$
  • $r(x) = -x^{7} - x^{4} - x^{3} + 1 \mod 2 = x^{7} + x^{4} + x^{3} + 1$

những gì tôi đã cố gắng

Tôi đã cố gắng tìm hiểu $r^{-1}(x)$ nhưng không thành công.

Đây là những gì tôi đã thử:

Từ thuật toán của Euclides:

\begin{align*} u(x) &= q(x) \cdot m(x) + r(x) \ m(x) &= q_{2}(x) \cdot r(x) + r_{2}(x) \ &= x \cdot r(x) + (-x^{5} + x^{3} + 1 \mod 2) \ &= x \cdot r(x) + ( x^{5} + x^{3} + 1) \ r(x) &= q_{3}(x) \cdot r_{2}(x) + r_{3}(x) \ &= (x^{2} - 1 \mod 2) \cdot r_{2}(x) + (x^{4} + 2 x^{3} - x^{2} + 2 \mod 2) \ \ &= (x^{2} + 1) \cdot r_{2}(x) + (x^{4} + x^{2}) \ r_{2}(x) &= q_{4}(x) \cdot r_{3}(x) + r_{4}(x) \ &= x \cdot r_{3}(x) + 1 \ r_{3}(x) &= q_{5}(x) \cdot r_{4}(x) + r_{5}(x) \ &= (x^{4} + x^{2}) \cdot r_{4}(x) + 0 \end{align*}

Chúng ta có:

\begin{align*} q_{2}(x) &= x \ q_{3}(x) &= x^{2} + 1 \ q_{4}(x) &= x \ q_{5}(x) &= x^{4} + x^{2} \ r_{2}(x) &= x^{5} + x^{3} + 1 \ r_{3}(x) &= x^{4} + x^{2} \ r_{4}(x) &= 1 \ r_{5}(x) &= 0 \end{align*}

Như vậy:

\begin{align*} 1 &= r_{4}(x) \ &= r_{2}(x) - q_{4}(x)r_{3}(x) \ &= r_{2}(x) - q_{4}(x)\big(r(x) - q_{3}(x)r_{2}(x)\big) \ &= \big(-q_{4}(x)\big) r(x) + \big(1 + q_{3}(x)\big) r_{2}(x) \ &= \big(-q_{4}(x)\big) r(x) + \big(1 + q_{3}(x)\big) \big(m(x) - q_{2}(x)r(x)\big) \ &= \Big(-q_{4}(x) - q_{2}(x) - q_{2}(x)q_{3}(x)\Big) r(x) + \Lớn(1 + q_{r}(x)\Lớn) m(x) \end{align*}

Vì vậy, chúng tôi nhận được:

\begin{align*} r^{-1}(x) & = - q_{4}(x) - q_{2}(x) - q_{2}(x)q_{3}(x) & \mod 2 \ & = - x - x - x(x^{2} + 1) & \mod 2 \ & = - x - x - x^{3} - x & \mod 2 \ & = - x^{3} - 3x & \mod 2 \ & = x^{3} + x \end{align*}

Nhưng, điều này là sai bởi vì khi tôi tính toán $r^{-1}(x) r(x) \mod m(x)$ kết quả không phải là 1

lá cờ us
"mod 2" đến từ đâu?
blackyellow avatar
lá cờ sx
@SamGinrich mod 2 là vì chúng tôi đang ở $GF(2^n)$
lá cờ us
$GF(2^n)$ là một cái gì đó modulo $m(x)$
blackyellow avatar
lá cờ sx
Xin lỗi, tôi không hiểu những gì tôi đã làm sai ..Tôi gặp khó khăn trong việc hiểu thuật toán (đó là lý do tại sao tôi cần trợ giúp). Tôi đã tính $\mod 2$ vì tôi nghĩ các hệ số đa thức phải bằng $\{0,1\}$ vì chúng ta đang xử lý byte. Nếu bạn có thể giải thích những gì tôi đã làm sai, tôi sẽ đánh giá cao nó!
fgrieu avatar
lá cờ ng
Tôi đoán nó muốn nghịch đảo đa thức của $s(x)\cdot t(x)$ modulo $m(x)$, và theo hướng này bạn xác định $r(x)=s(x)\cdot t(x)\ bmod m(x)$. Không có định nghĩa này, tôi không hiểu được _thus_ $u(x)=s(x)\cdot t(x)$.
blackyellow avatar
lá cờ sx
@fgrieu Tôi quên đề cập rằng $u(x) = s(x) \cdot t(x)$ vì nó được định nghĩa theo cách này trong bài toán
Điểm:1
lá cờ ng

Một vấn đề là ở đâu $$r_{2}(x) - q_{4}(x)\big(r(x) - q_{3}(x)r_{2}(x)\big)$$trở thành$$\big(-q_{4}(x)\big) r(x) +\big(1 + q_{3}(x)\big) r_{2}(x)$$khi đó nên được$$\big(-q_{4}(x)\big) r(x) +\big(1 + q_{4}(x)\cdot q_{3}(x)\big) r_{2}( x)$$


Một cách độc lập, tôi nghĩ tốt nhất nên sử dụng thuật toán đơn giản hơn đáng kể ở đó, chỉ cần theo dõi 4 biến.

blackyellow avatar
lá cờ sx
Cảm ơn bạn! Đó là nơi tôi đã sai! Chúa ban phước lành cho bạn vì tôi đã rất căng thẳng với câu hỏi này ...
blackyellow avatar
lá cờ sx
Nhân tiện, tôi đã triển khai thuật toán đơn giản hơn mà bạn đã nói thay vì thuật toán tôi đang sử dụng trước đây.... cảm ơn!

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.