 Pure Mathematics 理论数学, 2011, 1, 189-197 http://dx.doi.org/10.12677/pm.2011.13037 Published Online October 2011 (http://www.hanspub.org/journal/pm/) Copyright © 2011 Hanspub PM A Sort of New Solution for the Conjecture of Binary Matrix Equation Qingcan Xiao, Zhilian Zeng School of Mathematics and Information Science, Guangzhou University, Guangzhou Email: qcxiao@21cn.com; zhilianzeng@gmail.com Received: Jul. 13th, 2011; revised: Aug. 20th, 2011; accepted: Aug. 21st, 2011. Abstract: In this paper, we give four general solutions satisfying the requirement of the conjecture for binary matrix equation |E – 2A| = q. Many distinct solutions can be derived from the base solution, and the lower bound of the number of solutions can be determined, given the integer q. Furthermore, we study the properties of these base solutions, and find most of the solutions. We extend the result of François Arnault’s paper [1], and solve the conjecture proposed by François Arnault proposed in [2]. Keywords: 2-adic Ring; FCSRs; -Sequences; Determinant 关于二进制矩阵方程猜想的一类新解 肖卿灿，曾志廉 广州大学数学与信息科学学院，广州 Email: qcxiao@21cn.com; zhilianzeng@gmail.com 收稿日期：2011年7月13日；修回日期：2011年8月20日；录用日期：2011 年8月21日 摘 要：本文给出了二进制矩阵方程|E – 2A| = q 满足猜想要求的四个通解，由此基础解衍生出不同的 解，根据具体的 q就能确定出不同的解个数的下限，在此基础上进一步研究解的性质，进而求出大部 分的解。我们的结论推广了François Arnault等人在文[1]的结果，解决了François Arnault在文[2]中提 出的猜想问题。 关键词：2-adic 环；FCSRs；序列；行列式 1. 引言 关于代数攻击和具有移位寄存器的反馈(FCSRs)问题很多人进行了研究，如 François Arnault及Thierry P. Berger [3]等人，在密码学和伪随机序列产生时使用，设计者不希望攻击者容易猜测到寄存器的内容，这要求内部 状态有高熵。密码学中的矩阵方法是近两年来时兴的研究方法，为了增加破解难度，François Arnault通过构造 每行或每列至多有两个元素不为零的二进制矩阵 A加以解决，他们构造了具有 FCSRs 的两个转移矩阵如下(其 中A是|E–2A| = q 的解，q为负奇数，h = [log2(–q)]，n = h + 1 或h，A的元素 {–1,0,1})： 0 2 3 1 1 132 01 1 0(0) 01 (0) 1 01 (0)0 1 01 (0)0 1 1 10 GFn n n r r r r rrr AA 0 r  肖卿灿 等关于二进制矩阵方程猜想的一类新解 190 | 1 0 2 22 2 nj j j Enrd A， 1 2 0 11 2 q r ， 1 2 01q d François Arnault在文[2]中猜测对于任意的负奇数 q存在着在 或 0 G A0 F A基础上每行或每列至多只添加进一 个非零元素的情况，使得在每行或每列至多有两个元素不为零的情况下，转移矩阵A满足|E – 2A| = q。 0 00 0 01 1 01 (0) 00 1(0) 01 001 (0) 01 0(0) 01 100 0 10 GF r r AA (1) 本文给出了完整的存在性证明，在A ≠或 0 G A0 F A时，对于给定的q，至少有四个 A同时满足|E – 2A| = q， 并给出 A的四个通项公式。 下面先回顾一下行列式的定义，假设 11 121 21 222 12 n n nn nn aa a aa a aa a D 是由排成 n阶方阵形式的 个数确定的一个数，其值为 项之和 2 n ,1,2,, ij aij n !n 12 12 1n n aa a D式 中12 n ,, ,是将序列1,2, 的元素次序交换,n 次所得到的一个序列， 号表示对 12 n ,, ,,n取遍1,2, 的 一切排列求和，那么数 D称为n阶方阵相应的行列式。 2. 引理及定理证明 引理 1 设x为正整数，令h = [log2(x)]，则对于任意一个正整数x均可化成两两不相邻的2i的幂级数形式， 其系数 ，其项数 1 1, 0,1h C 21n。 证明 当x为正偶数时，令 00 2i x k，(2,k0) = 1,若k0 = 1，则命题成立；若k0 > 1，不失一般性，只须证明x 为正奇数的情形。由于对于任意的正奇数x均可表成 4k ± 1 的形式，取c0 = ±1，则 x = 4k + c0 + c0，(2, k1) = 1,若k1 = 1，则命题成立；若k1 > 1，则k1同样可表成 4k2 ± 1的形式，即 k1 = 4k2 ± 1，同样取c1 = ±1，则 k1 = 4k2 ± 1 + c1，(2,k3) = 1此时 1 2 1 2ik 2 2 3 2ik 112 242 010 31 422 2 iii 1 i 0 x kck ckcc 若k3 = 1，则命题成立；若k3 > 1，则 k3 = 4k4 ± 1，同样地取c2 = ± 1，则 3 2 35 2i kk 2 c ，(2, k5) = 1，此时 123 12 1 642 52 1 222 ii iii i 0 x kcc c e i 若k5 = 1，则命题成立；若k5 > 1，则这个过程不断地继续下去，经过有限次之后，最后总存在正整数s使 得ks = 1。令 ，则 1 t t e j 2 0 2l mlj l l xc (2) 其中， ， 00j1c2nmj m m ，由构造性证明过程易知其系数不为零的项数 11 22 m nj n m1 证毕。 一般情况下，当2h + 2h–2 < x < 2h+1 时，取次数n = h + 1，当2h < x < 2h + 2h–2，取次数 n = h。参考文献[1]和 [2]的方法我们容易证明引理2。 引理 2 设q为负奇数， 1q 2 0 11 2 r ， 1q 2 01d ，yi为实数，1in，令 Copyright © 2011 Hanspub PM  肖卿灿 等关于二进制矩阵方程猜想的一类新解191 | 1 0 132 2 12 (0) 12 Â (0)1 2 nn d yyyy y ，则 1 11 0 1 Â2 2 n ni ni i ydy (3) 定理 1 设q为负奇数， 1 2 0 11 2 q r ， 1 2 01q d ，取 h = [log2(–q)]，令n = h + 1或h，构造 n阶方阵 A：首 先an,1 = 1，ai,i + 1 = 1，i = 1,,n–1，在此基础上添加元素，方阵 添加 a1,1 = ，方 阵 0 G A0 r0 F A添加 an,n = ， AG和AF的具体构造如下： 0 r 1) 方阵 AG的构造 在基础上添加 an – j,1 + j = rn – 2j, an – j – 1,1 + j = rn – 2j – 1，第 0 G A3 2 n 行第 1 2 n 列中的元素为r3，第 2 2 n 行 第2 n 0 0 2 32 43 4 5 34 34 2 2 11 01 01 0 101 01 01 01 01 01 01 01 001 100 001 10 10 G n nn nn n n rr r rr rr r rrr rr r r 或A 列中的元素为r2，其余都为零。 (4) 1 n为偶数 n为奇数 另外 AG还有第二种构造方法：在基础上添加 an – j,1 + j = rn – 2j，an – j, 2 + j = rn – 2j – 1，第 0 G A5 2 n 行第 +1 2 n 列 中的元素为r3，第 4 2 n 行第 2 2 n 列中的元素为r2，其余都为零。 0 0 2 32 43 34 34 2 2 1 101 01 01 01 01 01 01 01 01 01 01 01 01 100 10 0 G nn nn n n r r r rr rr rr rr rr 或A (5) n为偶数 n为奇数 Copyright © 2011 Hanspub PM  肖卿灿 等关于二进制矩阵方程猜想的一类新解 192 | 2) 对于 AF而言，构造如下：在 0 F A基础上添加 an – j – 2, j = rn – 2j，an – j – 3,j = rn – 2j – 1，第 1 2 n 行第 3 2 n 列 中的元素为r3，第2 n 行第 2 2 n 列中的元素为r2，其余都为零(详见(6)式)。 2 32 43 4 5 34 34 2 2 0 0 01 01 01 01 0 101 01 01 01 01 01 01 01 001 100 001 1 1 F n nn nn n n r rr rr r rrr rr r r r r 或A 1 1 (6) n为偶数 n为奇数 2 32 43 4 5 34 34 2 2 0 0 01 01 01 01 0 101 01 01 01 01 01 01 01 001 100 001 1 1 F n nn nn n n r rr rr r rrr rr r rr r 或A (7) n为偶数 n为奇数 另外 AF还有第二种构造方法：在 0 F A基础上添加 an – j – 2, j = rn – 2j，an – j – 2, j + 1 = rn – 2j – 1，第 3 2 n 行第 1 2 n 列中的元素为r3，第 2 2 n 行第 2 n 列中的元素为r2，其余都为零(详见(7)式)。 则对于以上八个行列式皆有 23 332 02333 2 2222222 nnn n nn n Edrrrrr 0 d A (8) 证明 我们先对(4)式的第一式计算|E – 2A| Copyright © 2011 Hanspub PM  肖卿灿 等关于二进制矩阵方程猜想的一类新解193 | 0 32 4 5 34 2 2 12 1 2 12 12 2221 2 212 2 221 2 21 2 1 G n nn n d Err r r rr r A 2 (9) 第n行乘以 2加到第n – 1 行，第 n – 1 行乘以 2加到第n – 2 行，，第 2 n 乘以2加到第 +2 2 n 行，取υ = +2 2 n ，这样第υ + 1列至第 n列除主对角线上的元素为 1外，其余均为 0。(υ,υ)位置上的元素为1，则第υ 行变为 -2 3 2345432 2222222210 0 nn nn rrrr LrrrL 由(1,1) - (υ,υ)位置所组成的行列式为引理 2中(3)式的形式，把 yn = –2υ，yn – 1 = –2υ – 2(2rn – 2 + rn – 3)，，y3 = –2(2r4 + r3)，y2 = –2r2，y1 = 1 代入(3)式结合引理 2可得 ––2 12 –23043 020 23 n332 0233320 22222222 222 222222 nn Gnn nnn nn n Errdrrd drrrr rd Ard 方法二：令Γ = E–2 A，当|Γ| = 2n ± 1 时，命题显然成立，不失一般性，不妨设rj不全为零(j = 2,,n – 2)，Γ 在(n,1)位置上的代数余子式为(–1)n + 1((–2)n – 1) = 2n – 1，在(n,n)位置上的代数余子式为(–1)n + nβ1 = β1，利用拉普拉 斯展开定理我们有 |Γ| = –2·2n – 1 + β1= –2n + β1 对于 n – 1阶行列式 β1在(n – 1,2)位置上的余子式为主对角线上除第一个元素为 d0外其余元素均为–2 的下三 角形，其代数余子式为(–1)n – 1 + 2((–2)n – 2– 1d0) = 2n – 3d0，在(n – 1,n – 1)位置上的代数余子式为β2，同样用拉普拉 斯展开定理我们有 β1 = –2rn – 2(2n – 3d0) + β2 = –d0rn – 22n – 2 + β2 若rn – 2 ≠ 0，其余的均为零，则有β2 = d0，否则β2在(n – 2,2)位置上的余子式为主对角线上除第一个元素为 d0外其余元素均为–2 的下三角形，其代数余子式为(–1)n – 2 + 2((–2)n – 3 – 1d0) = 2n – 4d0；β2在(n – 2,3)位置上的余子 式为主对角线上除第一个元素为d0和第二个元素为 1外其余元素均为–2 的下三角形，其代数余子式为 (–1)n– 2 + 3((–2)n – 3 – 2d0) = 2n – 5d0，在(n – 2,n – 2)位置上的代数余子式为β3，同样用拉普拉斯展开定理我们有 β2 = –2rn – 3(2n – 4d0) – 2rn – 4(2n – 5d0) + β3 = –d0rn – 32n – 3– d0rn – 42n – 4 + β3 若其余的均为零，则有β3 = d0，否则这个过程不断地继续下去，经过有限次之后(此种情形存在正整数s ≤ INT(n/2)使得 βs = d0)，最后有 |E – 2A| = |Γ| = –2n – d0(rn – 22n – 2 + rn – 32n – 3++rn – 32n – 3 + r323 + r222) + d0 计算其余七个|E – 2A|可得出同样的结论。 Copyright © 2011 Hanspub PM  肖卿灿 等关于二进制矩阵方程猜想的一类新解 194 | 当r0 = 0时d0 = 1，此时上面四种情形的矩阵A有两种是相同的，为此我们必须再构造一种情形，在 0 G A 基础上添加 ai,n – i = r2i + 1, ai,n – i + 1 = r2i，第 3 2 n 行第 4 2 n 列中的元素为 1 21 2 n r ，第 2 2 n 行第 5 2 n 列中 的元素为 2 22 n r ，至此我们完成A1的构造。 32 32 54 4 3 23 2 1 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 10 10 n nn n rr rr rr r rrr r 或A (10) n为偶数 n为奇数 定理 2 设A1为形如(10)式的n阶方阵，ri {–1,0,1}，i = 2,,n – 2，则 |E – 2A1| = –2 n–rn – 22n – 2– rn – 32n – 3 ––r323 – r222 + 1 证明 我们先考察 n – 1 阶行列式 ： 32 32 4 4 4 3 23 2 22 222 12 2 122 12 12 222 22 12 12 12 12 12 12 12 1211 n n nn n rr rr r rr rrr r 2 2 或 根据拉普拉斯行列式展开定理， 按第一行展开后有 = (–1)1 + 1(–2)α1 + (–1) 1 + n – 2 (–2r3)(–2) + (–1)1 + n – 1 (–2r2) = –2α1 + (–1)n + 1r322 + 2(–1)n + 1r2 同样对 α1根据拉普拉斯行列式展开定理，按第一行展开后有 α1 = (–2)α2 + (–1)1 + n – 4(–2r5)(–2)2 + (–1)1 + n – 3(–2r2)(–2) = –2α2 + (–1)nr523 + (–1)nr422 此时 = α2(–2)2 + (–1)n + 1r524 + (–1)n + 1r423 + (–1)n + 1r322 + 2(–1)n + 1r2 仿前可证， = (–2)n – 1 + (–1)n + 1(rn – 22n – 3 + rn – 32n – 4 ++r322 + 2r2) 此时|E – 2A1|根据拉普拉斯行列式展开定理按第 n行展开后有 |E – 2A1|=(–1)n + 1(–2) + 1 = –2n – rn – 22n – 2 – rn – 32n – 3––r323 – r222 + 1 Copyright © 2011 Hanspub PM  肖卿灿 等关于二进制矩阵方程猜想的一类新解195 | d 仍然为定理 1的形式。 3. 结论 首先把负奇数 q化成如下形式 2 0 2 22 n nj j j qb (11) 1, 0,1 j b ，取 1 2 1q j r 0 j j bdb， 2,,2jn 则前面所构造的方阵A都是|E – 2A| = q的解，根据引理1，q可化成 12 0 1 22 l mlj n l l qc d0 l i，，1lm ， 1 t te e ji ，1 2m nmj i m (12) 在此种情况下，bj不为零的项两两不相邻，故利用rj = d0bj可知rj不为零的项也两两不相邻。这样我们就证 明了对于任意一个负奇数 q，取 h = [log2(–q)]，令 n = h + 1 或h，则存在着每行和每列至多有两个元素不为零的 n阶方阵 A满足|E – 2A| = q。 结合定理 1和合定理 2我们可得出更强的结论： 对于任意一个负奇数 q，取h = [log2(–q)]，令 n = h + 1 或h，n的值可由–q表成(2)的形式唯一确定，当m ≥ 1，n > 8 时至少存在着 4个每行和每列至多有两个元素不为零的 n阶方阵 A满足|E – 2A| = q。 4. 讨论及推广 其实当 m = 1，n = 4 时，我们已经找到 4个不同的解A，所以可把条件放宽至 m ≥ 1，n ≥ 4。当中间项即有 奇数项又有偶数项时，(4)式和(7)式以副对角线作对称移动rj，|A – 2E|值不变。 我们在 基础上进一步考察在由(n,1) - (u + 1,u)位置所形成的矩形框内添加元素ai,j(其中 an,1 = 1，1 ≤ j ≤ u, u,1 ≤ i ≤ n)的情形(对于 0 G A 0 F A的情形可类似处理)。令 υ = n – u，Γ = E – 2A 2 1 0 21 23 2 21 321 21 1 1 1222 2 21 1 H 221 E 22 2 BH P E B 12 2 2221 12 22221 1 u u u d Q ，，， 2 (13) 则有|P| = |Q| = 1，|E – 2A| = |Γ| = |P|·|Γ| = |PΓ| = |PΓ|·|Q| = |PΓQ|，先对Γ施行左乘P运算，运算后得到 PΓ的第 u + 2列至第 n列元素除主对角线元素为 1外，其余均为零。(u + 1,u + 1)位置上的元素为 1，此时PΓ的第 u + 1行 的前 u个元素分别为 1 11 2,2 , ii ui jui j ii aa ，1 ≤ j ≤ u 由(1,1) - (u + 1,u + 1)位置所组成的行列式为引理 2中(3)式的形式，把 ， 1 ≤ j ≤ u，y1 = 1 代入(3)式结合据引理 2可得 11 1 ,2 i ui j uj i ya 1 10, 0 121 2P 2,222d,n u uiuji ui uij iji Eada u A (14) 若对 PΓ再进行右乘 Q运算，则PΓQ的第1行至第 u行除(u + 1,u + 2)位置上的元素为–2 外，其余的均为0， Copyright © 2011 Hanspub PM  肖卿灿 等关于二进制矩阵方程猜想的一类新解 196 | 这样就可对|PΓQ|运用行列式定义直接算出结果，其结果仍为(14)式。 对于 0 F A的情形，我们有 1 0,0 121 22,2 22d, uu jij nj uij jij Eada A nu (15) 当u = 1(参见(14)式)或υ = 1(参见(15)式)即为François Arnault 在文[1]中的结果。当 u > 1 时，令 an,1 = 1,bi,1 = ai,1，bi,j = d0ai,j，u + 1 ≤ i ≤ n，1 < j ≤ u，则(14)可写成 2 1 1 222, n nnt nt jj tj EP b A0 d, τ = {j:1 ≤ t ≤ n – 2,t + 2–υ ≤ j ≤ t + 1,j ≤ u} (16) 若要满足猜想条件必须添加a1,1 = 1 时j ≠ 1, an,n = 1 时j ≠ t + 1，此时 τ也可写成 τu = {j:2 ≤ i ≤ n – 1, u + 1 ≤ i + j –1 ≤ n,1 ≤ j ≤ u；a1,1 = 1 时j ≠ 1, an,n = 1 时j ≠ n + 1 – i} (17) 在(n,1) - (u + 1,u)位置所形成的矩形框内添加元素，每行每列至多只添加进一个非零元素，故有 2n – t的系数 只能在–bn – t + j – 1,j之中，也就是说 2t的系数(1 < t < n)只出现在(t + j – 1,j)位置上。对于 a1,1 = 1 时第 1列不添加元 素，对于an,n = 1 时第 n行不添加元素。 设aζ(1 < ζ < n)是满足猜想条件的一组解，aζ全部落在(n,1) - (u + 1,u)位置所形成的矩形框内，令hζ = d0aζ， 利用(16)可知在(n,1) - (u + 1,u)位置所形成的矩形框内 ht在(t + j – 1,j)位置上(2 ≤ t ≤ ζ)任意移动都不会改变行列式 |E – 2A|的值，只要移动的结果满足猜想条件都是由此衍生的解。当 n为偶数时最大的矩形框为 2nn2，n为 奇数时最大的矩形框为 12 12nn和 12 12nn，设 m – 1 为aζ中不为零的个数 (m ≤ INT(2n))，an,n ≠ 1的情形其矩形框的最小高度为m – 1，从最小高度为 m – 1的矩形框到最大的矩形框， 再到最小宽度为m – 1 的矩形框，依次在各矩形框内在(t + j–1,j)位置上移动各ht，得到满足猜想条件的不同解。 当中间项较少且 n较大时，如4mn，n > 30 时，(16)式中将出现较多空项，若在(t + j – 1,j)位置上多填上 一对符号相反的虚拟对hζ，则|E – 2A|的值仍不变。对于给定的 q，找出满足猜想条件的虚拟对，重复以上步骤， 找出符合条件的解。 同理对于上三角部分(d0 = –1 时，r2必须为零才可行)，在(u,u + 2) - (1,n)位置所形成的矩形框内添加元素rt， 利用 rt = d0bt，2 ≤ t，2t的系数(1 < t < n)只出现在(i,n + 1 – t + i)位置上。仿前可得出上三角部分的大部分解。 至此，对于每个给定的 q，我们能够求出大部分的解。为了防止虚拟对的出现我们只须把猜测的条件加强 至：对于每个t，最多只有一个落(t + j – 1,j)位置上，或者最多只有一个出现在(i,n + 1–t + i)位置上。特别强调填 数的时候必须在同一矩形框内进行，若超出矩形框的范围就容易出错。例如： 12 12 12 12 12 12 12 00212 1 200001 2 1109 1173 0000212000012 000201 202001 2 002001 2000012 000001 2000212 2121 第二式中r2和r4的移动超出了矩形框的范围，故出错。 Copyright © 2011 Hanspub PM  肖卿灿 等 | 关于二进制矩阵方程猜想的一类新解 Copyright © 2011 Hanspub PM 197 5. 构造方法 设q为负奇数， 1q 2 0 11 2 r ， 1q 2 01d ，根据引理1，q可化成(12)式的形式，补齐系数为0的项， 把它写成(11)式的形式。利用rt = d0bt, 2 ≤ t ≤ n – 2考察在(n,1) - (u + 1,u)位置所形成的矩形框内添加元素rt，每 行每列至多只添加进一个非零元素，使得在每行或每列至多有两个元素不为零的情形。由上面的结论知rt只能 填在(t + j – 1, j)位置上，据(17)式j必须满足 j τu，利同(12)式可知，在(n – (2 + im) + j – 1,j)位置上 rn – (2 + im) 仅有 3 – r0 + im种选法，上面我们己经构造满足猜想条件的A(参见(4)~(7)及(10)式)，在此基础上沿着与主对角线 平行的方向作平移变换，变换后若rn – (2 + im)的位置未越出边界，则仍为其解；当中间项即有奇数项又有偶数 项时， (4)式和(7)式以副对角线作对称移动rj，|A – 2E|值不变，(5)式和(6)式作类似的变换，变换后若 rn – (2 + im) 的位置未越出边界，则|A – 2E|值不变。对于上三角的情形必须满足r2 + i1未超出边界。 利同(12)式可知，在(n – (2 + im) + j – 1,j)位置上 rn – (2 + im)仅有 3 – r0 + im种选法，在(n – (4 + im + im–1) + j – 1,j) 位置上 rn – (4 + im + im – 1)可能有3 – r0 + im + im–1 种选法，令 pi = jm – jm–i，j0 = 0，对于在 基础上添加 m – 1 个 不为零的元素(m ≤ INT( 0 G A 2n))，位于下三角位不同行不同列至多各添加一个元素使得每行和每列至多有两个元素 不为零的情形。首先rn – (2 + im)填在(n – (2 + im),1)位置上，接着rn – (4 + im + im-1) 填在(n – (4+ im + im–1) + 1,2) 位置上，rn – (2j + pi) 填在(n – (2j + pi) + j – 1,j)位置上，r (2 + i1)填在(2 + i1 + j – 1,j)位置上，若 il全为零则仅有 3 – r0种填法(1 ≤ l ≤ m – 1)(定理 1已给出)。若 il不全为零，当 m ≥ 4时rn – (4 + im + im–1) 填在(n – (4 + im + im–1) + 1,2) 位置上有3 – r0 + im + im–1 种填法，则从最小高度为m – 1 矩形框((n,1) - (n – m + 2, n – m + 1)(开始出发扩大高度， 沿着与主对角线平行的方向向左上角方向作平移变换 2 – r0 + im次，在高度为 m矩形框沿着与主对角线平行的方 向在(n – (2j + pi) + j – 1,j)位置上移动部分 rn – (2j + pi)位置得出满足条件的不同解，扩大矩形框的高度至 m + 1， 重复上述步骤，从最小高度为m – 1的矩形框到最大的矩形框(当n为偶数时最大的矩形框为 2nn2，n为奇 数时最大的矩形框为 12 12nn和 12 12nn，an,n ≠ 1 的情形其矩形框的最小高度为m – 1)，再 到最小宽度为m – 1 的矩形框，依次在各矩形框内在(t + j – 1,j)位置上移动各rt，得到满足猜想条件的不同解。 同理对于上三角部分(d0 = –1 时，r2必须为零才可行)，在(u,u + 2) - (1,n)位置所形成的矩形框内添加元素rt， 利用 rt = d0bt,2 ≤ t, 2t的系数(1 < t < n)只出现在(i,n + 1 – t + i)位置上。仿前可得出上三角部分的大部分解。 6. 猜测 设σ为Max{Min{3 – r0 + pl,1 + jm – l – i1}:1 ≤ l ≤ m–1}下标中最小的一个，我们猜测在下三角部可能有 m2 00 1 11 1r 3r1 ll ll pj 1 i m i 种填法；设 σ1为Max{Min{1 – r0 + jl, 1 + pm – l – im}:1 ≤ l ≤ m – 1}下标中最小 的一个，我们猜测在上三角部可能有 种填法。 11 m2 00 1 11 11 1 ll ll rrj p 参考文献 (References) [1] F. Arnault, T. P. Berger, C. Lauradoux, M. Minier and B. Pousse. A new approach for FCSRs. In: M. J. J. V. Rijmen Jr., R. Safavi-Naini (Eds.), Selected areas in cryptography. New York: Springer, 2009, 5867: 433-448. [2] F. Arnault, T. P. Berger and B. Pousse. A matrix approach for FCSR automata. Cryptography and Communications, Springer Science + Busi- ness Media, 2011, 3(2): 109-139. [3] T. P. Berger, M. Minier and B. Pousse. Software oriented stream ciphers based upon FCSRs in diversified mode. In: B. Roy, N. Sendrier (Eds.), INDOCRYPT 2009, Lecture notes in computer science. New York: Springer, 2009, 5922: 119-135. |