0%

# 一、拓展欧拉算法（Extended Euclidean Algorithm）

## 1. 欧拉算法（Euclidean Algorithm）

Fact 1: gcd(a,0) = a Fact 2: gcd(a,b) = gcd(b,r), where r is the remainder of dividing a by b

gcd(36,10) = gcd(10,6) = gcd(6,4) = gcd(4,2) = gcd(2,0) = 2

sa+tb = gcd(a,b)

# 二、$$GF(2^n)$$的多项式乘法（Multiplication of Polynomials in $$GF(2^n)$$）

## 1. $$GF(2^n)$$

Algebraic Structure Supported Typical Operations Supported Typical Sets of Integers
Group (+ -) or ($$\times \div$$) $$Z\_n or Z{\_n}{^*}$$
Ring (+ -) and ($$\times$$) $$Z$$
Field (+ -) and ($$\times \div$$) $$Z\_p$$

A Galois field, $$GF(p^n$$), is a finite field with $$p^n$$ elements.

## 2. 多项式乘法

$f(x) = a\_{n-1}x^{n-1} + a\_{n-2}x^{n-2} + \cdots + a\_{1}x^{1} + a\_{0}x^{0}$

1. 乘除法：在乘法中，可以先利用我们代数中的多项式乘法。显然，积中的项可能有大于n-1的，不同于加减法中的项都是限定在了n-1内。因此，对于这些项，我们需要用我们上面说的质数多项式进行取模，使得其余数落于n-1的最高指数项内。

q r1 r2 r t1 t2 t
$$(x^2+1)$$ $$(x^4+x+1)$$ $$(x^2+1)$$ $$x$$ $$(0)$$ $$(1)$$ $$(x^2+1)$$
$$x$$ $$(x^2+1)$$ $$x$$ $$(1)$$ $$(1)$$ $$(x^2+1)$$ $$(x^3+x+1)$$
$$x$$ $$x$$ $$(1)$$ $$(0)$$ $$(x^2+1)$$ $$(x^3+x+1)$$ $$(0)$$
$$(1)$$ $$(0)$$ $$(x^3+x+1)$$ $$(0)$$