多项式扩展欧几里德算法 [英] polynomial extended euclidean algorithm
问题描述
任何人都知道如何开始编写C代码来生成
有限域GF的倒数（2 ^ 8）使用扩展的欧几里得算法？
我的意思是如何表示多项式，例如C中的f（x）= x ^ 8 + x ^ 4 + x ^ 3 + x + 1
？如何表示乘法&
多项式的划分过程？
问候。
- Tiza -
Hi,
Anybody have an idea on how to start writing a C code for generating
the inverse of finite field GF(2^8) using extended Euclidean algorithm?
What I mean is how to represent a polynomial, e.g. f(x)=x^8+x^4+x^3+x+1
in C? How to represent the multiplication & division process of
polynomial?
Regards.
-- Tiza --
推荐答案
Tiza Naziri写道：
Tiza Naziri wrote:
任何人都知道如何开始写作使用扩展欧几里德算法生成有限域GF（2 ^ 8）的逆的C代码？
我的意思是如何表示多项式，例如C中的f（x）= x ^ 8 + x ^ 4 + x ^ 3 + x + 1
如何表示乘法&多项式的划分过程？
问候。
- Tiza -
Hi,
Anybody have an idea on how to start writing a C code for generating
the inverse of finite field GF(2^8) using extended Euclidean algorithm?
What I mean is how to represent a polynomial, e.g. f(x)=x^8+x^4+x^3+x+1
in C? How to represent the multiplication & division process of
polynomial?
Regards.
-- Tiza --
基本上有两种方式：
1）密集表示：
使用N + 1个位置的向量，其中N是最高学位词。
在这种情况下你会使用9个位置的向量：
1 0 0 0 1 1 0 1 1
在多项式5x ^ 8 + 25x ^ 4 + 567中你会得到：
5 0 0 0 25 0 0 0 567
2）稀疏表示：
使用链表，其中每个术语由一对
数字指数和常数项。这种表示更适用于
多项式，如10x ^ 200 + x + 5：
{200 10} {1 1} {0 5}
jacob
There are basically two ways:
1) Dense representation:
Use a vector of N+1 positions where N is the highest degree term.
In this case you would use a vector of 9 positions:
1 0 0 0 1 1 0 1 1
In a polynomial 5x^8 + 25x^4 + 567 you would have:
5 0 0 0 25 0 0 0 567
2) Sparse representation:
Use a linked list where each term is represented by a pair of
numbers exponent and constant term. This representation is better for
polynomials like 10x^200 + x + 5:
{ 200 10 } {1 1} { 0 5}
jacob
Tiza Naziri写道：
Tiza Naziri wrote:
任何人都知道如何开始编写C代码，使用扩展的欧几里德算法生成有限域GF（2 ^ 8）的逆？
我的意思是如何表示多项式，例如C中的f（x）= x ^ 8 + x ^ 4 + x ^ 3 + x + 1
如何表示乘法&多项式的除法过程？
Hi,
Anybody have an idea on how to start writing a C code for generating
the inverse of finite field GF(2^8) using extended Euclidean algorithm?
What I mean is how to represent a polynomial, e.g. f(x)=x^8+x^4+x^3+x+1
in C? How to represent the multiplication & division process of
polynomial?
让变量中的位代表x的幂，这样，例如，
x ^ 8 + x ^ 4 + x ^ 3 + x + 1由位*，4,3,1和0表示。在这种情况下，我们获得0x11b作为该多项式的重新定义。
现在，如果我们想要添加或减去两个这样的值，我们所要做的就是
将它们放在一起，以便例如：
''x + 1''+''x ^ 2 + x''==> 0x003 xor 0x006 = 0x005 ==> x ^ 2 + 1.
乘以x是一个位置左移。最后，如果在操作后设置位
8，我们必须将（xor）0x11b减去
结果（假设0x11b是我们的模式多项式）。分区可以
然后通过重复减法来表示。
如果我们想要将GF（2 ^ 8）元素T除以元素B，我们向左移动B
变量，直到它的最高位与T的最高位匹配。然后我们将
结果变为T，这样T的最高位变为零。现在我们可以再次重复
这个T的新值，直到T比B的位数少。
得到的T值是除法的余数，而商
是1位代表我们在这个过程中从T
中拿走的B的倍数
美国FIPS文件对于AES加密算法，请在
中详细说明。
Brian Gladman
Let the bits in a variable represent powers of x so that, for example,
x^8+x^4+x^3+x+1 is represented by bits *, 4, 3, 1 and 0. In this case
we obtain 0x11b as the represntation of this polynomial.
Now if we want to add or subtract two such values, all we have to do is
to xor them together so that, for example:
''x + 1'' + ''x^2 + x'' ==> 0x003 xor 0x006 = 0x005 ==> x^2 + 1.
And multiplication by x is a shift left by one position. Finally if bit
8 is set after an operation we have to subtract (xor) 0x11b into the
result (assuming that 0x11b is our modular polynomial). Division can
then be represented by repeated subtraction.
If we want to divide GF(2^8) element T by element B, we shift left the B
variable until its top bit matches the top bit of T. We then xor the
result into T so that the top bit of T becomes zero. Now we can repeat
this again for the new value of T until T has fewer bits than B. The
resulting T value is the remainder of the division, while the quotient
is the 1 bits representing the multiples of B that we take away from T
in this process
The US FIPS document for the AES encryption algorithm explains this in
more detail.
Brian Gladman
BRG写道：
让变量中的位代表x的幂，以便例如表示
x ^ 8 + x ^ 4 + x ^ 3 + x + 1比特*，4,3,1和0.在这种情况下，我们获得0x11b作为该多项式的重新定位。
Let the bits in a variable represent powers of x so that, for example,
x^8+x^4+x^3+x+1 is represented by bits *, 4, 3, 1 and 0. In this case
we obtain 0x11b as the represntation of this polynomial.
是否可以表示
45x ^ 8 + 1769x ^ 3 + 7.976x + 3.14159
使用该表示形式？
也许有可能限制
多项式的域但是那不是规格，至少在
规格中，比如我理解它们......
jacob
Is it possible to represent
45x^8 + 1769x^3 + 7.976x + 3.14159
using that representation?
Maybe it is possible to restrain the domain of the
polynomial but that wasn''t in the specs, at least in
the specs such as I understood them...
jacob
这篇关于多项式扩展欧几里德算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
