异或和循环移位

Question

假设我们有这个方程 c = m ⊕ (m << 6) ⊕ (m << 10) where ⊕ stands for XOR and << for cyclic shift to the left. How can this be written as m in terms of c? What operations must be used?

我尝试用 c 对双方进行异或运算<< 6 but didnt result in an equation that has only m

Answer 1

假设

c

和

m

的 16 位，我从一个包含 16 个方程的系统开始：

m0 = c0 + m6+m10
m1 = c1 + m7+m11
m2 = c2 + m8+m12
m3 = c3 + m9+m13
m4 = c4 + m10+m14
m5 = c5 + m11+m15
m6 = c6 + m0+m12
m7 = c7 + m1+m13
m8 = c8 + m2+m14
m9 = c9 + m3+m15
m10 = c10 + m0+m4
m11 = c11 + m1+m5
m12 = c12 + m2+m6
m13 = c13 + m3+m7
m14 = c14 + m4+m8
m15 = c15 + m5+m9

通过变量消除/替换的迭代循环，我最终得到以下结果（

+

代表

xor

）：

m0 = c0+c2+c4+c12+c14
m1 = c1+c3+c5+c13+c15
m2 = c0+c2+c4+c6+c14
m3 = c1+c3+c5+c7+c15
m4 = c0+c2+c4+c6+c8
m5 = c1+c3+c5+c7+c9
m6 = c2+c4+c6+c8+c10
m7 = c3+c5+c7+c9+c11
m8 = c4+c6+c8+c10+c12
m9 = c5+c7+c9+c11+c13
m10 = c6+c8+c10+c12+c14
m11 = c7+c9+c11+c13+c15
m12 = c0+c8+c10+c12+c14
m13 = c1+c9+c11+c13+c15
m14 = c0+c2+c10+c12+c14
m15 = c1+c3+c11+c13+c15

在单词级别，这可以写成

m = c ⊕ (c << 2) ⊕ (c << 4) ⊕ (c << 12) ⊕ (c << 14)

我想知道，这种词级形式是如何不解方程组而直接推导出来的

位级方程是模 2 (GF2) 方程组。这可以使用 Gauss Jordan elimination.

来解决

---

我的 C# 代码：

    class Program
    {
        const int Bits = 16;

        //  several loops make use of this Range
        static readonly IEnumerable<int> BitIndices = Enumerable.Range(0, Bits);

        //  Class represents an xor sum of c and m elements
        class CMXorSumExpression
        {
            int no;
            bool[] c = new bool[Bits];
            bool[] m = new bool[Bits];

            public CMXorSumExpression(int ic) 
            {
                no = ic;
                c[ic] = true; //  the c bit ic
                m[(Bits - 6 + ic) % Bits] = true;  //  the m << 6 bit 
                m[(Bits - 10 + ic) % Bits] = true;  //  the m << 10 bit
            }

            // Replace m_i element in expression by expression r
            public void Replace(int i, CMXorSumExpression r)
            {
                if ((i != no) && m[i])
                //  m_i is set => replace it
                {
                    m[i] = false;
                    c = BitIndices.Select(x => c[x] ^ r.c[x]).ToArray();
                    m = BitIndices.Select(x => m[x] ^ r.m[x]).ToArray();
                }
            }

            public override string ToString()
            {
                return $"m{no} = "
                     + string.Join("",
                         BitIndices.Select(x => c[x] ? $"+c{x}" : ""))[1..] 
                     + " " 
                     + string.Join("", 
                         BitIndices.Select(x => m[x] ? $"+m{x}" : ""));
            }
        }

        static void Main()
        {
            //  array of bit-level equations
            CMXorSumExpression[] cmSumExpressions = 
                BitIndices.Select(x => new CMXorSumExpression(x)).ToArray();

            //  show equations
            foreach(var e in cmSumExpressions)
            {
                O($"{e}");
            }

            //  replace operands to eliminate m elements on the right-hand-side
            bool changed;
            int round = 0;
            do
            {
                changed = false;

                O();
                O($"round {++round}");
                foreach (int i in BitIndices)
                    foreach (int j in BitIndices)
                    {
                        string sBefore = cmSumExpressions[j].ToString();
                        cmSumExpressions[j].Replace(i, cmSumExpressions[i]);
                        string sAfter = cmSumExpressions[j].ToString();

                        if (sBefore != sAfter)
                        {
                            O($"before i={i} j={j} cm[j]: {sBefore}");
                            O($"after  i={i} j={j} cm[j]: {sAfter}");
                            O();
                            changed = true;
                        }
                    }
            } while (changed);

            //  show resulting equations
            foreach (var e in cmSumExpressions)
            {
                O($"{e}");
            }

            O("ciao!");
        }

        private static void O(string s = "")
        {
            Console.WriteLine(s);
        }
    }