Thuật toán giải mã Patterson cho mã Goppa

Từ trang Wiki này: được cấp mã Goppa $\Gamma(g, L)$ và một từ nhị phân $v=(v_0,...,v_{n-1})$, hội chứng của nó được định nghĩa là $$s(x)=\sum_{i=0}^{n-1}\frac{v_i}{x-L_i} \mod g(x).$$ Để sửa lỗi, thuật toán của Patterson diễn ra như sau:

• Tính toán $$v(x)=\sqrt{s(x)^{-1}-x}\mod g(x)$$ (điều này giả định rằng $s(x)\ne 0$, luôn luôn như vậy trừ khi $v$ thuộc về $\Gamma(g,L)$ và không cần hiệu chỉnh).

• Sử dụng EEA để có được các đa thức $a(x)$ và $b(x)$ như vậy mà $$ a(x)=b(x)v(x)\mod g(x)$$

• Tính đa thức $p(x)=a(x)+xb(x)^2$. Giả sử rằng từ gốc có thể giải mã được, điều này sẽ giống như từ được phân tích thành hệ số định vị lỗi đa thức $$\sigma(x)=\prod_{i\in B}(x-L_i) $$ ở đâu $B=\{i \text{ s.t. } e_i\ne 0\}$.

• Giả sử rằng từ gốc có thể giải mã được (nghĩa là $|B|<d$ ở đâu $d$ là khoảng cách tối thiểu của mã), chúng tôi chỉ cần tính toán rễ của $\sigma(x)$: nếu $L_i$ là root, sau đó xảy ra lỗi như trong các $i$-vị trí thứ.

Tôi chỉ có một câu hỏi: làm thế nào để chứng minh rằng đa thức $p(x)$ thu được trong bước thứ ba tương ứng chính xác với $\sigma(x)$ như định nghĩa ở trên?

Đầu tiên lưu ý rằng $$\frac{\sigma'(x)}{\sigma(x)}=\sum_{i\in B}\frac 1{x-L_i}$$ và rằng nếu chúng ta viết $C$ đối với các vị trí bit của một từ mã, mã Goppa được xác định bởi $$\sum_{i\in C}\frac 1{x-L_i}\equiv 0\pmod{g(x)}$$ để có thể $$\frac{\sigma'(x)}{\sigma(x)}\equiv\sum_{i\in B\ominus C}\frac 1{x-L_i}\pmod{g(x)}$$ và phía bên tay phải chỉ là $s(x)$.

Chúng tôi chia tay $\sigma(x)$ thành các đơn thức bậc lẻ và bậc chẵn để tìm đa thức $\sigma_{odd}$ và$\sigma_{even}$ như vậy mà $$\sigma(x)=x\sigma_{odd}(x^2)+\sigma_{even}(x^2). \qquad (1)$$ Bởi vì chúng ta đang ở trong một trường đặc trưng 2, các đa thức chỉ có các hạng tử bình phương nhiều nhất là bình phương của các đa thức bậc khác $(\deg g-1)/2$ và chúng tôi mong muốn phục hồi $a(x)$ và $b(x)$ thỏa mãn bậc này ràng buộc sao cho $a(x)^2=\sigma_{even}(x^2)$ và $b(x)^2=\sigma_{odd}$.

Phân biệt (1) mang lại $$\sigma'(x)=\sigma_{odd}(x^2)$$ và vì thế $$\frac{\sigma(x)}{\sigma'(x)}=x+\frac{\sigma_{even}(x^2)}{\sigma_{odd}(x^2)}$$ cho chúng ta biết rằng $$\frac1{s(x)}-x\equiv \frac{\sigma_{even}(x^2)}{\sigma_{odd}(x^2)}\pmod{g(x)}.$ $ Như vậy đa thức $v(x)$ tương đương với hàm hữu tỷ $a(x)/b(x)$ mà chúng tôi tìm kiếm modulo $g(x)$. Thuật toán Euclide mở rộng sẽ trả về hai đa thức sao cho $$\frac{c(x)}{d(x)}\equiv v(x)\pmod{g(x)}$$ với $\deg c$ và $\deg d$ cả hai ít hơn $(\deg g)/2$ và các đa thức này phải bằng với tìm kiếm của chúng tôi $a(x)$ và $b(x)$ nếu không thì $a(x)d(x)-b(x)c(x)$ là một đa thức bậc nhỏ hơn $d$ và chia hết cho $g(x)$. đã hồi phục $a(x)$ và $b(x)$ bây giờ chúng ta có thể xây dựng $\sigma(x)=a(x)^2+xb(x)^2$ đó là định nghĩa của $p(x)$ mà thường được đưa ra.