math - bitxor，求解方程，布尔逻辑

Question

我有等式：

C = A^b + (2*A)^b + (4*A)^b.  

其中 C 和 A 已知，但 b 未知。如何找到b？所有数字都是 8 位字节。有没有比蛮力更快的方法？

Answer 1

+ 符号是否表示字节加法和 * 乘法，溢出位被丢弃？如果是这样，我认为答案是

b = C ^ (A + 2 * A + 4* A)

如何得出这个结论：

C = A^b + (2*A)^b + (4*A)^b

因此

C^b = A^b^b + (2*A)^b^b + (4*A)^b^b = A + 2*A + 4*A

然后

C^C^b = b = C^(A + 2*A + 4*A)

编辑只是为了确保：这个答案不正确。真丢人。我将不得不考虑更多。

Answer 2

我采用相同的假设：+并且*忽略了溢出的加法和乘法。

查找表

这可能是最快的解决方案：预先计算结果，并将它们存储在查找表中。它需要 2^{个 16}字节的内存，即 64 kB。

猜测、检查、改进方法

以类似 C 系列的伪代码呈现：

byte Solve(byte a, byte c){
    byte guess = lastGuess = result = lastResult = 0;

    do {
        guess = lastGuess ^ lastResult ^ c;            //see explanation below
        result = a^guess + (2*a)^guess + (4*a)^guess; 
        lastGuess = guess;
        lastResult = result;
    } while (result != c);

    return guess;
}

这个算法的想法是，它猜测是什么b，然后将其代入公式以获得暂定结果，并与c. 猜测中导致结果不同的任何位都会c被更改。这对应于最后一个猜测、最后一个结果和c（如果这个陈述有点跳跃，我鼓励你画一个真值表，而不是只信我的话！）。

解释

它之所以有效，是因为更改一个位只能影响该位的结果，以及更重要的位，但不会影响较低的位（因为当您用笔和纸进行加法时，进位可以传播到左侧）。因此，在最坏的情况下，算法需要 2 次猜测才能使最低有效位正确，第 2 个 lsb 的另一个猜测，第 3 个的另一个猜测，等等。给定 和 的任意组合，最多9 个猜测。ac

这是我的测试程序的示例跟踪：

a: 00001100
c: 01100111

Guess:  01100111
Result: 01000001
Guess:  01000001
Result: 00010111
Guess:  00110001
Result: 01100111

b: 00110001