Giảm mô đun trong vòng $\mathbb{Z}_{q}[x]/(x^n + 1)$

Có thể ai đó vui lòng giải thích làm thế nào giảm được thực hiện? Tôi đã quen thuộc với các cấu trúc đại số khác nhưng tự hỏi liệu tôi có đang rút gọn đúng cách cho việc này không.

Người ta hiểu rằng một vành đa thức có dạng này, $\mathbb{Z}_{q}[x]/(x^n + 1)$, bao gồm tập hợp tất cả các đa thức được xác định bởi $(x^n + 1)$ với hệ số trên $\mathbb{Z}_q = \{0, 1, ..., q-1\}$.

Để đơn giản, giả sử tôi đang làm việc trong $\mathbb{Z}_{5}[x]/[x^4+1]$

Giả sử tôi nhân hai đa thức trong vành theo công thức tích chập.

    3 2 1 0 <- hệ số vô định

$a(x) = 4x^3 + 1x^2 + 1x + 2$

$b(x) = 1x^3 + 1x^2 + 3x + 2$

$n=4, n-1=3$

tất cả số học hệ số được thực hiện mod 5 điều khoản thêm like và giảm mod 5 số âm ta cộng bội của mod 5

$$a(x)\cdot b(x) = ([(a_0b_1x + a_0b_2x^2 + a_0b_3x^3) + (a_1b_2x^3 + a_1b_3x^4 + a_2b_3x^3)] - \ [a_3b_1 + a_2b_2 + a_3b_2x + a_1b_3 + a_2b_3x + a_3b_3x^2]) \mod (x^4 + 1)\ =[(x + 2x^2 + x^3) + (x^3 + x^4 + x^3)] - [(2 + 1 + 4x + 1 + 1x + 4x^2)] \mod.. \ = [x^4 + 3x^3 + 2x^2 + x] - [4x^2 + 4] \mod..\ = [x^4 + 3x^3 + (2-4)x^2 + x - 4] \mod..\ = [x^4 + 3x^3 + 3x^2 + x + 1] \mod (x^4 + 1) $$

Ba câu hỏi:

1. công thức tích chập là chính xác.
2. phép trừ giống như đa thức bình thường: $4x^2 - x^2 = 3x^2$
3. rút gọn: thực hiện như phép chia đa thức chuẩn lấy dư

Được cho $(x^4 + 3x^3 + 3x^2 + x + 1) \mod (x^4 + 1)$: $\Rightarrow (x^4 + 3x^3 + 3x^2 + x + 1) / (x^4 + 1)$ phép trừ đầu tiên: $\Rightarrow (x^4 + 3x^3 + 3x^2 + x + 1) - (x^4 + 1) = 3x^3 + 3x^2 + x$ (câu trả lời cuối cùng)

Được cho $(3x^5 + x^3 + 1) \mod (x^4 + 1) \Rightarrow (3x^5 + x^3 + 1) / 3x(x^4 + 1)$ phép trừ đầu tiên: $\Rightarrow (3x^5 + x^3 + 1) - (3x^5 + 3x) = x^3 - 3x + 1)$

công thức tích chập là chính xác.

Không, nó không đúng; nếu $a = x^0$ và $b = x^0$, công thức của bạn sẽ cho $a \cdot b = 0$, điều đó rõ ràng là sai.

Cách sách giáo khoa để thể hiện hoạt động nhân là:

$$a \cdot b = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} a_i \cdot b_j \cdot x^{i+j} \pmod{x ^n+1}$$

Một cách tương đương (dễ dàng nhận thấy bởi danh tính $x^{k+n} \equiv -x^k \pmod{x^n+1}$ bất cứ gì $k$) Là

$$a \cdot b = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1-i} a_i \cdot b_j \cdot x^{i+j} - \ sum_{i=1}^{n-1} \sum_{j=n-i}^{n-1} a_i \cdot b_j \cdot x^{i+j-n}$$

Tôi tin rằng sau này là những gì bạn dự định

phép trừ giống như đa thức bình thường: $4x^2âx^2=3x^2$

Có (với lưu ý rằng, như chính bạn đã đề cập, các phép toán trong các hệ số đã được thực hiện $\mod p$, trong ví dụ của bạn, $\mod 5$)

rút gọn: thực hiện như phép chia đa thức chuẩn lấy dư

Nó có thể được thực hiện theo cách đó; có khả năng hiệu quả hơn để tận dụng danh tính mà tôi đã đề cập ở trên, đó là $x^{k+n} \equiv -x^k \pmod{ x^n+1 }$)