A. *_*ebb 13
动机
这里的二进制系数意味着系数在字段Z_2中是模2,或者仅取值0和1并且像位一样操作.这并不意味着系数是基数为2的任意整数.它们是二进制的(取两个值),而不是简单地用二进制数字表示.
牢记这一点,这个问题很容易回答,是的,XOR和(左)移位的按位运算就足够了.虽然不需要回答这个问题,但这个问题是由加密技术推动的.它演示了散列中常用的一些按位运算与一些加密方案和抽象代数之间的联系,因此可以在密码分析中利用有限域上多项式的结果.将产品模数为另一个多项式是为了防止结果的程度超过一定限度.机器寄存器上的操作自然地作为溢出执行.
加成
首先让我们谈谈补充.作为系数模2,加入x + x = 2x = 0x = 0自2 mod 2 = 0.因此,只要有两个相同的术语,它们就会取消,而当只有一个术语时,它会持续存在.这与行为相同XOR.例如,添加(x^4 + x^2 + 1) + (x^3 + x^2):
(1x^4+0x^3+1x^2+0x^1+1x^0)+(0x^4+1x^3+1x^2+0x^1+0x^0) = (1x^4+1x^3+0x^2+0x^1+1x^0)
或者,仅使用紧凑系数表示法,
10101 XOR 01100 = 11001
乘法
乘法通过x将每个项的幂增加一.在紧凑符号中,这相当于左按位移位.
(1x^4+0x^3+1x^2+0x^1+1x^0) * x = (1x^5+0x^4+1x^3+0x^2+1x^1+0x^0)
10101 << 1 = 101010
因此,为了乘以多项式,f(x) * g(x)我们可以分别乘以f(x)每个项,每个项g(x)等于一个移位,然后加上,加法相当于XOR.让我们相乘(x^4 + x^2 + 1) * (x^3 + x^2)
(x^4 + x^2 + 1) * (x^3 + x^2) = (x^4 + x^2 + 1)*x^3 + (x^4 + x^2 + 1) *x^2
(10101 << 3) XOR (10101 << 2) = 10101000 XOR 01010100 = 11111100
所以,答案是x^7 + x^6 + x^5 + x^4 + x^3 + x^2.
模数减少
减少模数h(x)也相当容易.它的确不要求你记住怎么做长除法.像乘法一样,我们将逐项完成.让我们继续使用相同的示例,并将其模数化h(x) = x^5 + x
(x^7 + ... + x^2) mod (x^5+x) = [x^7 mod (x^5+x)] + ... + [x^2 mod (x^5+x)]
现在,如果程度n的x^n比小h(x),在这里5,那么有什么可以做,因为h(x)不会分裂x^n.
[x^2 mod (x^5+x)] = x^2 or 00000100
[x^3 mod (x^5+x)] = x^3 or 00001000
[x^4 mod (x^5+x)] = x^4 or 00010000
然后当度是平等的,我们可以说,h(x)分裂x^n一次,我们通过的其余条款下颚h(x).我们已经超越而不是低调,这几乎不重要,此后的余额也没有-1 mod 2 = 1.这里,
x^5 = (x^5 + x) – x, so
[x^5 mod (x^5+x)] = x, or 00000010
通常,[x ^ n mod h(x)] = [h(x)-x ^ n]时n = degree(h).在紧凑的形式,这等同于关闭n个比特,其可以通过异或的表示来完成h(x)与的表示x^n:
00100010 XOR 00100000 = 00000010.
当x^n有一个度大于h(x)我们可以成倍h(x)通过x^k让度的匹配,并进行如在现有的情况下.
x ^ 6 =(x ^ 5 + x)*x - (x)*x = -x ^ 2,所以[x ^ 6 mod(x ^ 5 + x)] = x ^ 2,或00000100,或紧凑形式(00100010 << 1)异或(00100000 << 1)= 00000100
但是,更有效率,只需改变之前的答案,我们将为此做的x^7:
[x^7 mod (x^5+x)] = x^3, or 00001000
所以要收集,我们需要添加这些结果,这是在紧凑表示中的异或.
x^2 + x^3 + x^4 + x + x^2 + x^3 = x^4 + 2x^3 + 2x^2 + x = x^4 + x, or
00000100 XOR 00001000 XOR 00010000 XOR 00000010 XOR 00000100 XOR 00001000 = 00010010
结束语
我们可以要求Wolfram Alpha通过长期划分为我们验证这一结果.给出的余数是x^4 - x,等于x^4 + x系数为2的模数.
x对于更有效的算法,可以组合逐项乘法和模数步骤,例如乘以产品的模数,如果产品的程度至少是,则该算法将是一个移位和异或h(x).然后重复结果,乘以x产品并对其求模,并记录该乘法的答案x^2.等等...
这是一道知识题。基本上，除非你像高斯一样聪明，或者你已经了解同余数学，也称为“模算术”，否则你就完蛋了。为了了解这些内容，您可能想阅读一本书：Allenby 的《数论与计算导论》。
最终的关键知识是，同余可以通过多种方法计算，其中最好的是相当古老的“平方乘法”方法。基本上，每当你有一个二进制 1 时，你都会平方和倍数，但当你有一个 0 时，你只是平方。完整的算法和解释位于第 14 页。79 艾伦比。
另一种方法是使用中国余数定理，这可能就是提问者的目的。
你在哪里申请？美国国家安全局？洛斯阿拉莫斯？这是一个非常棘手的问题。
太棒了，因为是唯一真正回答问题的人而被否决。这里要明确一点：毫无疑问，面试官期望利用平方和乘法算法，正如我上面所说的。平方和乘法在 RSA/密码算法内部使用来执行快速模运算。参见第 17 页。225 有关该算法和 RSA 应用的描述：RSA State 的多项式标准积的实现。面试官可能曾研究过 RSA，这就是他知道该方法的原因。