法国数学家Pierre de Fermat于1640年提出了形如F_n=2²ⁿ+1的数(后人称Fermat数)为素数的猜想，但Euler于1732年在研究该问题时发现F₅为合数，此后关于Fermat数的研究持续了几个世纪. Fermat数在二进制计算机算法、二元序列的复杂度等研究中都有重要应用.

Lenstra等^[1-2]利用Fermat数的素性和分解问题给出了一类由单圈T函数生成的极大周期序列，即第k位序列的2-adic复杂度，给出了该类序列由带进位的反馈移位寄存器(FCSR，feedback with carry shift register)的生成级数，并由此研究了单圈T函数按状态输出序列的2-adic复杂度，给出了其2-adic复杂度的估计.

1 预备知识 1.1 Fermat数

定义1  称形如2²ⁿ+1(n=0, 1, 2, …)的数为Fermat数，记作F_n.

对Fermat数的因子分解问题，有如下结论^[3]：

1) F₀、F₁、F₂、F₃、F₄为素数；

2) F₅~F₁₁为合数，且人们对这些Fermat数已全部找到了素因子分解；

3) 对F₁₂、F₁₃、F₁₅、F₁₆、F₁₇、F₁₈、F₁₉、F₂₁、F₂₃已经找到部分因子；

4) 对F₁₄、F₂₀、F₂₂、F₂₄已证明为合数，但未找到因子；

5) F₀F₁F₂F₃…F_n=F_n+1-2；

6) 任意2个Fermat数F_m、F_n(m≠n)互素，即

$ \left( {{F}_{m}}, {{F}_{n}} \right)=1 $

引理1^[3]  若2^m+1是素数，则m=2ⁿ；反之不真.

引理2^[3]  当n≥2时，F_n的素因数必为形式

$ p={{2}^{n+2}}h+1\ \ \left( h\in \mathbb{N} \right) $

引理3^[3]  Fermat合数除641外，没有其他小于10⁶的因子.

引理4^[3]  形如4t+3(t≥1)的素数均不为Fermat数的因子.

1.2 序列的2-adic复杂度

考虑到线性移位寄存器容易被攻击的问题，Klapper等^[4-5]提出了FCSR.一个FCSR由r个系数q₁, q₂, …, q_r, (q_i∈{0, 1}，i=1, 2…, r)以及一个初始存储整数m_r-1(可为任意整数)确定.其结构如图 1所示.

记FCSR的任一个状态为(a_n-1, a_n-2, …, a_n-r), a_i∈{0, 1}，存储整数为m_n-1，则移位寄存器的运算为

A1：计算${{\delta }_{n}}=\sum\limits_{k=1}^{r}{{{q}_{k}}{{a}_{n-k}}+{{m}_{n-1}}}$；

A2：右移一位，输出寄存器最右端的a_n-r；

A3：令a_n=δ_n(mod 2)，将其放入寄存器的最左端；

A4：令m_n=(δ_n-a_n)/2=$\left\lfloor {{\sigma }_{n}}/2 \right\rfloor $.

引理5^[4]  设x为最终周期序列.则$\alpha =\sum\limits_{i=0}^{\infty }{{{x}_{i}}{{2}^{i}}}$是2个整数的商p/q，其中q为生成x的FCSR的连接整数.进而x是严格周期序列，当且仅当1≤α≤0.

这说明每一个最终周期序列都可以由一个FCSR产生.反过来，下面的结果说明所有由FCSR生成的序列也都是最终周期的.

引理6^[6]  设序列x由FCSR生成，q为x的连接整数，则x为最终周期序列，且存在整数p使得$\alpha =\sum\limits_{i=0}^{\infty }{{{x}_{i}}{{2}^{i}}=p/q}$.

设x为最终周期序列，q为生成x的FCSR的连接整数，则称q为x的一个连接整数.称x的连接整数中的最小的那个为x的极小连接整数.

下面的结果给出连接整数满足的性质:

引理7^[6]  设x为严格周期二元序列，q为x的极小连接整数，则q′为x的一个连接整数当且仅当q′可被q整除.

引理8^[6]  设x为严格周期序列，T为x的周期，则x的极小连接整数q满足q≤2^T-1.

FCSR序列的周期完全由其极小连接整数确定.类似于线性复杂度，2-adic复杂度衡量一个周期序列需要用多大的FCSR来生成. 2-adic复杂度定义如下.

定义2^[6]  设x为严格周期序列，$\sum\limits_{i=0}^{\infty }{{{x}_{i}}{{2}^{i}}=p/q}$，其中gcd (p, q)=1，称ϕ₂(x)=lb(Φ(p, q))为x的2-adic复杂度，其中Φ(p, q)=max(|p|, |q|).

2-adic复杂度度量一个二元序列由FCSR^[4]生成的难度，它与线性复杂度没有必然的联系，即具有高线性复杂度的序列，其2-adic复杂度可能会很低，反之亦然. Klapper提出了有理逼近算法，即对一条固定序列，只要已知其约2倍2-adic复杂度比特，就能唯一确定原序列.这就要求密钥序列必须具有较高的2-adic复杂度，才能有效抵抗有理逼近攻击.

引理9^[6]  设x为严格周期二元序列，极小连接数为q，则x的2-adic复杂度为ϕ₂(x)=lb q.

1.3 单圈T函数及其生成序列

记F₂为二元域，F₂ⁿ为F₂上的n维向量空间，其中n为正整数，称x=(x₀, x₁, …, x_n-1)∈F₂ⁿ为一个n长单字.在剩余类环Z/(2ⁿ)中，x可被表示成$\sum\limits_{j=0}^{n-1}{{{x}_{i}}{{2}^{i}}}$.称x =(x₀, …, x_m-1)^T∈F₂^m×n为一个多字，其中每一个x_i(i=0, 1, …, m-1)为n长单字，显然，多字x也可被看作一个m×n矩阵.

定义3^[7-10]  设映射f:F₂^m×n→F₂^l×n为f(x)= x，其中x和y是多字.若输出y的第i列只与输入x的第0，1，…，i(0≤i＜n)列有关，则称f为一个T函数.当m=l=1时，称f为一个单字T函数；反之称其为多字T函数.注意，后面出现的T函数均指单字T函数，其相应性质都可推广到多字T函数中.

设x₀为初始状态，T函数f:F₂ⁿ→F₂ⁿ为状态转移函数，即f(x_i)= x_i+1，于是可得f的状态序列{x_i}_i≥0.若序列{x_i}_i≥0的极小周期为N =2ⁿ，则称f是单圈的.

定义“+”为域上的加法，“⊕”为模2加法.称由x_i第k位形成的序列{x_{i, k}}_i=0^2n-1(0≤k＜n)为x_i的第k位序列，记为x_k.由文献[11-12]知，x_k的周期为N_k=2^k+1，且

$ {{x}_{i+{{N}_{k}}/2, k}}={{x}_{i, k}}\oplus 1 $

(1)

T函数f(x)也可被表示为向量布尔函数，即f(x)=(f₀(x), f₁(x), …, f_n-1(x))，其中每一个分量函数f_k(x) (0≤k＜n)称为第k位布尔函数，其取值只与x的前k位有关^[11].据定义3可知，第k位序列即为第k位分量布尔函数的输出序列.

2 单圈T函数序列的2-adic复杂度

引理10  设f:F₂ⁿ→F₂ⁿ为单圈T函数，其状态序列{x_i}_i≥0的第k位序列{x_{i, k}}_i=0^2n-1(0≤k＜n)的极小连接整数q满足q≤2^2k+1-1.

该结果可由引理9获得.

定理1  设f:F₂ⁿ→F₂ⁿ为单圈T函数，其状态序列{x_i}_i≥0的第k位序列s_k$\triangleq ${x_{i, k}}_i=0^2n-1(0≤k＜n)的2-adic复杂度ϕ₂(s_k)满足：

1) k=0, 1, 2, 3, 4时，ϕ₂(s_k)=lbF_k，其中F_k为第k个Fermat数；

2) k≥5时，若F_k=p₁p₂…p_t，记s_k的后1/2序列对应的十进制数$\sum\limits_{i={{2}^{n-1}}}^{2n-1}{{{x}_{i, k}}{{2}^{i-{{2}^{n-1}}}}}$的因子集合为P，并记P∩{p₁, p₂, …, p_t}={p_j1, p_j2, …, p_ju}，则${{\phi }_{2}}\left( {{s}_{k}} \right)=\text{lb}\frac{{{F}_{k}}}{{{p}_{j1}}{{p}_{j1}}\cdots {{p}_{ju}}}$.

证明  根据2-adic复杂度的定义，需讨论

$ \begin{align} &\sum\limits_{i=0}^{\infty }{{{x}_{i}}{{2}^{i}}=\frac{\sum\limits_{i=0}^{T-1}{{{x}_{i}}{{2}^{i}}}}{1-{{2}^{T}}}}=-\frac{\sum\limits_{i=0}^{{{2}^{k+1}}-1}{{{x}_{i}}{{2}^{i}}}}{{{2}^{{{2}^{k+1}}}}-1}= \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ -\frac{\sum\limits_{i=0}^{{{2}^{k+1}}-1}{{{x}_{i}}{{2}^{i}}}}{\left( {{2}^{{{2}^{k}}}}-1 \right)\left( {{2}^{{{2}^{k}}}}+1 \right)} \\ \end{align} $

(2)

由单圈T函数的性质，式(2)中分子可表示为

$ \begin{align} &\sum\limits_{i=0}^{{{2}^{k+1}}-1}{{{x}_{i}}{{2}^{i}}}=\sum\limits_{i=0}^{{{2}^{k}}-1}{\left( {{x}_{i, k}}{{2}^{i}}+{{x}_{i+{{2}^{k}}, k}}{{2}^{i+{{2}^{k}}}} \right)}= \\ &\ \ \ \sum\limits_{i=1}^{{{2}^{k}}-1}{\left[{{x}_{i, k}}{{2}^{i}}+\left( {{x}_{i, k}}\oplus 1 \right){{2}^{i+{{2}^{k}}}} \right]} \\ \end{align} $

(3)

考虑到{x_i, x_i⊕1}={0, 1}，记S={i|x_{i+2^k, k}=1, 0≤i≤2^k-1}，设|S|=m，则S也可简记为{i₁, i₂, …, i_m}，其中i₁＜i₂＜…＜i_m，于是式(3)可表示为

$\begin{align} &\ \ \ \ \sum\limits_{i=1}^{{{2}^{k}}-1}{\left[{{x}_{i, k}}{{2}^{i}}+\left( {{x}_{i, k}}\oplus 1 \right){{2}^{i+{{2}^{k}}}} \right]}= \\ &\ \ \sum\limits_{i=1}^{{{2}^{k}}-1}{\left( 1\cdot {{2}^{i}} \right)}+\sum\limits_{i=1, i\in S}^{{{2}^{k}}-1}{{{x}_{i, k}}\left( {{2}^{i+{{2}^{k}}}}-{{2}^{i}} \right)}= \\ &({{2}^{{{2}^{k}}}}-1)+({{2}^{{{2}^{k}}}}-1)({{2}^{{{i}_{1}}}}+{{2}^{{{i}_{2}}}}+\cdots +{{2}^{{{i}_{m}}}})= \\ &\ \ \ \ \ ({{2}^{{{2}^{k}}}}-1)(1+{{2}^{{{i}_{1}}}}+{{2}^{{{i}_{2}}}}+\cdots +{{2}^{{{i}_{m}}}})~ \\ \end{align} $

因而式(1)成为

$ \frac{1+{{2}^{{{i}_{1}}}}+{{2}^{{{i}_{2}}}}+\cdots +{{2}^{{{i}_{m}}}}}{{{2}^{{{2}^{k}}}}+1} $

(4)

而式(4)分母恰好为第k个Fermat数，记作F_k，由文献[1-3]可知，前5个Fermat数F₀=3，F₁=5，F₂=17，F₃=257，F₄=65 537均为素数，由引理10知ϕ₂(s_k)=lbF_k.

当k≥5时，由文献[1-2]可知，在目前可计算范围内F_k为合数，且皆为一次因子，记F_k=p₁p₂…p_t，则问题转化为求式(4)的最简分数.记s_k的后1/2序列对应的十进制数$\sum\limits_{i={{2}^{n-1}}}^{{{2}^{n}}-1}{{{x}_{i, k}}{{2}^{i-{{2}^{n-1}}}}}$的因子集合为P，并记P∩{p₁, p₂, …, p_t}={p_j1, p_j2, …, p_ju}，则式(4)的最简分数为

$\frac{\frac{1+{{2}^{{{i}_{1}}}}+{{2}^{{{i}_{2}}}}+\cdots +{{2}^{{{i}_{m}}}}}{~{{p}_{{{j}_{1}}}}{{p}_{{{j}_{2}}}}\cdots {{p}_{{{j}_{u}}}}}}{\frac{{{F}_{k}}}{{{p}_{{{j}_{1}}}}{{p}_{{{j}_{2}}}}\ldots {{p}_{{{j}_{u}}}}}} $

因而ϕ₂(s_k)=lb$\frac{{{F}_{k}}}{{{p}_{{{j}_{1}}}}{{p}_{{{j}_{2}}}}\ldots {{p}_{{{j}_{u}}}}}$.特别地，s_k的后1/2序列对应的十进制数$\sum\limits_{i={{2}^{n-1}}}^{{{2}^{n}}-1}{{{x}_{i, k}}{{2}^{i-{{2}^{n-1}}}}}$恰为F_k的某个因子p_i时，ϕ₂(s_k)= $ \text{lb}\frac{{{F}_{k}}}{{{p}_{i}}}$.

推论1  设f:F₂ⁿ→F₂ⁿ为单圈T函数，其状态序列{x_i}_i≥0的第k位序列为s_k$\triangleq ${x_{i, k}}_i=0^2n-1(2≤k＜n).则当式(4)中1+2^i₁+2^i₂+…+2^i_m≠2ⁿ⁺²h+1(h∈N)时，ϕ₂(s_k)=lbF_k.

证明  由引理2可知，当n≥2时，F_n的素因数必为形式p=2ⁿ⁺²h+1(h∈N)，于是对满足

$ 1+{{2}^{{{i}_{1}}}}+{{2}^{{{i}_{2}}}}+\cdots +{{2}^{{{i}_{m}}}}\ne {{2}^{n+2}}h+1 $

的单圈T函数k位序列，式(4)为既约分式，故ϕ₂(s_k)=lbF_k.

推论2  设f:F₂ⁿ→F₂ⁿ为单圈T函数，其状态序列{x_i}_i≥0的第k位序列为s_k$\triangleq ${x_{i, k}}_i=0^2n-1(6≤k＜n)，则当$\underset{{{i}_{j}}\in S}{\mathop{\text{max}}}\, \ {{i}_{j}}={{i}_{m}}\le 19$时，ϕ₂(s_k)=lbF_k.

证明  由引理3可知，当i_m＜lb 10⁶≈19.93时，式(4)分母的因子都大于10⁶.此时式(4)的分子1+2^i₁+2^i₂+…+2^i_m≤10⁶.于是式(4)为既约分式，故ϕ₂(s_k)=lbF_k.

推论3  设f:F₂ⁿ→F₂ⁿ为单圈T函数，其状态序列{x_i}_i≥0的第k位序列为s_k$\triangleq ${x_{i, k}}_i=0^2n-1(6≤k＜n)，则当式(4)中1+2^i₁+2^i₂+…+2^i_m为二进制形如…11₂的素数时，ϕ₂(s_k)=lbF_k.

证明  由引理4可知，形如4t+3(t≥1)的素数，即二进制形如…11₂的素数均不是Fermat数的因子.因而式(4)为既约分式，故ϕ₂(s_k)=lbF_k.

进一步，对单圈T函数的第k位序列，有定理2.

定理2  设f:F₂ⁿ→F₂ⁿ为单圈T函数，其状态序列{x_i}_i≥0的第k位序列s_k(0≤k＜n)的周期为T，则ϕ₂(s_k)＜T≤ϕ(q)＜2^T/2 (k=0, 1, 2, …，13)，其中q为s_k的极小连接整数，φ(q)为q的欧拉函数值.

证明

1) 由定理1可知

$ {{\phi }_{2}}({{s}_{k}})\le \text{lb}({{2}^{{{2}^{k}}}}+1)<\text{lb}{{2}^{{{2}^{k}}}}{{2}^{{{2}^{k}}}}={{2}^{k+1}}=T~ $

2) 当k=0, 1, 2, …，4时，2^2k+1为素数

$ \varphi \left( q \right)=\varphi ({{2}^{{{2}^{k}}}}+1)={{2}^{{{2}^{k}}}}\ge {{2}^{k+1}}=T $

(5)

式(5)中等号成立，当且仅当k=0, 1.

当5≤k≤13时，由F_k的分解式^[1-2]可知，所有的φ(q)＞2^k+1=T.

3) 由定理1的证明知，序列s_k的极小连接整数q≤1+2^2k=1+2^T/2；同时，φ(q)≤q-1对所有整数q都成立.因而，φ(q)＜2^T/2.

对于单圈T函数的按状态输出序列，其周期较大，相应的2-adic复杂度由定理3给出.

定理3  设f:F₂ⁿ→F₂ⁿ为单圈T函数，其状态序列为S，则S具有最大2-adic复杂度lb(2^n·2n-1+1).

证明  记按状态输出序列为

$ \begin{align} &S={{\{{{x}_{i, k}}\}}_{0\le i\le {{2}^{n}}-1, 0\le k\le n-1}}\triangleq {{\{{{s}_{j}}\}}_{0\le j\le n\text{ }\cdot {{2}^{n}}-1}}, 考查 \\ &\sum\limits_{i=0}^{\infty }{{{x}_{i}}{{2}^{i}}=\frac{\sum\limits_{i=0}^{T-1}{{{x}_{i}}{{2}^{i}}}}{1-{{2}^{T}}}}=-\frac{\sum\limits_{i=0}^{n-1}{\sum\limits_{j=0}^{{{2}^{n}}-1}{{{x}_{i, j}}}{{2}^{j+i\cdot {{2}^{n}}}}}}{1-{{2}^{T}}} \\ \end{align} $

(6)

根据单圈T函数生成序列的性质，若x_{i, j}=1，式(6)的分子前半部分的和为

$ \sum\limits_{i=0}^{n-1}{\sum\limits_{j=0}^{{{2}^{n}}-1}{1\times }{{2}^{j+i\cdot {{2}^{n}}}}={{2}^{n\cdot {{2}^{n-1}}}}-1} $

记S的后半部分序列中非0位置的下标为t₁, t₂, …, t_u，则式(6)的分子后半部分的和为(2^n·2n-1-1)×(2^t₁+2^t₂+…+2^t_t)，故式(6)的分子等于(2^n·2n-1-1)(1+2^t₁+2^t₂+…+2^t_t)，式(6)可约分为

$ \frac{1+{{2}^{{{t}_{1}}}}+{{2}^{{{t}_{2}}}}+\cdots +{{2}^{{{t}_{t}}}}}{1+{{2}^{n\cdot {{2}^{n-1}}}}}~ $

因而S的最大2-adic复杂度为lb(2^n·2n-1+1).

S的2-adic复杂度ϕ₂(S)依赖于数2^n·2n-1+1的分解，当n=2^m时，这依然是Fermat数的分解问题；n≠2^m且较大时，这对应大整数分解问题.

推论4  设f:F₂ⁿ→F₂ⁿ为单圈T函数，其状态序列S$\triangleq ${x_i}_i≥0的周期为T，则S的最大2-adic复杂度max ϕ₂(S)满足

$ \frac{T}{2}<\text{max}\ {{\phi }_{2}}\left( S \right)<\frac{T}{2}+1~ $

证明  由

$ \begin{align} &\text{max}\ {{\phi }_{2}}\left( S \right)=\text{lb}({{2}^{n\cdot {{2}^{n-1}}}}+1)>\text{lb}~{{2}^{n\cdot {{2}^{n-1}}}}=\frac{T}{2} \\ &\ \ \ \ \text{lb}({{2}^{n\text{ }\cdot {{2}^{n-1}}}}+1)<\text{lb}2\times {{2}^{n\text{ }\cdot {{2}^{n-1}}}}=\frac{T}{2}+1 \\ \end{align} $

可得.

对单圈T函数的按状态输出序列，引理8的结果可改进为推论5.

推论5  设f:F₂ⁿ→F₂ⁿ为单圈T函数，其状态序列S={x_i}_i≥0的周期为T，q为S的极小连接整数，则φ(q)＜2^T/2.

证明  一方面，由定理3可知，序列S的最大连接整数q≤1+2^n·2n-1=1+2^T/2；另一方面，φ(q)≤q-1对所有整数q都成立.因此，φ(q)＜2^T/2.

推论6  设f:F₂ⁿ→F₂ⁿ为单圈T函数，其状态序列S={x_i}_i≥0的周期为T，q为S的极小连接整数，则不等式

$ T<\varphi \left( q \right) $

在域F、F₂²、F₂⁴、F₂⁵、F₂⁶、F₂⁷、F₂⁸、F₂¹⁶、F₂³²中成立.

对f:F₂ⁿ→F₂ⁿ(n=1, 2, 4, 5, 6, 7, 8, 16, 32)，可以通过计算T和min{φ(q_i)}(q_i为2^n2n-1+1的素因子)的值比较得到T＜φ(q).

在分组密码高级加密标准(AES, advanced encryption standard)中，密钥在F₂⁷、F₂⁸中取得，流密码SOBER、LEVIARHAN等中，密钥在F₂¹⁶、F₂³²中取得，而推论6表明，单圈T函数状态序列在这些域中不是l序列.

3 结束语

单圈T函数生成序列因其具有极大周期、好的游程分布、能将0作为初始状态等优点，受到了密码设计者的广泛关注. FCSR是一类可用于序列密码设计的非线性序列发生器，序列的2-adic复杂度反映了序列由FCSR生成的级数.通过分析单圈T函数生成的第k位序列和状态序列各位之间的关系，利用Fermat数理论，给出了这2种序列低位序列的2-adic复杂度的值和高位序列2-adic复杂度的估值，从FCSR生成的角度，揭示了单圈T函数序列的特性.结果表明，与文献[6, 12]的结果对比，尽管单圈T函数生成序列达到了最大周期并具有高的线性复杂度，但远没有达到最大2-adic复杂度，不是l序列.