C代数在有限主素场中的片段
我需要在16位CPU上求解有限素数域中的多项式。 我看到有人使用GF((2^16)+1), GF((2^16)-15)和GF((2^32)-5) 。 我想这些选择源于有几个优化的事实。 但是，除了使用“mod”之外，我不知道还有哪些优化。 如果有人给我指出一个好的资源，给我代码片段，或者解释为什么人们使用那些奇怪的素数而不是GF((2^16)-1)我会非常感激。
编辑：GF（％（2 ^ 16）+1）中的％模免模：
uint32_t mod_0x10001(uint32_t divident)
{
uint16_t least;
uint16_t most;
least = divident & 0xFFFF;
most = divident >> 16;
if (least >= most) {
return least - most;
} else {
return 0x10001 + least - most;
}
}
编辑：无GF％（2 ^ 16-15）模％：
uint32_t mod_0xFFF1(uint32_t divident)
{
uint16_t least;
uint16_t most;
uint32_t remainder;
least = divident & 0xFFFF;
most = divident >> 16;
/**
* divident mod 2^16-15
* = (most * 2^N + least) mod 2^16-15
* = [(most * 2^N mod 2^16-15) + (least mod 2^16-15)] mod 2^16-15
* = [ 15 * most + least ] mod 2^16-15
*/
remainder = 15 * most + least;
while (remainder >= 0xFFF1) {
remainder -= 0xFFF1;
}
return remainder;
}
更新：我测量了MSP430的执行速度：较高版本比较低版本快4倍。 较低版本与使用％：/一样快。 任何进一步的建议，以加快低版本？
干杯康拉德
使用幂2 ^ N - m（其中很小）的原因是由于计算格式（HI * 2 ^ N + LO）mod 2 ^ Nm的单词的模可以被分成两个（或更多件），减少到
(HI*2^N+LO) mod (2^N-m) ==
((HI*2^N) mod (2^N-m) + LO mod (2^N-m)) mod (2^N-m)
(m * HI + LO ) mod (2^N-m).
m * HI + LO的值至多log2（m）位多于计算机字的值 - log2（m）位值可以通过反复乘以m并累加而再次折回到总和。 通常一次迭代就足够了。
如果m很小，m ^ 2或m ^ 3也可以合理地小 - 那么可以应用该技术来计算大数的模数：
[AAAAA | BBBBB | CCCCC | DDDDD | EEEEE ] mod (2^N-m) ==
EEEEE * 1 mod (2^N-m) +
DDDDD * m mod (2^N-m) +
CCCCC * (m^2) mod (2^N-m) + ... etc.
在基地10，在那里是一样的
1234 5678 9812 mod 9997 ==
9812 mod 9997 +
3*5678 mod 9997 +
9*1234 mod 9997 ==
3 7952 mod 9997 == ( 7952 + 3*3 ) mod 9997 = 7961
Here 9997 doesn't have to prime, we are using 10^4 instead of 2^N and m = 3
对于GF（2 ^ n）计算，典型的加速是root ^ n和log（n）的查找表; 然后乘法减少到加法。 如果目标系统不是一些16位系统，我会建议使用SSE4.2（或氖）多项式（免提）乘法。 如果我没有大错特错，GF中的多项式计算应该可以通过卷积来实现：
for (i=0;i<N*2-1;i++) temp[i]=popcount(A & (bit_reverse(B)<<N)>>i);
// A = 11010, B=01101, reverse B = 10110
//
// 11010 11010 11010 11010 11010 11010 11010 11010 11010
// 10110 10110 10110 10110 10110 10110 10110 10110 10110
// 0000000000 00010000 0000000 010100 10010 001000 0011000 00010000 000000000
// 0 1 0 0 0 1 0 1 0
// 010001010 to be divided by the generator polynomial using typical CRC approach
GF（2 ^ n）乘法比较的进一步阅读：
（Serdar S. Erdem，TuğrulYanık，ÇetinK.Koç，
Acta Applicandae Mathematica 2006年9月，第93卷，第1-3期，第33-55页）
除了丹尼尔的回答之外：有限域只能拥有许多元素的主要力量。 但是，你想要有许多元素，因为它们与计算模p同构（这很快！）。 尽管有限域P（r> 1）中的许多元素决不会同构于Z / p ^ r Z（即计算模p ^ r）。
编辑：如果你想在GF（p ^ r）中实现计算，你可以在r（GF）（x）中选择一个不可约多项式p（x），并在GF（p）[x] /（p （x））即你计算mod p（x）（所以你必须实现多项式除法）。 您可以在计算机代数系统（如Singular或Macaulay 2）中使用这些东西
链接地址: http://www.djcxy.com/p/62985.html