轻量级加法同态算法
潘无穷，顾洪良
潘无穷，顾洪良, 蚂蚁集团. E-mail: wuqiong.pwq@antgroup.com.
我们发现目前的加法同态算法基本都是基于公钥体制的，少数的几个基于对称体制的加法同态算法，都被陆续发现有安全问题。因此，我们尝试设计了一种基于对称体制的加法同态算法，并寄希望因为不需要满足“公钥和私钥不同”，而获得更高的性能。与Paillier等标准的加法同态算法相比，本文算法将加解密的消耗从模幂降为模乘，将密文加的消耗从模乘降为模加。
我们还未能完全探明新设计的算法的安全机理，但如果能够攻破以下问题，可能会对算法的安全性造成显著挑战：
{x=u+r1py=v+r2qcases𝑥𝑢subscript𝑟1𝑝𝑦𝑣subscript𝑟2𝑞\left\{\begin{array}[]{l}x=u+r_{1}p\\
y=v+r_{2}q\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_x = italic_u + italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT italic_p end_CELL end_ROW start_ROW start_CELL italic_y = italic_v + italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT italic_q end_CELL end_ROW end_ARRAY
,
p,q𝑝𝑞p,qitalic_p , italic_q为长度是ψ/2𝜓2\psi/2italic_ψ / 2的秘密素数。
r1,r2subscript𝑟1subscript𝑟2r_{1},r_{2}italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT分别是均匀分布于[0,2ψ/p],[0,2ψ/q]0superscript2𝜓𝑝0superscript2𝜓𝑞[0,2^{\psi}/p],[0,2^{\psi}/q][ 0 , 2 start_POSTSUPERSCRIPT italic_ψ end_POSTSUPERSCRIPT / italic_p ] , [ 0 , 2 start_POSTSUPERSCRIPT italic_ψ end_POSTSUPERSCRIPT / italic_q ]的随机数。
u,v𝑢𝑣u,vitalic_u , italic_v为长度为ψ/2𝜓2\psi/2italic_ψ / 2的有符号随机数，e为128比特正随机数，且u+v=2128m+e𝑢𝑣superscript2128𝑚𝑒u+v=2^{128}m+eitalic_u + italic_v = 2 start_POSTSUPERSCRIPT 128 end_POSTSUPERSCRIPT italic_m + italic_e, m𝑚mitalic_m为明文；(x,y)𝑥𝑦(x,y)( italic_x , italic_y )为密文。
我们设计的算法在上式的基础上增加了“线性变换、更多的噪声、更长的r1subscript𝑟1r_{1}italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT和r2subscript𝑟2r_{2}italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT”等措施，因我们未能探明上述问题的难度，所以暂时无法知晓增加的安全措施是否有意义。
直接使用上述过程进行加密过程是无法进行解密的。为此，我们构思了两种解密思路，相应地对加密过程进行了微调，分别对应后文的两种算法。
算法1
1 变量
密钥：{p,q,a,b}𝑝𝑞𝑎𝑏\{p,q,a,b\}{ italic_p , italic_q , italic_a , italic_b }，其中p,q𝑝𝑞p,qitalic_p , italic_q为γ𝛾\gammaitalic_γ（例如1024）比特大素数，a,b𝑎𝑏a,bitalic_a , italic_b为γ𝛾\gammaitalic_γ比特。
明文：m𝑚mitalic_m，为η𝜂\etaitalic_η（例如64）比特。
密文：{x,y,w}𝑥𝑦𝑤\{x,y,w\}{ italic_x , italic_y , italic_w }, 其中x,y𝑥𝑦x,yitalic_x , italic_y分别为ψ𝜓\psiitalic_ψ比特(ψ≥2γ𝜓2𝛾\psi\geq 2\gammaitalic_ψ ≥ 2 italic_γ,这里暂时取ψ𝜓\psiitalic_ψ为2γ2𝛾2\gamma2 italic_γ，例如2048)，w𝑤witalic_w为密文相加次数。注：算法支持的密文相加次数最大为w<2α/2𝑤superscript2𝛼2w<2^{\alpha/2}italic_w < 2 start_POSTSUPERSCRIPT italic_α / 2 end_POSTSUPERSCRIPT (α𝛼\alphaitalic_α定义参见下文)。
𝐗𝐠:𝐡subscript𝐗:𝐠𝐡\mathbf{X_{g:h}}bold_X start_POSTSUBSCRIPT bold_g : bold_h end_POSTSUBSCRIPT:
Xg:hsubscript𝑋:𝑔ℎX_{g:h}italic_X start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT是指X𝑋Xitalic_X从第g𝑔gitalic_g比特到第hℎhitalic_h比特的数据(含g𝑔gitalic_g，不含hℎhitalic_h；g≤h𝑔ℎg\leq hitalic_g ≤ italic_h;第00比特表示最低位)。Xg:∞subscript𝑋:𝑔X_{g:\infty}italic_X start_POSTSUBSCRIPT italic_g : ∞ end_POSTSUBSCRIPT指X𝑋Xitalic_X从第g𝑔gitalic_g比特到最高位的数据（含g𝑔gitalic_g）。
若X𝑋Xitalic_X为负数，令Xg:h=−|X|g:hsubscript𝑋:𝑔ℎsubscript𝑋:𝑔ℎX_{g:h}=-|X|_{g:h}italic_X start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT = - | italic_X | start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT。
记Xg:h¯=2gXg:hsubscript𝑋¯:𝑔ℎsuperscript2𝑔subscript𝑋:𝑔ℎX_{\overline{g:h}}=2^{g}X_{g:h}italic_X start_POSTSUBSCRIPT over¯ start_ARG italic_g : italic_h end_ARG end_POSTSUBSCRIPT = 2 start_POSTSUPERSCRIPT italic_g end_POSTSUPERSCRIPT italic_X start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT，Xg:∞¯=2gXg:∞subscript𝑋¯:𝑔superscript2𝑔subscript𝑋:𝑔X_{\overline{g:\infty}}=2^{g}X_{g:\infty}italic_X start_POSTSUBSCRIPT over¯ start_ARG italic_g : ∞ end_ARG end_POSTSUBSCRIPT = 2 start_POSTSUPERSCRIPT italic_g end_POSTSUPERSCRIPT italic_X start_POSTSUBSCRIPT italic_g : ∞ end_POSTSUBSCRIPT
数据结构：算法及证明过程中部分变量采用下面的数据结构：
高位随机数(ρ𝜌\rhoitalic_ρ) ∥∥\|∥ 查找区(α𝛼\alphaitalic_α) ∥∥\|∥ 明文区(η𝜂\etaitalic_η) ∥∥\|∥ 低位随机数(ρ𝜌\rhoitalic_ρ)
•
高、低位随机数各ρ𝜌\rhoitalic_ρ比特，用于存放随机数。
•
查找区为α𝛼\alphaitalic_α比特(例如40)，用于解密时搜索关键参数。
•
明文区为η𝜂\etaitalic_η比特。注意，算法要求明文相加后的长度也不能超过明文区。
•
上述变量满足2ρ+α+η=γ2𝜌𝛼𝜂𝛾2\rho+\alpha+\eta=\gamma2 italic_ρ + italic_α + italic_η = italic_γ。
实际算法中，查找区被等分成θ𝜃\thetaitalic_θ个小的查找区，记α=μθ𝛼𝜇𝜃\alpha=\mu\thetaitalic_α = italic_μ italic_θ （例如μ=8𝜇8\mu=8italic_μ = 8，θ=5𝜃5\theta=5italic_θ = 5）。
2 加密
加密的核心思想是，把明文分成两个分片，然后把两个分片按照前述数据结构使用随机数“夹在中间”，最后再分别将两个分片隐藏在近似公因子问题的误差部分中，具体过程如下：
生成两个ρ𝜌\rhoitalic_ρ比特正随机数ξ,ζ𝜉𝜁\xi,\zetaitalic_ξ , italic_ζ，一个γ𝛾\gammaitalic_γ比特正随机数τ𝜏\tauitalic_τ，且下式中u𝑢uitalic_u和v𝑣vitalic_v满足u {u=2ρ+η+αξ+2ρm+ζ−τρ:ρ+η+α¯v=τcases𝑢superscript2𝜌𝜂𝛼𝜉superscript2𝜌𝑚𝜁subscript𝜏¯:𝜌𝜌𝜂𝛼𝑣𝜏\left\{\begin{array}[]{l}u=2^{\rho+\eta+\alpha}\xi+2^{\rho}m+\zeta-\tau_{% \overline{\rho:\rho+\eta+\alpha}}\\ v=\tau\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_u = 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT italic_ξ + 2 start_POSTSUPERSCRIPT italic_ρ end_POSTSUPERSCRIPT italic_m + italic_ζ - italic_τ start_POSTSUBSCRIPT over¯ start_ARG italic_ρ : italic_ρ + italic_η + italic_α end_ARG end_POSTSUBSCRIPT end_CELL end_ROW start_ROW start_CELL italic_v = italic_τ end_CELL end_ROW end_ARRAY 为了方便表述，我们将u𝑢uitalic_u和v𝑣vitalic_v称为明文m𝑚mitalic_m的秘密分享。记 M=u+v=(2ρ+η+αξ+τρ+η+α:∞¯)+2ρm+(ζ+τ0:ρ¯)𝑀𝑢𝑣superscript2𝜌𝜂𝛼𝜉subscript𝜏¯:𝜌𝜂𝛼superscript2𝜌𝑚𝜁subscript𝜏¯:0𝜌M=u+v=(2^{\rho+\eta+\alpha}\xi+\tau_{\overline{\rho+\eta+\alpha:\infty}})+2^{% \rho}m+(\zeta+\tau_{\overline{0:\rho}})italic_M = italic_u + italic_v = ( 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT italic_ξ + italic_τ start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT ) + 2 start_POSTSUPERSCRIPT italic_ρ end_POSTSUPERSCRIPT italic_m + ( italic_ζ + italic_τ start_POSTSUBSCRIPT over¯ start_ARG 0 : italic_ρ end_ARG end_POSTSUBSCRIPT ) 由上可知： • M𝑀Mitalic_M的查找区为0，即Mρ+η:ρ+η+α=0subscript𝑀:𝜌𝜂𝜌𝜂𝛼0M_{\rho+\eta:\rho+\eta+\alpha}=0italic_M start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0。 • 当ζ+τ0:ρ¯𝜁subscript𝜏¯:0𝜌\zeta+\tau_{\overline{0:\rho}}italic_ζ + italic_τ start_POSTSUBSCRIPT over¯ start_ARG 0 : italic_ρ end_ARG end_POSTSUBSCRIPT不超过ρ𝜌\rhoitalic_ρ比特时，M𝑀Mitalic_M的明文区为m𝑚mitalic_m，否则M𝑀Mitalic_M的明文区为m+1𝑚1m+1italic_m + 1，即Mρ:ρ+η=msubscript𝑀:𝜌𝜌𝜂𝑚M_{\rho:\rho+\eta}=mitalic_M start_POSTSUBSCRIPT italic_ρ : italic_ρ + italic_η end_POSTSUBSCRIPT = italic_m或m+1𝑚1m+1italic_m + 1。 计算x,y𝑥𝑦x,yitalic_x , italic_y，得到密文(x,y,w=1)𝑥𝑦𝑤1(x,y,w=1)( italic_x , italic_y , italic_w = 1 )： {x=(au)%p+r1py=(bv)%q+r2qcases𝑥percent𝑎𝑢𝑝subscript𝑟1𝑝𝑦percent𝑏𝑣𝑞subscript𝑟2𝑞\left\{\begin{array}[]{l}x=(au)\%p+r_{1}p\\ y=(bv)\%q+r_{2}q\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_x = ( italic_a italic_u ) % italic_p + italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT italic_p end_CELL end_ROW start_ROW start_CELL italic_y = ( italic_b italic_v ) % italic_q + italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT italic_q end_CELL end_ROW end_ARRAY , 其中r1,r2subscript𝑟1subscript𝑟2r_{1},r_{2}italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT是分别满足[0,2ψ/p−1],[0,2ψ/q−1]0superscript2𝜓𝑝10superscript2𝜓𝑞1[0,2^{\psi}/p-1],[0,2^{\psi}/q-1][ 0 , 2 start_POSTSUPERSCRIPT italic_ψ end_POSTSUPERSCRIPT / italic_p - 1 ] , [ 0 , 2 start_POSTSUPERSCRIPT italic_ψ end_POSTSUPERSCRIPT / italic_q - 1 ]的均匀分布的随机数。%percent\%%是取模的意思。 3 同态加 记(x1,y2,w1subscript𝑥1subscript𝑦2subscript𝑤1x_{1},y_{2},w_{1}italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_w start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT)和 (x2,y2,w2subscript𝑥2subscript𝑦2subscript𝑤2x_{2},y_{2},w_{2}italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_w start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT) 为两个密文，则它们的和(x,y,w𝑥𝑦𝑤x,y,witalic_x , italic_y , italic_w)的计算方法为： x=x1+x2𝑥subscript𝑥1subscript𝑥2x=x_{1}+x_{2}italic_x = italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT + italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，y=y2+y2𝑦subscript𝑦2subscript𝑦2y=y_{2}+y_{2}italic_y = italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT + italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT, w=w1+w2𝑤subscript𝑤1subscript𝑤2w=w_{1}+w_{2}italic_w = italic_w start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT + italic_w start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT 同态加的原理是，两个密文分片相加，相当于在明文秘密分享u𝑢uitalic_u和v𝑣vitalic_v上相加，就相当于在明文上相加。 4 解密 4.1 解密思路 为了方便理解严格的解密算法，我们先以不严谨的方式讲述解密思路。 假设密文(x,y)𝑥𝑦(x,y)( italic_x , italic_y )（对应明文记为m𝑚mitalic_m，对应明文的秘密分享记为u𝑢uitalic_u，v𝑣vitalic_v）是由 (x1,y1)subscript𝑥1subscript𝑦1(x_{1},y_{1})( italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT )，(x2,y2)subscript𝑥2subscript𝑦2(x_{2},y_{2})( italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT )，…，(xw,yw)subscript𝑥𝑤subscript𝑦𝑤(x_{w},y_{w})( italic_x start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT )相加得来的（对应的明文记为m1subscript𝑚1m_{1}italic_m start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，m2subscript𝑚2m_{2}italic_m start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，mwsubscript𝑚𝑤m_{w}italic_m start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT。对应的秘密分享分别为u1subscript𝑢1u_{1}italic_u start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，u2subscript𝑢2u_{2}italic_u start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，uwsubscript𝑢𝑤u_{w}italic_u start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT；v1subscript𝑣1v_{1}italic_v start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，v2subscript𝑣2v_{2}italic_v start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，vwsubscript𝑣𝑤v_{w}italic_v start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT）。 因为(ui+vi)subscript𝑢𝑖subscript𝑣𝑖(u_{i}+v_{i})( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT )对应的明文区近似为misubscript𝑚𝑖m_{i}italic_m start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT，所以解密的关键是求得∑i=1w(ui+vi)superscriptsubscript𝑖1𝑤subscript𝑢𝑖subscript𝑣𝑖\sum_{i=1}^{w}(u_{i}+v_{i})∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT )对应的明文区。 由加密过程和同态加法的定义可知： {x=∑i=1wxi=a∑i=1wui+r1′py=∑i=1wyi=b∑i=1wvi+r2′qcases𝑥superscriptsubscript𝑖1𝑤subscript𝑥𝑖𝑎superscriptsubscript𝑖1𝑤subscript𝑢𝑖superscriptsubscript𝑟1′𝑝𝑦superscriptsubscript𝑖1𝑤subscript𝑦𝑖𝑏superscriptsubscript𝑖1𝑤subscript𝑣𝑖superscriptsubscript𝑟2′𝑞\left\{\begin{array}[]{l}x=\sum_{i=1}^{w}x_{i}=a\sum_{i=1}^{w}u_{i}+r_{1}^{{}^% {\prime}}p\\ y=\sum_{i=1}^{w}y_{i}=b\sum_{i=1}^{w}v_{i}+r_{2}^{{}^{\prime}}q\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_x = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_x start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = italic_a ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p end_CELL end_ROW start_ROW start_CELL italic_y = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_y start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = italic_b ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q end_CELL end_ROW end_ARRAY , 其中r1′superscriptsubscript𝑟1′r_{1}^{{}^{\prime}}italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT, r2′superscriptsubscript𝑟2′r_{2}^{{}^{\prime}}italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT分别对应为p𝑝pitalic_p, q𝑞qitalic_q前的系数和。 即 {∑i=1wui≡a−1x(modp)∑i=1wvi≡b−1y(modq)casessuperscriptsubscript𝑖1𝑤subscript𝑢𝑖annotatedsuperscript𝑎1𝑥pmod𝑝superscriptsubscript𝑖1𝑤subscript𝑣𝑖annotatedsuperscript𝑏1𝑦pmod𝑞\left\{\begin{array}[]{l}\sum_{i=1}^{w}u_{i}\equiv a^{-1}x\pmod{p}\\ \sum_{i=1}^{w}v_{i}\equiv b^{-1}y\pmod{q}\end{array}\right.{ start_ARRAY start_ROW start_CELL ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≡ italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x start_MODIFIER ( roman_mod start_ARG italic_p end_ARG ) end_MODIFIER end_CELL end_ROW start_ROW start_CELL ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≡ italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y start_MODIFIER ( roman_mod start_ARG italic_q end_ARG ) end_MODIFIER end_CELL end_ROW end_ARRAY 注意，虽然从上式中可以知道∑i=1wuisuperscriptsubscript𝑖1𝑤subscript𝑢𝑖\sum_{i=1}^{w}u_{i}∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT， ∑i=1wvisuperscriptsubscript𝑖1𝑤subscript𝑣𝑖\sum_{i=1}^{w}v_{i}∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT模p𝑝pitalic_p，q𝑞qitalic_q的值，但是我们真正的目标∑i=1w(ui+vi)superscriptsubscript𝑖1𝑤subscript𝑢𝑖subscript𝑣𝑖\sum_{i=1}^{w}(u_{i}+v_{i})∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT )需要的是没有做模运算以前的值。 假设 ∑i=1wui=(a−1x(modp))+tpsuperscriptsubscript𝑖1𝑤subscript𝑢𝑖annotatedsuperscript𝑎1𝑥pmod𝑝𝑡𝑝\displaystyle\sum_{i=1}^{w}u_{i}=(a^{-1}x\pmod{p})+tp∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x start_MODIFIER ( roman_mod start_ARG italic_p end_ARG ) end_MODIFIER ) + italic_t italic_p (1) ∑i=1wvi=(b−1y(modq))+sqsuperscriptsubscript𝑖1𝑤subscript𝑣𝑖annotatedsuperscript𝑏1𝑦pmod𝑞𝑠𝑞\displaystyle\sum_{i=1}^{w}v_{i}=(b^{-1}y\pmod{q})+sq∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y start_MODIFIER ( roman_mod start_ARG italic_q end_ARG ) end_MODIFIER ) + italic_s italic_q 则问题的关键在于求解t𝑡titalic_t, s𝑠sitalic_s。 由于ui 记M′=(a−1x(modp))+(b−1y(modq))superscript𝑀′annotatedsuperscript𝑎1𝑥pmod𝑝annotatedsuperscript𝑏1𝑦pmod𝑞M^{{}^{\prime}}=(a^{-1}x\pmod{p})+(b^{-1}y\pmod{q})italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x start_MODIFIER ( roman_mod start_ARG italic_p end_ARG ) end_MODIFIER ) + ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y start_MODIFIER ( roman_mod start_ARG italic_q end_ARG ) end_MODIFIER )，由等式(1)可知 ∑i=1w(ui+vi)superscriptsubscript𝑖1𝑤subscript𝑢𝑖subscript𝑣𝑖\displaystyle\sum_{i=1}^{w}(u_{i}+v_{i})∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) =(a−1x(modp))+(b−1y(modq))+tp+sqabsentannotatedsuperscript𝑎1𝑥pmod𝑝annotatedsuperscript𝑏1𝑦pmod𝑞𝑡𝑝𝑠𝑞\displaystyle=(a^{-1}x\pmod{p})+(b^{-1}y\pmod{q})+tp+sq= ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x start_MODIFIER ( roman_mod start_ARG italic_p end_ARG ) end_MODIFIER ) + ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y start_MODIFIER ( roman_mod start_ARG italic_q end_ARG ) end_MODIFIER ) + italic_t italic_p + italic_s italic_q (2) =M′+tp+sqabsentsuperscript𝑀′𝑡𝑝𝑠𝑞\displaystyle=M^{{}^{\prime}}+tp+sq= italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t italic_p + italic_s italic_q 由符号说明、加密过程有下述条件：“ui+visubscript𝑢𝑖subscript𝑣𝑖u_{i}+v_{i}italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT的查找区为0；∑i=1w(ui+vi)superscriptsubscript𝑖1𝑤subscript𝑢𝑖subscript𝑣𝑖\sum_{i=1}^{w}(u_{i}+v_{i})∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT )的明文区相加不会越界”，由此可知∑i=1w(ui+vi)superscriptsubscript𝑖1𝑤subscript𝑢𝑖subscript𝑣𝑖\sum_{i=1}^{w}(u_{i}+v_{i})∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT )的查找区为0。这是一个非常强的约束，可以用来检索t𝑡titalic_t和s𝑠sitalic_s是其取值范围[0,w)0𝑤[0,w)[ 0 , italic_w )中的哪一个值。前面章节中将查找区的大小定为α𝛼\alphaitalic_α比特，所以查找区能够区分2αsuperscript2𝛼2^{\alpha}2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT种情况。同时，w𝑤witalic_w的上限定为2α/2superscript2𝛼22^{\alpha/2}2 start_POSTSUPERSCRIPT italic_α / 2 end_POSTSUPERSCRIPT，则(t𝑡titalic_t，s𝑠sitalic_s)可能的取值一共有2αsuperscript2𝛼2^{\alpha}2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT种。所以查找区可以区分这些情况。不过，如果直接暴力搜索(t𝑡titalic_t，s𝑠sitalic_s)所有可能的取值，计算量太大了。 在讲解搜索方法之前，我们先回顾一下：我们是如何利用“竖式除法”计算“商”的。我们首先根据“被除数”的高位预估“商”的高位，然后将“商”的高位与除数相乘，再从“被除数”中减去刚刚计算的乘积。如此往复，不断的将“商”的所有位都计算出来。 我们再回到本算法中。将查找区等分成θ𝜃\thetaitalic_θ份小查找区，每份是μ𝜇\muitalic_μ比特，从高到低依次称为第0,1,…θ−1𝜃1\theta-1italic_θ - 1个小查找区。后续部分的思路为（参见Figure 1）： • 计算d𝑑ditalic_d使得M′+dsuperscript𝑀′𝑑M^{{}^{\prime}}+ditalic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_d的查找区为0，即为tp+sq𝑡𝑝𝑠𝑞tp+sqitalic_t italic_p + italic_s italic_q逼近的目标值。 • 寻找t0subscript𝑡0t_{0}italic_t start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT和s0subscript𝑠0s_{0}italic_s start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT使得“t0p+s0qsubscript𝑡0𝑝subscript𝑠0𝑞t_{0}p+s_{0}qitalic_t start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT italic_q和d𝑑ditalic_d的第0个小查找区相同”。 • 计算d=d−(t0p+s0q)𝑑𝑑subscript𝑡0𝑝subscript𝑠0𝑞d=d-(t_{0}p+s_{0}q)italic_d = italic_d - ( italic_t start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT italic_q )，注意此时d𝑑ditalic_d的第0个小查找区会被减为0。 • 后续循环进行（i从1开始）： 寻找tisubscript𝑡𝑖t_{i}italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT和sisubscript𝑠𝑖s_{i}italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT使得“tip+siqsubscript𝑡𝑖𝑝subscript𝑠𝑖𝑞t_{i}p+s_{i}qitalic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_q和d𝑑ditalic_d的第i个小查找区相同，且tip+siqsubscript𝑡𝑖𝑝subscript𝑠𝑖𝑞t_{i}p+s_{i}qitalic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_q的第0到i-1个小查找区都为0”。注意d𝑑ditalic_d的第0到i-1个小查找区已经在前序操作中被减为0。 • 计算d=d−(tip+siq)𝑑𝑑subscript𝑡𝑖𝑝subscript𝑠𝑖𝑞d=d-(t_{i}p+s_{i}q)italic_d = italic_d - ( italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_q )，注意此时d𝑑ditalic_d的第0个到i个小查找区会被减为0。 在上面的过程中，∑j=0i(tjp+sjq)superscriptsubscript𝑗0𝑖subscript𝑡𝑗𝑝subscript𝑠𝑗𝑞\sum_{j=0}^{i}(t_{j}p+s_{j}q)∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_i end_POSTSUPERSCRIPT ( italic_t start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT italic_q )的查找区逐渐逼近d，最初只有一个小查找区相同，直至完全相同。所以最后， M′+∑j=0θ−1(tjp+sjq)superscript𝑀′superscriptsubscript𝑗0𝜃1subscript𝑡𝑗𝑝subscript𝑠𝑗𝑞M^{{}^{\prime}}+\sum_{j=0}^{\theta-1}(t_{j}p+s_{j}q)italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT ( italic_t start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT italic_q )的查找区为0，即M′+(∑j=0θ−1tj)p+(∑j=0θ−1sj)qsuperscript𝑀′superscriptsubscript𝑗0𝜃1subscript𝑡𝑗𝑝superscriptsubscript𝑗0𝜃1subscript𝑠𝑗𝑞M^{{}^{\prime}}+(\sum_{j=0}^{\theta-1}t_{j})p+(\sum_{j=0}^{\theta-1}s_{j})qitalic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + ( ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_t start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ) italic_p + ( ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_s start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ) italic_q的查找区为0。 Figure 1: 查找区逐段逼近(θ=3𝜃3\theta=3italic_θ = 3) 此时我们找到了一组t𝑡titalic_t,s𝑠sitalic_s使得等式（2）中的“∑i=1w(ui+vi)superscriptsubscript𝑖1𝑤subscript𝑢𝑖subscript𝑣𝑖\sum_{i=1}^{w}(u_{i}+v_{i})∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT )的查找区为0”，但我们仍然有两个主要问题未解决。 第一个是“如何找到合适的tisubscript𝑡𝑖t_{i}italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT, sisubscript𝑠𝑖s_{i}italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT”。这个可以通过预计算一个查找表解决。该查找表为，针对小查找区的每一个取值，给出一组满足要求的tisubscript𝑡𝑖t_{i}italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT和sisubscript𝑠𝑖s_{i}italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT。因为小查找区只有μ𝜇\muitalic_μ比特，所以针对每个小查找区只需要2μsuperscript2𝜇2^{\mu}2 start_POSTSUPERSCRIPT italic_μ end_POSTSUPERSCRIPT个预计算表项。 第二个是“刚刚找到的(∑j=0θ−1tj,∑j=0θ−1sj)superscriptsubscript𝑗0𝜃1subscript𝑡𝑗superscriptsubscript𝑗0𝜃1subscript𝑠𝑗(\sum_{j=0}^{\theta-1}t_{j},\sum_{j=0}^{\theta-1}s_{j})( ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_t start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT , ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_s start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT )大概率不是目标的(t,s)𝑡𝑠(t,s)( italic_t , italic_s )”。其中一个现象可以帮助我们从侧面意识到这个问题，tθ−1subscript𝑡𝜃1t_{\theta-1}italic_t start_POSTSUBSCRIPT italic_θ - 1 end_POSTSUBSCRIPT和sθ−1subscript𝑠𝜃1s_{\theta-1}italic_s start_POSTSUBSCRIPT italic_θ - 1 end_POSTSUBSCRIPT需要拟合查找区的α𝛼\alphaitalic_α比特，则tθ−1subscript𝑡𝜃1t_{\theta-1}italic_t start_POSTSUBSCRIPT italic_θ - 1 end_POSTSUBSCRIPT和sθ−1subscript𝑠𝜃1s_{\theta-1}italic_s start_POSTSUBSCRIPT italic_θ - 1 end_POSTSUBSCRIPT大概率需要各为α/2𝛼2\alpha/2italic_α / 2比特；目标的t𝑡titalic_t和s𝑠sitalic_s要求小于w𝑤witalic_w，w𝑤witalic_w为密文相加的次数，实际情况中完全可以远小于2α/2superscript2𝛼22^{\alpha/2}2 start_POSTSUPERSCRIPT italic_α / 2 end_POSTSUPERSCRIPT。即，目标的(t,s)𝑡𝑠(t,s)( italic_t , italic_s )很有可能远小于(∑j=0θ−1tj,∑j=0θ−1sj)superscriptsubscript𝑗0𝜃1subscript𝑡𝑗superscriptsubscript𝑗0𝜃1subscript𝑠𝑗(\sum_{j=0}^{\theta-1}t_{j},\sum_{j=0}^{\theta-1}s_{j})( ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_t start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT , ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_s start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT )。记 tΔ=t−∑j=0θ−1tj;sΔ=s−∑j=0θ−1sjformulae-sequencesuperscript𝑡Δ𝑡superscriptsubscript𝑗0𝜃1subscript𝑡𝑗superscript𝑠Δ𝑠superscriptsubscript𝑗0𝜃1subscript𝑠𝑗\displaystyle t^{\Delta}=t-\sum_{j=0}^{\theta-1}t_{j};s^{\Delta}=s-\sum_{j=0}^% {\theta-1}s_{j}italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT = italic_t - ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_t start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ; italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT = italic_s - ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_s start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT (3) 因为M′+(∑j=0θ−1tj)p+(∑j=0θ−1sj)qsuperscript𝑀′superscriptsubscript𝑗0𝜃1subscript𝑡𝑗𝑝superscriptsubscript𝑗0𝜃1subscript𝑠𝑗𝑞M^{{}^{\prime}}+(\sum_{j=0}^{\theta-1}t_{j})p+(\sum_{j=0}^{\theta-1}s_{j})qitalic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + ( ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_t start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ) italic_p + ( ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_s start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT ) italic_q、 M′+tp+sqsuperscript𝑀′𝑡𝑝𝑠𝑞M^{{}^{\prime}}+tp+sqitalic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t italic_p + italic_s italic_q的查找区都为0，所以tΔp+sΔqsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞t^{\Delta}p+s^{\Delta}qitalic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q的查找区为0。依据这个，解决第二个问题的思路为： • 在预计算阶段寻找所有使得“tΔp+sΔqsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞t^{\Delta}p+s^{\Delta}qitalic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q的查找区为0”成立的tΔsuperscript𝑡Δt^{\Delta}italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT和sΔsuperscript𝑠Δs^{\Delta}italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT。 • 根据前述过程计算(∑j=0θ−1tj,∑j=0θ−1sj)superscriptsubscript𝑗0𝜃1subscript𝑡𝑗superscriptsubscript𝑗0𝜃1subscript𝑠𝑗(\sum_{j=0}^{\theta-1}t_{j},\sum_{j=0}^{\theta-1}s_{j})( ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_t start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT , ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_s start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT )。 • 根据预计算结果，寻找tΔsuperscript𝑡Δt^{\Delta}italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT和sΔsuperscript𝑠Δs^{\Delta}italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT，使得t=tΔ+∑j=0θ−1tj𝑡superscript𝑡Δsuperscriptsubscript𝑗0𝜃1subscript𝑡𝑗t=t^{\Delta}+\sum_{j=0}^{\theta-1}t_{j}italic_t = italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_t start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT,s=sΔ+∑j=0θ−1sj𝑠superscript𝑠Δsuperscriptsubscript𝑗0𝜃1subscript𝑠𝑗s=s^{\Delta}+\sum_{j=0}^{\theta-1}s_{j}italic_s = italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_s start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT满足t∈[0,w),s∈[0,w)formulae-sequence𝑡0𝑤𝑠0𝑤t\in[0,w),s\in[0,w)italic_t ∈ [ 0 , italic_w ) , italic_s ∈ [ 0 , italic_w ) 为了方便理解整体过程，前述的部分措辞并不严谨，比如一些“查找区为0”实际上为“查找区为0或者一些特定的值”。下面给出精准描述。 4.2 预计算 T[i][j]𝑇delimited-[]𝑖delimited-[]𝑗T[i][j]italic_T [ italic_i ] [ italic_j ]是第一张预计算表，即“解密思路”章节用于寻找tisubscript𝑡𝑖t_{i}italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT和sisubscript𝑠𝑖s_{i}italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT的查找表。其第一个维度是θ𝜃\thetaitalic_θ，第二个维度是2μsuperscript2𝜇2^{\mu}2 start_POSTSUPERSCRIPT italic_μ end_POSTSUPERSCRIPT (参见Figure 2)。 表元素T[i][j]𝑇delimited-[]𝑖delimited-[]𝑗T[i][j]italic_T [ italic_i ] [ italic_j ] 是一个三元组结构(t,s,e)𝑡𝑠𝑒(t,s,e)( italic_t , italic_s , italic_e ), t𝑡titalic_t和s𝑠sitalic_s是正整数，e=(tp+sq)0:ρ+η+α𝑒subscript𝑡𝑝𝑠𝑞:0𝜌𝜂𝛼e=(tp+sq)_{0:\rho+\eta+\alpha}italic_e = ( italic_t italic_p + italic_s italic_q ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT。e𝑒eitalic_e只取低位是因为在解密过程中高位没有用处。 整个查找区等分成θ𝜃\thetaitalic_θ个小查找区，T[i][j]𝑇delimited-[]𝑖delimited-[]𝑗T[i][j]italic_T [ italic_i ] [ italic_j ]用于搜索第i𝑖iitalic_i个小查找区，进一步地，T[i][j]𝑇delimited-[]𝑖delimited-[]𝑗T[i][j]italic_T [ italic_i ] [ italic_j ]用于存第i𝑖iitalic_i个小查找区值为j𝑗jitalic_j的项。即 T[i][j].eρ+η+α−μ(i+1):ρ+η+α=jformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗subscript𝑒:𝜌𝜂𝛼𝜇𝑖1𝜌𝜂𝛼𝑗T[i][j].e_{\rho+\eta+\alpha-\mu(i+1):\rho+\eta+\alpha}=jitalic_T [ italic_i ] [ italic_j ] . italic_e start_POSTSUBSCRIPT italic_ρ + italic_η + italic_α - italic_μ ( italic_i + 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = italic_j (4) 其中 i∈[0,θ−1]𝑖0𝜃1i\in[0,\theta-1]italic_i ∈ [ 0 , italic_θ - 1 ], j∈[0,2μ−1]𝑗0superscript2𝜇1j\in[0,2^{\mu}-1]italic_j ∈ [ 0 , 2 start_POSTSUPERSCRIPT italic_μ end_POSTSUPERSCRIPT - 1 ]。 ρ+η+α−μ(i+1):ρ+η+α:𝜌𝜂𝛼𝜇𝑖1𝜌𝜂𝛼\rho+\eta+\alpha-\mu(i+1):\rho+\eta+\alphaitalic_ρ + italic_η + italic_α - italic_μ ( italic_i + 1 ) : italic_ρ + italic_η + italic_α表示的就是第0到第i𝑖iitalic_i个小查找区。上式值为j𝑗jitalic_j，实际上只有第i𝑖iitalic_i个小查找区有非0的值，其他的都为0。 Figure 2: 表T结构(μ=8𝜇8\mu=8italic_μ = 8, θ=3𝜃3\theta=3italic_θ = 3) 此外，要寻找位宽尽可能小的t𝑡titalic_t和s𝑠sitalic_s作为预计算结果。这会使得“解密思路”章节中的(∑j=0θ−1tj,∑j=0θ−1sj)superscriptsubscript𝑗0𝜃1subscript𝑡𝑗superscriptsubscript𝑗0𝜃1subscript𝑠𝑗(\sum_{j=0}^{\theta-1}t_{j},\sum_{j=0}^{\theta-1}s_{j})( ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_t start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT , ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_s start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT )尽可能的小，从而使得“解密思路”章节中的tΔsuperscript𝑡Δt^{\Delta}italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT和sΔsuperscript𝑠Δs^{\Delta}italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT可能的取值范围尽可能的小。 一般来说，T[i][j]𝑇delimited-[]𝑖delimited-[]𝑗T[i][j]italic_T [ italic_i ] [ italic_j ]拟合的查找区长度为(i+1)μ𝑖1𝜇(i+1)\mu( italic_i + 1 ) italic_μ，所以它的t𝑡titalic_t和s𝑠sitalic_s的比特数小于或略超过(i+1)μ/2𝑖1𝜇2(i+1)\mu/2( italic_i + 1 ) italic_μ / 2，实测中一般最多超过1到2个比特。记所有t𝑡titalic_t和s𝑠sitalic_s的最大比特数为κ𝜅\kappaitalic_κ，κ𝜅\kappaitalic_κ一般为α/2+1𝛼21\alpha/2+1italic_α / 2 + 1或α/2+2𝛼22\alpha/2+2italic_α / 2 + 2。在密钥生成的时候，我们可以筛选合适的p𝑝pitalic_p和q𝑞qitalic_q，使得κ=α/2+1𝜅𝛼21\kappa=\alpha/2+1italic_κ = italic_α / 2 + 1。 R[j]𝑅delimited-[]𝑗R[j]italic_R [ italic_j ]是第二张预计算表，即“解密思路”章节用于寻找tΔsuperscript𝑡Δt^{\Delta}italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT和sΔsuperscript𝑠Δs^{\Delta}italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT的查找表。它是一个一维数组。表元素也是与T𝑇Titalic_T一样的三元组结构(t,s,e)𝑡𝑠𝑒(t,s,e)( italic_t , italic_s , italic_e )。表R𝑅Ritalic_R包含所有满足下列条件的三元组: • eρ+η:ρ+η+α=0subscript𝑒:𝜌𝜂𝜌𝜂𝛼0e_{\rho+\eta:\rho+\eta+\alpha}=0italic_e start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0或1111或2α−1superscript2𝛼12^{\alpha}-12 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1或2α−2superscript2𝛼22^{\alpha}-22 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 2 • t∈[−2κ+1,2κ+1]𝑡superscript2𝜅1superscript2𝜅1t\in[-2^{\kappa+1},2^{\kappa+1}]italic_t ∈ [ - 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT , 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT ], s∈[−2κ+1,2κ+1]𝑠superscript2𝜅1superscript2𝜅1s\in[-2^{\kappa+1},2^{\kappa+1}]italic_s ∈ [ - 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT , 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT ] eρ+η:ρ+η+αsubscript𝑒:𝜌𝜂𝜌𝜂𝛼e_{\rho+\eta:\rho+\eta+\alpha}italic_e start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT的取值是我们经过详细分析后得出的，参见“解密正确性说明”。 另外，需要为表R𝑅Ritalic_R建立索引，以使得根据t𝑡titalic_t、s𝑠sitalic_s两个元素的范围要求，能够快速找到对应的表项，具体建立方法参见“关键实现方法”章节。 4.3 实时计算 假设密文(x,y)𝑥𝑦(x,y)( italic_x , italic_y )（对应明文记为m𝑚mitalic_m，对应明文的秘密分享记为u𝑢uitalic_u，v𝑣vitalic_v）是由 (x1,y1)subscript𝑥1subscript𝑦1(x_{1},y_{1})( italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT )，(x2,y2)subscript𝑥2subscript𝑦2(x_{2},y_{2})( italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT )，…，(xw,yw)subscript𝑥𝑤subscript𝑦𝑤(x_{w},y_{w})( italic_x start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT )相加得来的（对应的明文记为m1subscript𝑚1m_{1}italic_m start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，m2subscript𝑚2m_{2}italic_m start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，mwsubscript𝑚𝑤m_{w}italic_m start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT，对应的秘密分享分别为u1subscript𝑢1u_{1}italic_u start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，u2subscript𝑢2u_{2}italic_u start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，uwsubscript𝑢𝑤u_{w}italic_u start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT，v1subscript𝑣1v_{1}italic_v start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，v2subscript𝑣2v_{2}italic_v start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，vwsubscript𝑣𝑤v_{w}italic_v start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT）。记 M′=(a−1x(modp))+(b−1y(modq))superscript𝑀′annotatedsuperscript𝑎1𝑥pmod𝑝annotatedsuperscript𝑏1𝑦pmod𝑞M^{{}^{\prime}}=(a^{-1}x\pmod{p})+(b^{-1}y\pmod{q})italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x start_MODIFIER ( roman_mod start_ARG italic_p end_ARG ) end_MODIFIER ) + ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y start_MODIFIER ( roman_mod start_ARG italic_q end_ARG ) end_MODIFIER )。 由“解密思路”章节可知（等式(2)），解密的关键是找到t𝑡titalic_t和s𝑠sitalic_s，使得： (M′+tp+sq)ρ+η:ρ+η+α=0subscriptsuperscript𝑀′𝑡𝑝𝑠𝑞:𝜌𝜂𝜌𝜂𝛼0\displaystyle(M^{{}^{\prime}}+tp+sq)_{\rho+\eta:\rho+\eta+\alpha}=0( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t italic_p + italic_s italic_q ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0 (5) t∈[0,w),s∈[0,w)formulae-sequence𝑡0𝑤𝑠0𝑤\displaystyle t\in[0,w),s\in[0,w)italic_t ∈ [ 0 , italic_w ) , italic_s ∈ [ 0 , italic_w ) 具体算法参见Algorithm 1。每个步骤的含义如下： 第2步求的d𝑑ditalic_d，即tp+sq𝑡𝑝𝑠𝑞tp+sqitalic_t italic_p + italic_s italic_q目标拟合的值。 从第3步到第9步是一个循环。循环的每一轮，寻找恰当的T[i][j].tformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑡T[i][j].titalic_T [ italic_i ] [ italic_j ] . italic_t和T[i][j].sformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑠T[i][j].sitalic_T [ italic_i ] [ italic_j ] . italic_s，使得T[i][j].tp+T[i][j].sqformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑡𝑝𝑇delimited-[]𝑖delimited-[]𝑗𝑠𝑞T[i][j].tp+T[i][j].sqitalic_T [ italic_i ] [ italic_j ] . italic_t italic_p + italic_T [ italic_i ] [ italic_j ] . italic_s italic_q和d𝑑ditalic_d的前i+1𝑖1i+1italic_i + 1个小查找区相同。然后将T[i][j].tformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑡T[i][j].titalic_T [ italic_i ] [ italic_j ] . italic_t和T[i][j].sformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑠T[i][j].sitalic_T [ italic_i ] [ italic_j ] . italic_s分别放到累加变量t𝑡titalic_t和s𝑠sitalic_s里，且从d𝑑ditalic_d中减去T[i][j].tp+T[i][j].sqformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑡𝑝𝑇delimited-[]𝑖delimited-[]𝑗𝑠𝑞T[i][j].tp+T[i][j].sqitalic_T [ italic_i ] [ italic_j ] . italic_t italic_p + italic_T [ italic_i ] [ italic_j ] . italic_s italic_q，即减去T[i][j].eformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑒T[i][j].eitalic_T [ italic_i ] [ italic_j ] . italic_e。这里有一个特殊情况，因为上面那个减法有可能导致d𝑑ditalic_d为负数。所以，算法中使用ϕitalic-ϕ\phiitalic_ϕ表示d𝑑ditalic_d的正负，且当d𝑑ditalic_d为负数的时候，不再“从d𝑑ditalic_d中减去T[i][j].tp+T[i][j].sqformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑡𝑝𝑇delimited-[]𝑖delimited-[]𝑗𝑠𝑞T[i][j].tp+T[i][j].sqitalic_T [ italic_i ] [ italic_j ] . italic_t italic_p + italic_T [ italic_i ] [ italic_j ] . italic_s italic_q”，而是将T[i][j].tp+T[i][j].sqformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑡𝑝𝑇delimited-[]𝑖delimited-[]𝑗𝑠𝑞T[i][j].tp+T[i][j].sqitalic_T [ italic_i ] [ italic_j ] . italic_t italic_p + italic_T [ italic_i ] [ italic_j ] . italic_s italic_q累加到d𝑑ditalic_d上，从而消去d𝑑ditalic_d当前最高的小反查找区。 第10步时，t𝑡titalic_t和s𝑠sitalic_s的值相当于“解密思路”章节中的(∑j=0θ−1tj(\sum_{j=0}^{\theta-1}t_{j}( ∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_t start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT和∑j=0θ−1sj)\sum_{j=0}^{\theta-1}s_{j})∑ start_POSTSUBSCRIPT italic_j = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_s start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT )。第10步则开始进行“解密思路”章节中根据预计算结果的寻找tΔsuperscript𝑡Δt^{\Delta}italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT和sΔsuperscript𝑠Δs^{\Delta}italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT工作。具体地，因为公式（5）中的t𝑡titalic_t, s𝑠sitalic_s有确定的范围，可以根据该范围确定 tΔsuperscript𝑡Δt^{\Delta}italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT和sΔsuperscript𝑠Δs^{\Delta}italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT的范围，即算法中R[j].tformulae-sequence𝑅delimited-[]𝑗𝑡R[j].titalic_R [ italic_j ] . italic_t和R[j].sformulae-sequence𝑅delimited-[]𝑗𝑠R[j].sitalic_R [ italic_j ] . italic_s的范围。再根据该范围从预计算表中把相应的表项筛出来。后续“关键实现方法”会说明筛出来的表项仅有几个。 第11步到第14步是按照公式（5）再做筛选。要说明的是，此时直接按照公式（5）对所有候选项进行计算也是可以的。算法中的方法更为的精巧和高效，其正确性参见“解密正确性”章节。 第15步做最后的筛选，一旦有多对(t𝑡titalic_t,s𝑠sitalic_s)满足公式（5）。则与它们期望w/2𝑤2w/2italic_w / 2最近的一组会被选中。 Input: w𝑤witalic_w, M′superscript𝑀′M^{{}^{\prime}}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT, p𝑝pitalic_p, q𝑞qitalic_q, T𝑇Titalic_T, R𝑅Ritalic_R Output: m𝑚mitalic_m 1 Signed int t=0,s=0formulae-sequence𝑡0𝑠0t=0,s=0italic_t = 0 , italic_s = 0, List E=[]𝐸E=[]italic_E = [ ] 2 d=(2ρ+η+α−M0:ρ+η+α′)0:ρ+η+α𝑑subscriptsuperscript2𝜌𝜂𝛼subscriptsuperscript𝑀′:0𝜌𝜂𝛼:0𝜌𝜂𝛼d=(2^{\rho+\eta+\alpha}-M^{{}^{\prime}}_{0:\rho+\eta+\alpha})_{0:\rho+\eta+\alpha}italic_d = ( 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT - italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT 3 for i = 0 to θ−1𝜃1\theta-1italic_θ - 1 do 4 ϕ=(d>0)?1:−1:italic-ϕ𝑑0?11\phi=(d>0)?1:-1italic_ϕ = ( italic_d > 0 ) ? 1 : - 1 5 寻找j𝑗jitalic_j，使得ϕ*T[i][j].eρ+η+μ(θ−i−1):ρ+η+α=|dρ+η+μ(θ−i−1):ρ+η+α|formulae-sequenceitalic-ϕ𝑇delimited-[]𝑖delimited-[]𝑗subscript𝑒:𝜌𝜂𝜇𝜃𝑖1𝜌𝜂𝛼subscript𝑑:𝜌𝜂𝜇𝜃𝑖1𝜌𝜂𝛼\phi*T[i][j].e_{\rho+\eta+\mu(\theta-i-1):\rho+\eta+\alpha}=\left|d_{\rho+\eta% +\mu(\theta-i-1):\rho+\eta+\alpha}\right|italic_ϕ * italic_T [ italic_i ] [ italic_j ] . italic_e start_POSTSUBSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_i - 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = | italic_d start_POSTSUBSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_i - 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT |； 6 d=d−ϕ*T[i][j].eformulae-sequence𝑑𝑑italic-ϕ𝑇delimited-[]𝑖delimited-[]𝑗𝑒d=d-\phi*T[i][j].eitalic_d = italic_d - italic_ϕ * italic_T [ italic_i ] [ italic_j ] . italic_e; 7 t=t+ϕ*T[i][j].tformulae-sequence𝑡𝑡italic-ϕ𝑇delimited-[]𝑖delimited-[]𝑗𝑡t=t+\phi*T[i][j].titalic_t = italic_t + italic_ϕ * italic_T [ italic_i ] [ italic_j ] . italic_t; 8 s=s+ϕ*T[i][j].sformulae-sequence𝑠𝑠italic-ϕ𝑇delimited-[]𝑖delimited-[]𝑗𝑠s=s+\phi*T[i][j].sitalic_s = italic_s + italic_ϕ * italic_T [ italic_i ] [ italic_j ] . italic_s; 9 10 end for 11根据R𝑅Ritalic_R的索引，将所有符合t+R[j].t∈[0,2α/2)formulae-sequence𝑡𝑅delimited-[]𝑗𝑡0superscript2𝛼2t+R[j].t\in[0,2^{\alpha/2})italic_t + italic_R [ italic_j ] . italic_t ∈ [ 0 , 2 start_POSTSUPERSCRIPT italic_α / 2 end_POSTSUPERSCRIPT )，s+R[j].s∈[0,2α/2)formulae-sequence𝑠𝑅delimited-[]𝑗𝑠0superscript2𝛼2s+R[j].s\in[0,2^{\alpha/2})italic_s + italic_R [ italic_j ] . italic_s ∈ [ 0 , 2 start_POSTSUPERSCRIPT italic_α / 2 end_POSTSUPERSCRIPT )的j𝑗jitalic_j加入列表A𝐴Aitalic_A； for j∈A𝑗𝐴j\in Aitalic_j ∈ italic_A do 12 if (R[j].e−d≥ 0and(R[j].e−d)ρ+η:ρ+η+α=0)or(R[j].e−d<0and(d−R[j].e−1)ρ+η:ρ+η+α=2α−1)(R[j].e-d\ \geq\ 0\ \textbf{and}\ (R[j].e-d)_{\rho+\eta:\rho+\eta+\alpha}=0)\ % \textbf{or}\ (R[j].e-d<0\ \textbf{and}\ (d-R[j].e-1)_{\rho+\eta:\rho+\eta+% \alpha}=2^{\alpha}-1)( italic_R [ italic_j ] . italic_e - italic_d ≥ 0 and ( italic_R [ italic_j ] . italic_e - italic_d ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0 ) or ( italic_R [ italic_j ] . italic_e - italic_d < 0 and ( italic_d - italic_R [ italic_j ] . italic_e - 1 ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1 ) then 13 E.append(t+R[j].t,s+R[j].s)E.append(t+R[j].t,s+R[j].s)italic_E . italic_a italic_p italic_p italic_e italic_n italic_d ( italic_t + italic_R [ italic_j ] . italic_t , italic_s + italic_R [ italic_j ] . italic_s ); 14 15 end for 16从E𝐸Eitalic_E中选择数值与(w/2𝑤2w/2italic_w / 2, w/2𝑤2w/2italic_w / 2)最接近的元素作为所求的(t,s)𝑡𝑠(t,s)( italic_t , italic_s ) m=(M′+tp+sq)ρ:ρ+η−w𝑚subscriptsuperscript𝑀′𝑡𝑝𝑠𝑞:𝜌𝜌𝜂𝑤m=(M^{{}^{\prime}}+tp+sq)_{\rho:\rho+\eta}-witalic_m = ( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t italic_p + italic_s italic_q ) start_POSTSUBSCRIPT italic_ρ : italic_ρ + italic_η end_POSTSUBSCRIPT - italic_w Algorithm 1 Decryption 5 解密正确性证明 记上述算法第3步至9步循环中，第5步d𝑑ditalic_d的值记为disubscript𝑑𝑖d_{i}italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT，即，到达第7步时，d𝑑ditalic_d的值为di+1subscript𝑑𝑖1d_{i+1}italic_d start_POSTSUBSCRIPT italic_i + 1 end_POSTSUBSCRIPT；第7、8步中的T[i][j].tformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑡T[i][j].titalic_T [ italic_i ] [ italic_j ] . italic_t，T[i][j].sformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑠T[i][j].sitalic_T [ italic_i ] [ italic_j ] . italic_s，T[i][j].eformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑒T[i][j].eitalic_T [ italic_i ] [ italic_j ] . italic_e记为tisubscript𝑡𝑖t_{i}italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT，sisubscript𝑠𝑖s_{i}italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT，eisubscript𝑒𝑖e_{i}italic_e start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT；第5步ϕitalic-ϕ\phiitalic_ϕ的值记为ϕisubscriptitalic-ϕ𝑖\phi_{i}italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT 引理1： 算法第3步到第9步能够实现“解密思路”中第00到i𝑖iitalic_i个小查找区为00，即 |(di)|<2ρ+η+μ(θ−i),i∈[0,θ]formulae-sequencesubscript𝑑𝑖superscript2𝜌𝜂𝜇𝜃𝑖𝑖0𝜃\left|(d_{i})\right|<2^{\rho+\eta+\mu(\theta-i)},i\in[0,\theta]| ( italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) | < 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_i ) end_POSTSUPERSCRIPT , italic_i ∈ [ 0 , italic_θ ] Proof. 下面根据数学归纳法进行证明。 当i=0𝑖0i=0italic_i = 0时，显然成立。 假设i=z𝑖𝑧i=zitalic_i = italic_z时成立，即|(dz)|<2ρ+η+μ(θ−z)subscript𝑑𝑧superscript2𝜌𝜂𝜇𝜃𝑧\left|(d_{z})\right|<2^{\rho+\eta+\mu(\theta-z)}| ( italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) | < 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_z ) end_POSTSUPERSCRIPT，下面证明i=z+1𝑖𝑧1i=z+1italic_i = italic_z + 1时成立，即|(dz+1)|<2ρ+η+μ(θ−(z+1))subscript𝑑𝑧1superscript2𝜌𝜂𝜇𝜃𝑧1\left|(d_{z+1})\right|<2^{\rho+\eta+\mu(\theta-(z+1))}| ( italic_d start_POSTSUBSCRIPT italic_z + 1 end_POSTSUBSCRIPT ) | < 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - ( italic_z + 1 ) ) end_POSTSUPERSCRIPT。 由算法第4至8步可知 dz+1={dz−ez,dz≥0dz+ez,dz<0subscript𝑑𝑧1casessubscript𝑑𝑧subscript𝑒𝑧subscript𝑑𝑧0subscript𝑑𝑧subscript𝑒𝑧subscript𝑑𝑧0d_{z+1}=\left\{\begin{array}[]{l}d_{z}-e_{z},\qquad d_{z}\geq 0\\ d_{z}+e_{z},\qquad d_{z}<0\end{array}\right.italic_d start_POSTSUBSCRIPT italic_z + 1 end_POSTSUBSCRIPT = { start_ARRAY start_ROW start_CELL italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT - italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT , italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ≥ 0 end_CELL end_ROW start_ROW start_CELL italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT + italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT , italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT < 0 end_CELL end_ROW end_ARRAY 根据预计算章节，可知ezsubscript𝑒𝑧e_{z}italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT只有ρ+η+α𝜌𝜂𝛼\rho+\eta+\alphaitalic_ρ + italic_η + italic_α个比特，则 ez=(ez)0:ρ+η+μ(θ−z−1)+(ez)ρ+η+μ(θ−z−1):ρ+η+α¯subscript𝑒𝑧subscriptsubscript𝑒𝑧:0𝜌𝜂𝜇𝜃𝑧1subscriptsubscript𝑒𝑧¯:𝜌𝜂𝜇𝜃𝑧1𝜌𝜂𝛼e_{z}=(e_{z})_{0:\rho+\eta+\mu(\theta-z-1)}+(e_{z})_{\overline{\rho+\eta+\mu(% \theta-z-1):\rho+\eta+\alpha}}italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT = ( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) end_POSTSUBSCRIPT + ( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) : italic_ρ + italic_η + italic_α end_ARG end_POSTSUBSCRIPT；并且ezsubscript𝑒𝑧e_{z}italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT为正数。 由算法第5步可知 (ez)ρ+η+μ(θ−z−1):ρ+η+α=|(dz)ρ+η+μ(θ−z−1):ρ+η+α|subscriptsubscript𝑒𝑧:𝜌𝜂𝜇𝜃𝑧1𝜌𝜂𝛼subscriptsubscript𝑑𝑧:𝜌𝜂𝜇𝜃𝑧1𝜌𝜂𝛼(e_{z})_{\rho+\eta+\mu(\theta-z-1):\rho+\eta+\alpha}=\left|(d_{z})_{\rho+\eta+% \mu(\theta-z-1):\rho+\eta+\alpha}\right|( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = | ( italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT | (6) 当dz≥0subscript𝑑𝑧0d_{z}\geq 0italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ≥ 0时，有(ez)ρ+η+μ(θ−z−1):ρ+η+α=(dz)ρ+η+μ(θ−z−1):ρ+η+αsubscriptsubscript𝑒𝑧:𝜌𝜂𝜇𝜃𝑧1𝜌𝜂𝛼subscriptsubscript𝑑𝑧:𝜌𝜂𝜇𝜃𝑧1𝜌𝜂𝛼(e_{z})_{\rho+\eta+\mu(\theta-z-1):\rho+\eta+\alpha}=(d_{z})_{\rho+\eta+\mu(% \theta-z-1):\rho+\eta+\alpha}( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = ( italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT,则 dz+1subscript𝑑𝑧1\displaystyle d_{z+1}italic_d start_POSTSUBSCRIPT italic_z + 1 end_POSTSUBSCRIPT =dz−ezabsentsubscript𝑑𝑧subscript𝑒𝑧\displaystyle=d_{z}-e_{z}= italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT - italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT =(dz)0:ρ+η+μ(θ−z−1)+(dz)ρ+η+μ(θ−z−1):ρ+η+α¯absentsubscriptsubscript𝑑𝑧:0𝜌𝜂𝜇𝜃𝑧1subscriptsubscript𝑑𝑧¯:𝜌𝜂𝜇𝜃𝑧1𝜌𝜂𝛼\displaystyle=(d_{z})_{0:\rho+\eta+\mu(\theta-z-1)}+(d_{z})_{\overline{\rho+% \eta+\mu(\theta-z-1):\rho+\eta+\alpha}}= ( italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) end_POSTSUBSCRIPT + ( italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) : italic_ρ + italic_η + italic_α end_ARG end_POSTSUBSCRIPT −[(ez)0:ρ+η+μ(θ−z−1)+(ez)ρ+η+μ(θ−z−1):ρ+η+α¯]delimited-[]subscriptsubscript𝑒𝑧:0𝜌𝜂𝜇𝜃𝑧1subscriptsubscript𝑒𝑧¯:𝜌𝜂𝜇𝜃𝑧1𝜌𝜂𝛼\displaystyle-[(e_{z})_{0:\rho+\eta+\mu(\theta-z-1)}+(e_{z})_{\overline{\rho+% \eta+\mu(\theta-z-1):\rho+\eta+\alpha}}]- [ ( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) end_POSTSUBSCRIPT + ( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) : italic_ρ + italic_η + italic_α end_ARG end_POSTSUBSCRIPT ] =(dz)0:ρ+η+μ(θ−z−1)−(ez)0:ρ+η+μ(θ−z−1)absentsubscriptsubscript𝑑𝑧:0𝜌𝜂𝜇𝜃𝑧1subscriptsubscript𝑒𝑧:0𝜌𝜂𝜇𝜃𝑧1\displaystyle=(d_{z})_{0:\rho+\eta+\mu(\theta-z-1)}-(e_{z})_{0:\rho+\eta+\mu(% \theta-z-1)}= ( italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) end_POSTSUBSCRIPT - ( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) end_POSTSUBSCRIPT 上式最后两项都为正数，则|(dz+1)|<2ρ+η+μ(θ−z−1)subscript𝑑𝑧1superscript2𝜌𝜂𝜇𝜃𝑧1\left|(d_{z+1})\right|<2^{\rho+\eta+\mu(\theta-z-1)}| ( italic_d start_POSTSUBSCRIPT italic_z + 1 end_POSTSUBSCRIPT ) | < 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) end_POSTSUPERSCRIPT。 当dz<0subscript𝑑𝑧0d_{z}<0italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT < 0时，有(ez)ρ+η+μ(θ−z−1):ρ+η+α=−(dz)ρ+η+μ(θ−z−1):ρ+η+αsubscriptsubscript𝑒𝑧:𝜌𝜂𝜇𝜃𝑧1𝜌𝜂𝛼subscriptsubscript𝑑𝑧:𝜌𝜂𝜇𝜃𝑧1𝜌𝜂𝛼(e_{z})_{\rho+\eta+\mu(\theta-z-1):\rho+\eta+\alpha}=-(d_{z})_{\rho+\eta+\mu(% \theta-z-1):\rho+\eta+\alpha}( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = - ( italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT，则有 dz+1subscript𝑑𝑧1\displaystyle d_{z+1}italic_d start_POSTSUBSCRIPT italic_z + 1 end_POSTSUBSCRIPT =dz+(ez)0:ρ+η+αabsentsubscript𝑑𝑧subscriptsubscript𝑒𝑧:0𝜌𝜂𝛼\displaystyle=d_{z}+(e_{z})_{0:\rho+\eta+\alpha}= italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT + ( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT =(dz)0:ρ+η+μ(θ−z−1)+(dz)ρ+η+μ(θ−z−1):ρ+η+α¯absentsubscriptsubscript𝑑𝑧:0𝜌𝜂𝜇𝜃𝑧1subscriptsubscript𝑑𝑧¯:𝜌𝜂𝜇𝜃𝑧1𝜌𝜂𝛼\displaystyle=(d_{z})_{0:\rho+\eta+\mu(\theta-z-1)}+(d_{z})_{\overline{\rho+% \eta+\mu(\theta-z-1):\rho+\eta+\alpha}}= ( italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) end_POSTSUBSCRIPT + ( italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) : italic_ρ + italic_η + italic_α end_ARG end_POSTSUBSCRIPT +[(ez)0:ρ+η+μ(θ−z−1)+(ez)ρ+η+μ(θ−z−1):ρ+η+α¯]delimited-[]subscriptsubscript𝑒𝑧:0𝜌𝜂𝜇𝜃𝑧1subscriptsubscript𝑒𝑧¯:𝜌𝜂𝜇𝜃𝑧1𝜌𝜂𝛼\displaystyle+[(e_{z})_{0:\rho+\eta+\mu(\theta-z-1)}+(e_{z})_{\overline{\rho+% \eta+\mu(\theta-z-1):\rho+\eta+\alpha}}]+ [ ( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) end_POSTSUBSCRIPT + ( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) : italic_ρ + italic_η + italic_α end_ARG end_POSTSUBSCRIPT ] =(dz)0:ρ+η+μ(θ−z−1)+(ez)0:ρ+η+μ(θ−z−1)absentsubscriptsubscript𝑑𝑧:0𝜌𝜂𝜇𝜃𝑧1subscriptsubscript𝑒𝑧:0𝜌𝜂𝜇𝜃𝑧1\displaystyle=(d_{z})_{0:\rho+\eta+\mu(\theta-z-1)}+(e_{z})_{0:\rho+\eta+\mu(% \theta-z-1)}= ( italic_d start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) end_POSTSUBSCRIPT + ( italic_e start_POSTSUBSCRIPT italic_z end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) end_POSTSUBSCRIPT 上式最后两项为一正一负，则|(dz+1)|<2ρ+η+μ(θ−z−1)subscript𝑑𝑧1superscript2𝜌𝜂𝜇𝜃𝑧1\left|(d_{z+1})\right|<2^{\rho+\eta+\mu(\theta-z-1)}| ( italic_d start_POSTSUBSCRIPT italic_z + 1 end_POSTSUBSCRIPT ) | < 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_μ ( italic_θ - italic_z - 1 ) end_POSTSUPERSCRIPT。 则i=z+1𝑖𝑧1i=z+1italic_i = italic_z + 1时成立，由数学归纳法得知对于所有的i𝑖iitalic_i都成立。 ∎ 引理2： (M0:ρ+η+α′+d0)0:ρ+η+α=0subscriptsubscriptsuperscript𝑀′:0𝜌𝜂𝛼subscript𝑑0:0𝜌𝜂𝛼0(M^{{}^{\prime}}_{0:\rho+\eta+\alpha}+d_{0})_{0:\rho+\eta+\alpha}=0( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + italic_d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0 Proof. 根据上述算法第2步的式子，记dmin=2ρ+η+α−M0:ρ+η+α′subscript𝑑𝑚𝑖𝑛superscript2𝜌𝜂𝛼subscriptsuperscript𝑀′:0𝜌𝜂𝛼d_{min}=2^{\rho+\eta+\alpha}-M^{{}^{\prime}}_{0:\rho+\eta+\alpha}italic_d start_POSTSUBSCRIPT italic_m italic_i italic_n end_POSTSUBSCRIPT = 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT - italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT，则d0=(dmin)0:ρ+η+αsubscript𝑑0subscriptsubscript𝑑𝑚𝑖𝑛:0𝜌𝜂𝛼d_{0}=(d_{min})_{0:\rho+\eta+\alpha}italic_d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT = ( italic_d start_POSTSUBSCRIPT italic_m italic_i italic_n end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT。 由于M′≥0superscript𝑀′0M^{{}^{\prime}}\geq 0italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ≥ 0, 故M0:ρ+η+α′∈[0,2ρ+η+α−1]subscriptsuperscript𝑀′:0𝜌𝜂𝛼0superscript2𝜌𝜂𝛼1M^{{}^{\prime}}_{0:\rho+\eta+\alpha}\in[0,2^{\rho+\eta+\alpha}-1]italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT ∈ [ 0 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT - 1 ] 当M0:ρ+η+α′=0subscriptsuperscript𝑀′:0𝜌𝜂𝛼0M^{{}^{\prime}}_{0:\rho+\eta+\alpha}=0italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0时，d0=0subscript𝑑00d_{0}=0italic_d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT = 0，从而d0+M0:ρ+η+α′=0subscript𝑑0subscriptsuperscript𝑀′:0𝜌𝜂𝛼0d_{0}+M^{{}^{\prime}}_{0:\rho+\eta+\alpha}=0italic_d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT + italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0; 当M0:ρ+η+α′∈(0,2ρ+η+α−1]subscriptsuperscript𝑀′:0𝜌𝜂𝛼0superscript2𝜌𝜂𝛼1M^{{}^{\prime}}_{0:\rho+\eta+\alpha}\in(0,2^{\rho+\eta+\alpha}-1]italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT ∈ ( 0 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT - 1 ]时，dmin∈[1,2ρ+η+α−1]subscript𝑑𝑚𝑖𝑛1superscript2𝜌𝜂𝛼1d_{min}\in[1,2^{\rho+\eta+\alpha}-1]italic_d start_POSTSUBSCRIPT italic_m italic_i italic_n end_POSTSUBSCRIPT ∈ [ 1 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT - 1 ], 从而d0=dminsubscript𝑑0subscript𝑑𝑚𝑖𝑛d_{0}=d_{min}italic_d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT = italic_d start_POSTSUBSCRIPT italic_m italic_i italic_n end_POSTSUBSCRIPT,从而 d0+M0:ρ+η+α′=2ρ+η+αsubscript𝑑0subscriptsuperscript𝑀′:0𝜌𝜂𝛼superscript2𝜌𝜂𝛼d_{0}+M^{{}^{\prime}}_{0:\rho+\eta+\alpha}=2^{\rho+\eta+\alpha}italic_d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT + italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT; 故(M0:ρ+η+α′+d0)0:ρ+η+α=0subscriptsubscriptsuperscript𝑀′:0𝜌𝜂𝛼subscript𝑑0:0𝜌𝜂𝛼0(M^{{}^{\prime}}_{0:\rho+\eta+\alpha}+d_{0})_{0:\rho+\eta+\alpha}=0( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + italic_d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0 ∎ 引理3： 若|Xρ+η:ρ+η+α|=0subscript𝑋:𝜌𝜂𝜌𝜂𝛼0\left|X_{\rho+\eta:\rho+\eta+\alpha}\right|=0| italic_X start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT | = 0或2α−1superscript2𝛼12^{\alpha}-12 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1，(X+Y)ρ+η:ρ+η+α=0subscript𝑋𝑌:𝜌𝜂𝜌𝜂𝛼0(X+Y)_{\rho+\eta:\rho+\eta+\alpha}=0( italic_X + italic_Y ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0，则|Yρ+η:ρ+η+α|=0subscript𝑌:𝜌𝜂𝜌𝜂𝛼0\left|Y_{\rho+\eta:\rho+\eta+\alpha}\right|=0| italic_Y start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT | = 0或1111或2α−1superscript2𝛼12^{\alpha}-12 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1或2α−2superscript2𝛼22^{\alpha}-22 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 2。 Proof. 令H′=(X+Y)ρ+η+α:∞¯superscript𝐻′subscript𝑋𝑌¯:𝜌𝜂𝛼H^{{}^{\prime}}=(X+Y)_{\overline{\rho+\eta+\alpha:\infty}}italic_H start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = ( italic_X + italic_Y ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT，L′=(X+Y)0:ρ+ηsuperscript𝐿′subscript𝑋𝑌:0𝜌𝜂L^{{}^{\prime}}=(X+Y)_{0:\rho+\eta}italic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = ( italic_X + italic_Y ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η end_POSTSUBSCRIPT，由于(X+Y)ρ+η:ρ+η+α=0subscript𝑋𝑌:𝜌𝜂𝜌𝜂𝛼0(X+Y)_{\rho+\eta:\rho+\eta+\alpha}=0( italic_X + italic_Y ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0，则X+Y=H′+L′𝑋𝑌superscript𝐻′superscript𝐿′X+Y=H^{{}^{\prime}}+L^{{}^{\prime}}italic_X + italic_Y = italic_H start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT。 下面进行分类讨论。 情形1. 当Xρ+η:ρ+η+α=0subscript𝑋:𝜌𝜂𝜌𝜂𝛼0X_{\rho+\eta:\rho+\eta+\alpha}=0italic_X start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0时，令H=Xρ+η+α:∞¯𝐻subscript𝑋¯:𝜌𝜂𝛼H=X_{\overline{\rho+\eta+\alpha:\infty}}italic_H = italic_X start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT，L=X0:ρ+η𝐿subscript𝑋:0𝜌𝜂L=X_{0:\rho+\eta}italic_L = italic_X start_POSTSUBSCRIPT 0 : italic_ρ + italic_η end_POSTSUBSCRIPT，则X=H+L𝑋𝐻𝐿X=H+Litalic_X = italic_H + italic_L。 此时，Y=(H′−H)+(L′−L)𝑌superscript𝐻′𝐻superscript𝐿′𝐿Y=(H^{{}^{\prime}}-H)+(L^{{}^{\prime}}-L)italic_Y = ( italic_H start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_H ) + ( italic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L )，由于L∈[−2ρ+η+1,2ρ+η−1]𝐿superscript2𝜌𝜂1superscript2𝜌𝜂1L\in[-2^{\rho+\eta}+1,2^{\rho+\eta}-1]italic_L ∈ [ - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT + 1 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT - 1 ]，L′∈[−2ρ+η+1,2ρ+η−1]superscript𝐿′superscript2𝜌𝜂1superscript2𝜌𝜂1L^{{}^{\prime}}\in[-2^{\rho+\eta}+1,2^{\rho+\eta}-1]italic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ [ - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT + 1 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT - 1 ]，所以(L′−L)∈[−2ρ+η+1+2,2ρ+η+1−2]superscript𝐿′𝐿superscript2𝜌𝜂12superscript2𝜌𝜂12(L^{{}^{\prime}}-L)\in[-2^{\rho+\eta+1}+2,2^{\rho+\eta+1}-2]( italic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L ) ∈ [ - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + 1 end_POSTSUPERSCRIPT + 2 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + 1 end_POSTSUPERSCRIPT - 2 ]。 当H′−Hsuperscript𝐻′𝐻H^{{}^{\prime}}-Hitalic_H start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_H和L′−Lsuperscript𝐿′𝐿L^{{}^{\prime}}-Litalic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L同号或其中一个为0时，|Yρ+η:ρ+η+α|=0subscript𝑌:𝜌𝜂𝜌𝜂𝛼0\left|Y_{\rho+\eta:\rho+\eta+\alpha}\right|=0| italic_Y start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT | = 0或1111； 当H′−Hsuperscript𝐻′𝐻H^{{}^{\prime}}-Hitalic_H start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_H和L′−Lsuperscript𝐿′𝐿L^{{}^{\prime}}-Litalic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L异号时，|Yρ+η:ρ+η+α|=2α−1subscript𝑌:𝜌𝜂𝜌𝜂𝛼superscript2𝛼1\left|Y_{\rho+\eta:\rho+\eta+\alpha}\right|=2^{\alpha}-1| italic_Y start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT | = 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1或2α−2superscript2𝛼22^{\alpha}-22 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 2； 故情形1结论成立。 情形2. 当Xρ+η:ρ+η+α=2α−1subscript𝑋:𝜌𝜂𝜌𝜂𝛼superscript2𝛼1X_{\rho+\eta:\rho+\eta+\alpha}=2^{\alpha}-1italic_X start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1时， 令H=Xρ+η+α:∞¯+2ρ+η+α𝐻subscript𝑋¯:𝜌𝜂𝛼superscript2𝜌𝜂𝛼H=X_{\overline{\rho+\eta+\alpha:\infty}}+2^{\rho+\eta+\alpha}italic_H = italic_X start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT + 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT，L=X−H𝐿𝑋𝐻L=X-Hitalic_L = italic_X - italic_H，则 L𝐿\displaystyle Litalic_L =−2ρ+η+α+X0:ρ+η+αabsentsuperscript2𝜌𝜂𝛼subscript𝑋:0𝜌𝜂𝛼\displaystyle=-2^{\rho+\eta+\alpha}+X_{0:\rho+\eta+\alpha}= - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + italic_X start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT =−2ρ+η+α+X0:ρ+η+Xρ+η:ρ+η+α¯absentsuperscript2𝜌𝜂𝛼subscript𝑋:0𝜌𝜂subscript𝑋¯:𝜌𝜂𝜌𝜂𝛼\displaystyle=-2^{\rho+\eta+\alpha}+X_{0:\rho+\eta}+X_{\overline{\rho+\eta:% \rho+\eta+\alpha}}= - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + italic_X start_POSTSUBSCRIPT 0 : italic_ρ + italic_η end_POSTSUBSCRIPT + italic_X start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_ARG end_POSTSUBSCRIPT =−2ρ+η+α+X0:ρ+η+2ρ+ηXρ+η:ρ+η+αabsentsuperscript2𝜌𝜂𝛼subscript𝑋:0𝜌𝜂superscript2𝜌𝜂subscript𝑋:𝜌𝜂𝜌𝜂𝛼\displaystyle=-2^{\rho+\eta+\alpha}+X_{0:\rho+\eta}+2^{\rho+\eta}X_{\rho+\eta:% \rho+\eta+\alpha}= - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + italic_X start_POSTSUBSCRIPT 0 : italic_ρ + italic_η end_POSTSUBSCRIPT + 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT italic_X start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT =−2ρ+η+α+X0:ρ+η+2ρ+η(2α−1)absentsuperscript2𝜌𝜂𝛼subscript𝑋:0𝜌𝜂superscript2𝜌𝜂superscript2𝛼1\displaystyle=-2^{\rho+\eta+\alpha}+X_{0:\rho+\eta}+2^{\rho+\eta}(2^{\alpha}-1)= - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + italic_X start_POSTSUBSCRIPT 0 : italic_ρ + italic_η end_POSTSUBSCRIPT + 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT ( 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1 ) =−2ρ+η+X0:ρ+ηabsentsuperscript2𝜌𝜂subscript𝑋:0𝜌𝜂\displaystyle=-2^{\rho+\eta}+X_{0:\rho+\eta}= - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT + italic_X start_POSTSUBSCRIPT 0 : italic_ρ + italic_η end_POSTSUBSCRIPT 此时，Y=(H′−H)+(L′−L)𝑌superscript𝐻′𝐻superscript𝐿′𝐿Y=(H^{{}^{\prime}}-H)+(L^{{}^{\prime}}-L)italic_Y = ( italic_H start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_H ) + ( italic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L )，由于L∈[−2ρ+η,−1]𝐿superscript2𝜌𝜂1L\in[-2^{\rho+\eta},-1]italic_L ∈ [ - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT , - 1 ]，L′∈[−2ρ+η+1,2ρ+η−1]superscript𝐿′superscript2𝜌𝜂1superscript2𝜌𝜂1L^{{}^{\prime}}\in[-2^{\rho+\eta}+1,2^{\rho+\eta}-1]italic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ [ - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT + 1 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT - 1 ]，所以(L′−L)∈[−2ρ+η+2,2ρ+η+1−1]superscript𝐿′𝐿superscript2𝜌𝜂2superscript2𝜌𝜂11(L^{{}^{\prime}}-L)\in[-2^{\rho+\eta}+2,2^{\rho+\eta+1}-1]( italic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L ) ∈ [ - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT + 2 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + 1 end_POSTSUPERSCRIPT - 1 ]。 当H′−Hsuperscript𝐻′𝐻H^{{}^{\prime}}-Hitalic_H start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_H和L′−Lsuperscript𝐿′𝐿L^{{}^{\prime}}-Litalic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L同号或其中一个为0时，|Yρ+η:ρ+η+α|=0subscript𝑌:𝜌𝜂𝜌𝜂𝛼0\left|Y_{\rho+\eta:\rho+\eta+\alpha}\right|=0| italic_Y start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT | = 0或1111； 当H′−Hsuperscript𝐻′𝐻H^{{}^{\prime}}-Hitalic_H start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_H和L′−Lsuperscript𝐿′𝐿L^{{}^{\prime}}-Litalic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L异号时，|Yρ+η:ρ+η+α|=2α−1subscript𝑌:𝜌𝜂𝜌𝜂𝛼superscript2𝛼1\left|Y_{\rho+\eta:\rho+\eta+\alpha}\right|=2^{\alpha}-1| italic_Y start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT | = 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1或2α−2superscript2𝛼22^{\alpha}-22 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 2； 故情形2结论成立。 情形3. 当Xρ+η:ρ+η+α=−(2α−1)subscript𝑋:𝜌𝜂𝜌𝜂𝛼superscript2𝛼1X_{\rho+\eta:\rho+\eta+\alpha}=-(2^{\alpha}-1)italic_X start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = - ( 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1 )时， 令H=Xρ+η+α:∞¯−2ρ+η+α𝐻subscript𝑋¯:𝜌𝜂𝛼superscript2𝜌𝜂𝛼H=X_{\overline{\rho+\eta+\alpha:\infty}}-2^{\rho+\eta+\alpha}italic_H = italic_X start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT，L=X−H𝐿𝑋𝐻L=X-Hitalic_L = italic_X - italic_H，则 L𝐿\displaystyle Litalic_L =2ρ+η+α+X0:ρ+η+αabsentsuperscript2𝜌𝜂𝛼subscript𝑋:0𝜌𝜂𝛼\displaystyle=2^{\rho+\eta+\alpha}+X_{0:\rho+\eta+\alpha}= 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + italic_X start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT =2ρ+η+α+X0:ρ+η+Xρ+η:ρ+η+α¯absentsuperscript2𝜌𝜂𝛼subscript𝑋:0𝜌𝜂subscript𝑋¯:𝜌𝜂𝜌𝜂𝛼\displaystyle=2^{\rho+\eta+\alpha}+X_{0:\rho+\eta}+X_{\overline{\rho+\eta:\rho% +\eta+\alpha}}= 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + italic_X start_POSTSUBSCRIPT 0 : italic_ρ + italic_η end_POSTSUBSCRIPT + italic_X start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_ARG end_POSTSUBSCRIPT =2ρ+η+α+X0:ρ+η+2ρ+ηXρ+η:ρ+η+αabsentsuperscript2𝜌𝜂𝛼subscript𝑋:0𝜌𝜂superscript2𝜌𝜂subscript𝑋:𝜌𝜂𝜌𝜂𝛼\displaystyle=2^{\rho+\eta+\alpha}+X_{0:\rho+\eta}+2^{\rho+\eta}X_{\rho+\eta:% \rho+\eta+\alpha}= 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + italic_X start_POSTSUBSCRIPT 0 : italic_ρ + italic_η end_POSTSUBSCRIPT + 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT italic_X start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT =2ρ+η+α+X0:ρ+η−2ρ+η(2α−1)absentsuperscript2𝜌𝜂𝛼subscript𝑋:0𝜌𝜂superscript2𝜌𝜂superscript2𝛼1\displaystyle=2^{\rho+\eta+\alpha}+X_{0:\rho+\eta}-2^{\rho+\eta}(2^{\alpha}-1)= 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + italic_X start_POSTSUBSCRIPT 0 : italic_ρ + italic_η end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT ( 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1 ) =2ρ+η+X0:ρ+ηabsentsuperscript2𝜌𝜂subscript𝑋:0𝜌𝜂\displaystyle=2^{\rho+\eta}+X_{0:\rho+\eta}= 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT + italic_X start_POSTSUBSCRIPT 0 : italic_ρ + italic_η end_POSTSUBSCRIPT 此时，Y=(H′−H)+(L′−L)𝑌superscript𝐻′𝐻superscript𝐿′𝐿Y=(H^{{}^{\prime}}-H)+(L^{{}^{\prime}}-L)italic_Y = ( italic_H start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_H ) + ( italic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L )，由于L∈[1,2ρ+η]𝐿1superscript2𝜌𝜂L\in[1,2^{\rho+\eta}]italic_L ∈ [ 1 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT ]，L′∈[−2ρ+η+1,2ρ+η−1]superscript𝐿′superscript2𝜌𝜂1superscript2𝜌𝜂1L^{{}^{\prime}}\in[-2^{\rho+\eta}+1,2^{\rho+\eta}-1]italic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ [ - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT + 1 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT - 1 ]，所以(L′−L)∈[−2ρ+η+1+1,2ρ+η−2]superscript𝐿′𝐿superscript2𝜌𝜂11superscript2𝜌𝜂2(L^{{}^{\prime}}-L)\in[-2^{\rho+\eta+1}+1,2^{\rho+\eta}-2]( italic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L ) ∈ [ - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + 1 end_POSTSUPERSCRIPT + 1 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT - 2 ]。 当H′−Hsuperscript𝐻′𝐻H^{{}^{\prime}}-Hitalic_H start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_H和L′−Lsuperscript𝐿′𝐿L^{{}^{\prime}}-Litalic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L同号或其中一个为0时，|Yρ+η:ρ+η+α|=0subscript𝑌:𝜌𝜂𝜌𝜂𝛼0\left|Y_{\rho+\eta:\rho+\eta+\alpha}\right|=0| italic_Y start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT | = 0或1111； 当H′−Hsuperscript𝐻′𝐻H^{{}^{\prime}}-Hitalic_H start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_H和L′−Lsuperscript𝐿′𝐿L^{{}^{\prime}}-Litalic_L start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - italic_L异号时，|Yρ+η:ρ+η+α|=2α−1subscript𝑌:𝜌𝜂𝜌𝜂𝛼superscript2𝛼1\left|Y_{\rho+\eta:\rho+\eta+\alpha}\right|=2^{\alpha}-1| italic_Y start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT | = 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1或2α−2superscript2𝛼22^{\alpha}-22 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 2； 故情形3结论成立。 综合情形1，情形2， 情形3，引理3成立。 ∎ 定理1： 集合{(t+R[j].t,s+R[j].s)|j\{(t+R[j].t,s+R[j].s)~{}|~{}j{ ( italic_t + italic_R [ italic_j ] . italic_t , italic_s + italic_R [ italic_j ] . italic_s ) | italic_j为算法第10步加入A的数值}}\}}包含了所有符合下述条件的(t′,s′)superscript𝑡′superscript𝑠′(t^{{}^{\prime}},s^{{}^{\prime}})( italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT , italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT )： (M′+t′p+s′q)ρ+η:ρ+η+α=0subscriptsuperscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞:𝜌𝜂𝜌𝜂𝛼0(M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}q)_{\rho+\eta:\rho+\eta+% \alpha}=0( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0,且t′,s′∈[0,w)superscript𝑡′superscript𝑠′0𝑤t^{{}^{\prime}},s^{{}^{\prime}}\in[0,w)italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT , italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ [ 0 , italic_w )。 Proof. 根据算法过程,在第10步有： dθ=d0−∑i=0θ−1ϕiei,t=∑i=0θ−1ϕiti,s=∑i=0θ−1ϕisiformulae-sequencesubscript𝑑𝜃subscript𝑑0superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscript𝑒𝑖formulae-sequence𝑡superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscript𝑡𝑖𝑠superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscript𝑠𝑖d_{\theta}=d_{0}-\sum_{i=0}^{\theta-1}\phi_{i}e_{i},\qquad t=\sum_{i=0}^{% \theta-1}\phi_{i}t_{i},\qquad s=\sum_{i=0}^{\theta-1}\phi_{i}s_{i}italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT = italic_d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT - ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_e start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , italic_t = ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT , italic_s = ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT (7) 令Mθ′=M′+tp+sq=M′+∑i=0θ−1ϕi(tip+siq)subscriptsuperscript𝑀′𝜃superscript𝑀′𝑡𝑝𝑠𝑞superscript𝑀′superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscript𝑡𝑖𝑝subscript𝑠𝑖𝑞M^{{}^{\prime}}_{\theta}=M^{{}^{\prime}}+tp+sq=M^{{}^{\prime}}+\sum_{i=0}^{% \theta-1}\phi_{i}(t_{i}p+s_{i}q)italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t italic_p + italic_s italic_q = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_q ) 则有： Mθ′subscriptsuperscript𝑀′𝜃\displaystyle M^{{}^{\prime}}_{\theta}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT =M′+∑i=0θ−1ϕi(tip+siq)0:ρ+η+α+∑i=0θ−1ϕi(tip+siq)ρ+η+α:∞¯absentsuperscript𝑀′superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscriptsubscript𝑡𝑖𝑝subscript𝑠𝑖𝑞:0𝜌𝜂𝛼superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscriptsubscript𝑡𝑖𝑝subscript𝑠𝑖𝑞¯:𝜌𝜂𝛼\displaystyle=M^{{}^{\prime}}+\sum_{i=0}^{\theta-1}\phi_{i}(t_{i}p+s_{i}q)_{0:% \rho+\eta+\alpha}+\sum_{i=0}^{\theta-1}\phi_{i}(t_{i}p+s_{i}q)_{\overline{\rho% +\eta+\alpha:\infty}}= italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_q ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_q ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT =M0:ρ+η+α′+Mρ+η+α:∞¯′+∑i=0θ−1ϕiei+∑i=0θ−1ϕi(tip+siq)ρ+η+α:∞¯absentsubscriptsuperscript𝑀′:0𝜌𝜂𝛼subscriptsuperscript𝑀′¯:𝜌𝜂𝛼superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscript𝑒𝑖superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscriptsubscript𝑡𝑖𝑝subscript𝑠𝑖𝑞¯:𝜌𝜂𝛼\displaystyle=M^{{}^{\prime}}_{0:\rho+\eta+\alpha}+M^{{}^{\prime}}_{\overline{% \rho+\eta+\alpha:\infty}}+\sum_{i=0}^{\theta-1}\phi_{i}e_{i}+\sum_{i=0}^{% \theta-1}\phi_{i}(t_{i}p+s_{i}q)_{\overline{\rho+\eta+\alpha:\infty}}= italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_e start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_q ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT =M0:ρ+η+α′+Mρ+η+α:∞¯′+d0−dθ+∑i=0θ−1ϕi(tip+siq)ρ+η+α:∞¯absentsubscriptsuperscript𝑀′:0𝜌𝜂𝛼subscriptsuperscript𝑀′¯:𝜌𝜂𝛼subscript𝑑0subscript𝑑𝜃superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscriptsubscript𝑡𝑖𝑝subscript𝑠𝑖𝑞¯:𝜌𝜂𝛼\displaystyle=M^{{}^{\prime}}_{0:\rho+\eta+\alpha}+M^{{}^{\prime}}_{\overline{% \rho+\eta+\alpha:\infty}}+d_{0}-d_{\theta}+\sum_{i=0}^{\theta-1}\phi_{i}(t_{i}% p+s_{i}q)_{\overline{\rho+\eta+\alpha:\infty}}= italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT + italic_d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT - italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_q ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT 记H=M0:ρ+η+α′+Mρ+η+α:∞¯′+d0+∑i=0θ−1ϕi(tip+siq)ρ+η+α:∞¯𝐻subscriptsuperscript𝑀′:0𝜌𝜂𝛼subscriptsuperscript𝑀′¯:𝜌𝜂𝛼subscript𝑑0superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscriptsubscript𝑡𝑖𝑝subscript𝑠𝑖𝑞¯:𝜌𝜂𝛼H=M^{{}^{\prime}}_{0:\rho+\eta+\alpha}+M^{{}^{\prime}}_{\overline{\rho+\eta+% \alpha:\infty}}+d_{0}+\sum_{i=0}^{\theta-1}\phi_{i}(t_{i}p+s_{i}q)_{\overline{% \rho+\eta+\alpha:\infty}}italic_H = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT + italic_d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ( italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_p + italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_q ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT，则Mθ′subscriptsuperscript𝑀′𝜃M^{{}^{\prime}}_{\theta}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT可写为： Mθ′=H−dθsubscriptsuperscript𝑀′𝜃𝐻subscript𝑑𝜃M^{{}^{\prime}}_{\theta}=H-d_{\theta}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT = italic_H - italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT 由引理1可知|dθ|<2ρ+ηsubscript𝑑𝜃superscript2𝜌𝜂\left|d_{\theta}\right|<2^{\rho+\eta}| italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT | < 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT。 由引理2可知(M0:ρ+η+α′+d0)0:ρ+η+α=0subscriptsubscriptsuperscript𝑀′:0𝜌𝜂𝛼subscript𝑑0:0𝜌𝜂𝛼0(M^{{}^{\prime}}_{0:\rho+\eta+\alpha}+d_{0})_{0:\rho+\eta+\alpha}=0( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + italic_d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0，从而有H0:ρ+η+α=0subscript𝐻:0𝜌𝜂𝛼0H_{0:\rho+\eta+\alpha}=0italic_H start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0。 则 (Mθ′)ρ+η:ρ+η+α=(H−dθ)ρ+η:ρ+η+α={0,Hdθ≤02α−1,H>0,dθ>01−2α,H<0,dθ<0subscriptsubscriptsuperscript𝑀′𝜃:𝜌𝜂𝜌𝜂𝛼subscript𝐻subscript𝑑𝜃:𝜌𝜂𝜌𝜂𝛼cases0𝐻subscript𝑑𝜃0formulae-sequencesuperscript2𝛼1𝐻0subscript𝑑𝜃0formulae-sequence1superscript2𝛼𝐻0subscript𝑑𝜃0(M^{{}^{\prime}}_{\theta})_{\rho+\eta:\rho+\eta+\alpha}=(H-d_{\theta})_{\rho+% \eta:\rho+\eta+\alpha}=\left\{\begin{array}[]{l}0,\qquad\qquad Hd_{\theta}\leq 0% \\ 2^{\alpha}-1,\qquad H>0,d_{\theta}>0\\ 1-2^{\alpha},\qquad H<0,d_{\theta}<0\end{array}\right.( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = ( italic_H - italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = { start_ARRAY start_ROW start_CELL 0 , italic_H italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT ≤ 0 end_CELL end_ROW start_ROW start_CELL 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1 , italic_H > 0 , italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT > 0 end_CELL end_ROW start_ROW start_CELL 1 - 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT , italic_H < 0 , italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT < 0 end_CELL end_ROW end_ARRAY 假设存在t′∈[0,w)superscript𝑡′0𝑤t^{{}^{\prime}}\in[0,w)italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ [ 0 , italic_w )，s′∈[0,w)superscript𝑠′0𝑤s^{{}^{\prime}}\in[0,w)italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ [ 0 , italic_w )，满足(M′+t′p+s′q)ρ+η:ρ+η+α=0subscriptsuperscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞:𝜌𝜂𝜌𝜂𝛼0(M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}q)_{\rho+\eta:\rho+\eta+% \alpha}=0( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0。 令{tΔ=t′−∑i=0θ−1ϕitisΔ=s′−∑i=0θ−1ϕisicasessuperscript𝑡Δsuperscript𝑡′superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscript𝑡𝑖superscript𝑠Δsuperscript𝑠′superscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscript𝑠𝑖\left\{\begin{array}[]{l}t^{\Delta}=t^{{}^{\prime}}-\sum_{i=0}^{\theta-1}\phi_% {i}t_{i}\\ s^{\Delta}=s^{{}^{\prime}}-\sum_{i=0}^{\theta-1}\phi_{i}s_{i}\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT = italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_CELL end_ROW start_ROW start_CELL italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT = italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT - ∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_CELL end_ROW end_ARRAY,则M′+t′p+s′q=Mθ′+tΔp+sΔqsuperscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞subscriptsuperscript𝑀′𝜃superscript𝑡Δ𝑝superscript𝑠Δ𝑞M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}q=M^{{}^{\prime}}_{\theta}+t^{% \Delta}p+s^{\Delta}qitalic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q 把Mθ′subscriptsuperscript𝑀′𝜃M^{{}^{\prime}}_{\theta}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT看成引理3中的X𝑋Xitalic_X，tΔp+sΔqsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞t^{\Delta}p+s^{\Delta}qitalic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q看成引理3中的Y𝑌Yitalic_Y, 由引理3可知|(tΔp+sΔq)ρ+η:ρ+η+α|=0subscriptsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞:𝜌𝜂𝜌𝜂𝛼0\left|(t^{\Delta}p+s^{\Delta}q)_{\rho+\eta:\rho+\eta+\alpha}\right|=0| ( italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT | = 0或1111或2α−1superscript2𝛼12^{\alpha}-12 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1或2α−2superscript2𝛼22^{\alpha}-22 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 2。 因为： 1、t′superscript𝑡′t^{{}^{\prime}}italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT的位宽小于等于α/2𝛼2\alpha/2italic_α / 2，比κ𝜅\kappaitalic_κ至少小1个比特; 2、tisubscript𝑡𝑖t_{i}italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT是预计算表T的第i𝑖iitalic_i行元素，位宽约为(i+1)μ/2𝑖1𝜇2(i+1)\mu/2( italic_i + 1 ) italic_μ / 2，当i∈[0,θ−2]𝑖0𝜃2i\in[0,\theta-2]italic_i ∈ [ 0 , italic_θ - 2 ]时，tisubscript𝑡𝑖t_{i}italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT的位宽明显小于κ𝜅\kappaitalic_κ；当i=θ−1𝑖𝜃1i=\theta-1italic_i = italic_θ - 1时，tisubscript𝑡𝑖t_{i}italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT的位宽最大为κ𝜅\kappaitalic_κ。 所以tΔsuperscript𝑡Δt^{\Delta}italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT的位宽最大为κ+1𝜅1\kappa+1italic_κ + 1。即 tΔ∈[−2κ+1,2κ+1]superscript𝑡Δsuperscript2𝜅1superscript2𝜅1t^{\Delta}\in[-2^{\kappa+1},2^{\kappa+1}]italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT ∈ [ - 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT , 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT ]，同理sΔ∈[−2κ+1,2κ+1]superscript𝑠Δsuperscript2𝜅1superscript2𝜅1s^{\Delta}\in[-2^{\kappa+1},2^{\kappa+1}]italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT ∈ [ - 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT , 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT ]。 又因为刚刚证明过|(tΔp+sΔq)ρ+η:ρ+η+α|=0subscriptsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞:𝜌𝜂𝜌𝜂𝛼0\left|(t^{\Delta}p+s^{\Delta}q)_{\rho+\eta:\rho+\eta+\alpha}\right|=0| ( italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT | = 0或1111或2α−1superscript2𝛼12^{\alpha}-12 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 1或2α−2superscript2𝛼22^{\alpha}-22 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT - 2，所以tΔsuperscript𝑡Δt^{\Delta}italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT，sΔsuperscript𝑠Δs^{\Delta}italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT一定在表R中。 由公式（7）可知，∑i=0θ−1ϕitisuperscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscript𝑡𝑖\sum_{i=0}^{\theta-1}\phi_{i}t_{i}∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT和∑i=0θ−1ϕisisuperscriptsubscript𝑖0𝜃1subscriptitalic-ϕ𝑖subscript𝑠𝑖\sum_{i=0}^{\theta-1}\phi_{i}s_{i}∑ start_POSTSUBSCRIPT italic_i = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_θ - 1 end_POSTSUPERSCRIPT italic_ϕ start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_s start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT即第10步的t𝑡titalic_t和s𝑠sitalic_s。则在第10步时，t+tΔ=t′∈[0,w)𝑡superscript𝑡Δsuperscript𝑡′0𝑤t+t^{\Delta}=t^{{}^{\prime}}\in[0,w)italic_t + italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT = italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ [ 0 , italic_w )，s+sΔ=s′∈[0,w)𝑠superscript𝑠Δsuperscript𝑠′0𝑤s+s^{\Delta}=s^{{}^{\prime}}\in[0,w)italic_s + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT = italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ [ 0 , italic_w )。所以tΔsuperscript𝑡Δt^{\Delta}italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT和sΔsuperscript𝑠Δs^{\Delta}italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT一定会在第10步被筛选到，其对应的数组下标会被加入到A中。 至此，定理得证。 ∎ 定理2： 上述算法第14步结束后，E𝐸Eitalic_E为符合下述条件的t,s𝑡𝑠t,sitalic_t , italic_s集合： (M′+tp+sq)ρ+η:ρ+η+α=0subscriptsuperscript𝑀′𝑡𝑝𝑠𝑞:𝜌𝜂𝜌𝜂𝛼0(M^{{}^{\prime}}+tp+sq)_{\rho+\eta:\rho+\eta+\alpha}=0( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t italic_p + italic_s italic_q ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0,且t,s∈[0,w)𝑡𝑠0𝑤t,s\in[0,w)italic_t , italic_s ∈ [ 0 , italic_w )。 Proof. 假设t′superscript𝑡′t^{{}^{\prime}}italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT，s′superscript𝑠′s^{{}^{\prime}}italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT为算法第10步A𝐴Aitalic_A中某个元素j𝑗jitalic_j对应的(t+R[j].tformulae-sequence𝑡𝑅delimited-[]𝑗𝑡t+R[j].titalic_t + italic_R [ italic_j ] . italic_t，s+R[j].sformulae-sequence𝑠𝑅delimited-[]𝑗𝑠s+R[j].sitalic_s + italic_R [ italic_j ] . italic_s)。 其他符号与定理1一致。 M′+t′p+s′q=Mθ′+tΔp+sΔq=H−dθ+(tΔp+sΔq)0:ρ+η+α+(tΔp+sΔq)ρ+η+α:∞¯=H+(tΔp+sΔq)ρ+η+α:∞¯+((tΔp+sΔq)0:ρ+η+α−dθ)ρ+η+α:∞¯+((tΔp+sΔq)0:ρ+η+α−dθ)0:ρ+η+αsuperscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞subscriptsuperscript𝑀′𝜃superscript𝑡Δ𝑝superscript𝑠Δ𝑞𝐻subscript𝑑𝜃subscriptsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞:0𝜌𝜂𝛼subscriptsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞¯:𝜌𝜂𝛼𝐻subscriptsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞¯:𝜌𝜂𝛼subscriptsubscriptsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞:0𝜌𝜂𝛼subscript𝑑𝜃¯:𝜌𝜂𝛼subscriptsubscriptsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞:0𝜌𝜂𝛼subscript𝑑𝜃:0𝜌𝜂𝛼M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}q=M^{{}^{\prime}}_{\theta}+t^{% \Delta}p+s^{\Delta}q\\ =H-d_{\theta}+(t^{\Delta}p+s^{\Delta}q)_{0:\rho+\eta+\alpha}+(t^{\Delta}p+s^{% \Delta}q)_{\overline{\rho+\eta+\alpha:\infty}}\\ =H+(t^{\Delta}p+s^{\Delta}q)_{\overline{\rho+\eta+\alpha:\infty}}+((t^{\Delta}% p+s^{\Delta}q)_{0:\rho+\eta+\alpha}-d_{\theta})_{\overline{\rho+\eta+\alpha:% \infty}}\\ +((t^{\Delta}p+s^{\Delta}q)_{0:\rho+\eta+\alpha}-d_{\theta})_{0:\rho+\eta+\alpha}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q = italic_H - italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT + ( italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + ( italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT = italic_H + ( italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT + ( ( italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT - italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT + ( ( italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT - italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT 记 H¯=H+(tΔp+sΔq)ρ+η+α:∞¯+((tΔp+sΔq)0:ρ+η+α−dθ)ρ+η+α:∞¯¯𝐻𝐻subscriptsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞¯:𝜌𝜂𝛼subscriptsubscriptsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞:0𝜌𝜂𝛼subscript𝑑𝜃¯:𝜌𝜂𝛼\overline{H}=H+(t^{\Delta}p+s^{\Delta}q)_{\overline{\rho+\eta+\alpha:\infty}}+% ((t^{\Delta}p+s^{\Delta}q)_{0:\rho+\eta+\alpha}-d_{\theta})_{\overline{\rho+% \eta+\alpha:\infty}}over¯ start_ARG italic_H end_ARG = italic_H + ( italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT + ( ( italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT - italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_η + italic_α : ∞ end_ARG end_POSTSUBSCRIPT L¯=(tΔp+sΔq)0:ρ+η+α−dθ¯𝐿subscriptsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞:0𝜌𝜂𝛼subscript𝑑𝜃\overline{L}=(t^{\Delta}p+s^{\Delta}q)_{0:\rho+\eta+\alpha}-d_{\theta}over¯ start_ARG italic_L end_ARG = ( italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT - italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT 则 M′+t′p+s′q=H¯+L¯0:ρ+η+αsuperscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞¯𝐻subscript¯𝐿:0𝜌𝜂𝛼M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}q=\overline{H}+\overline{L}_{0% :\rho+\eta+\alpha}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q = over¯ start_ARG italic_H end_ARG + over¯ start_ARG italic_L end_ARG start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT 定理1中已经证明过H0:ρ+η+α=0subscript𝐻:0𝜌𝜂𝛼0H_{0:\rho+\eta+\alpha}=0italic_H start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0，所以H¯0:ρ+η+α=0subscript¯𝐻:0𝜌𝜂𝛼0\overline{H}_{0:\rho+\eta+\alpha}=0over¯ start_ARG italic_H end_ARG start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0 根据M′superscript𝑀′M^{{}^{\prime}}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT的定义、第10步的筛选条件，可知 M′≥0superscript𝑀′0M^{{}^{\prime}}\geq 0italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ≥ 0，t′≥0superscript𝑡′0t^{{}^{\prime}}\geq 0italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ≥ 0，s′≥0superscript𝑠′0s^{{}^{\prime}}\geq 0italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ≥ 0，故M′+t′p+s′q≥0superscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞0M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}q\geq 0italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q ≥ 0。又因为M′+t′p+s′qsuperscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}qitalic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q的ρ+η+α𝜌𝜂𝛼\rho+\eta+\alphaitalic_ρ + italic_η + italic_α以上高位主要来自H¯¯𝐻\overline{H}over¯ start_ARG italic_H end_ARG，所以H¯≥0¯𝐻0\overline{H}\geq 0over¯ start_ARG italic_H end_ARG ≥ 0; 当L¯≥0¯𝐿0\overline{L}\geq 0over¯ start_ARG italic_L end_ARG ≥ 0时，(M′+t′p+s′q)ρ+η:ρ+η+α=0subscriptsuperscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞:𝜌𝜂𝜌𝜂𝛼0(M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}q)_{\rho+\eta:\rho+\eta+% \alpha}=0( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0的充要条件为L¯ρ+η:ρ+η+α=0subscript¯𝐿:𝜌𝜂𝜌𝜂𝛼0\overline{L}_{\rho+\eta:\rho+\eta+\alpha}=0over¯ start_ARG italic_L end_ARG start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0。 当L¯<0¯𝐿0\overline{L}<0over¯ start_ARG italic_L end_ARG < 0时，M′+t′p+s′q=(H¯−2ρ+η+α)+(2ρ+η+α+L¯0:ρ+η+α)superscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞¯𝐻superscript2𝜌𝜂𝛼superscript2𝜌𝜂𝛼subscript¯𝐿:0𝜌𝜂𝛼M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}q=(\overline{H}-2^{\rho+\eta+% \alpha})+(2^{\rho+\eta+\alpha}+\overline{L}_{0:\rho+\eta+\alpha})italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q = ( over¯ start_ARG italic_H end_ARG - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT ) + ( 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + over¯ start_ARG italic_L end_ARG start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT ) 注意，此时(H¯−2ρ+η+α)¯𝐻superscript2𝜌𝜂𝛼(\overline{H}-2^{\rho+\eta+\alpha})( over¯ start_ARG italic_H end_ARG - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT )也是大于等于0的，否则会导致M′+t′p+s′qsuperscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}qitalic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q为负数。所以此时，(M′+t′p+s′q)ρ+η:ρ+η+α=0subscriptsuperscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞:𝜌𝜂𝜌𝜂𝛼0(M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}q)_{\rho+\eta:\rho+\eta+% \alpha}=0( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0的充要条件为(2ρ+η+α+L¯0:ρ+η+α)ρ+η:ρ+η+α=0subscriptsuperscript2𝜌𝜂𝛼subscript¯𝐿:0𝜌𝜂𝛼:𝜌𝜂𝜌𝜂𝛼0(2^{\rho+\eta+\alpha}+\overline{L}_{0:\rho+\eta+\alpha})_{\rho+\eta:\rho+\eta+% \alpha}=0( 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + over¯ start_ARG italic_L end_ARG start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0，又因为2ρ+η+α>2ρ+η+α+L¯0:ρ+η+α>0superscript2𝜌𝜂𝛼superscript2𝜌𝜂𝛼subscript¯𝐿:0𝜌𝜂𝛼02^{\rho+\eta+\alpha}>2^{\rho+\eta+\alpha}+\overline{L}_{0:\rho+\eta+\alpha}>02 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT > 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + over¯ start_ARG italic_L end_ARG start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT > 0，所以该条件就转化为2ρ+η+α+L¯0:ρ+η+α∈[0,2ρ+η−1]superscript2𝜌𝜂𝛼subscript¯𝐿:0𝜌𝜂𝛼0superscript2𝜌𝜂12^{\rho+\eta+\alpha}+\overline{L}_{0:\rho+\eta+\alpha}\in[0,2^{\rho+\eta}-1]2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + over¯ start_ARG italic_L end_ARG start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT ∈ [ 0 , 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT - 1 ]，即L¯0:ρ+η+α+1∈[−2ρ+η+α+1,−2ρ+η+α+2ρ+η]subscript¯𝐿:0𝜌𝜂𝛼1superscript2𝜌𝜂𝛼1superscript2𝜌𝜂𝛼superscript2𝜌𝜂\overline{L}_{0:\rho+\eta+\alpha}+1\in[-2^{\rho+\eta+\alpha}+1,-2^{\rho+\eta+% \alpha}+2^{\rho+\eta}]over¯ start_ARG italic_L end_ARG start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + 1 ∈ [ - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + 1 , - 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT + 2 start_POSTSUPERSCRIPT italic_ρ + italic_η end_POSTSUPERSCRIPT ]，即(L¯0:ρ+η+α+1)ρ+η:ρ+η+α=1−2αsubscriptsubscript¯𝐿:0𝜌𝜂𝛼1:𝜌𝜂𝜌𝜂𝛼1superscript2𝛼(\overline{L}_{0:\rho+\eta+\alpha}+1)_{\rho+\eta:\rho+\eta+\alpha}=1-2^{\alpha}( over¯ start_ARG italic_L end_ARG start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + 1 ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 1 - 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT。 我们总结一下，(M′+t′p+s′q)ρ+η:ρ+η+α=0subscriptsuperscript𝑀′superscript𝑡′𝑝superscript𝑠′𝑞:𝜌𝜂𝜌𝜂𝛼0(M^{{}^{\prime}}+t^{{}^{\prime}}p+s^{{}^{\prime}}q)_{\rho+\eta:\rho+\eta+% \alpha}=0( italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0的充要条件为：当L¯≥0¯𝐿0\overline{L}\geq 0over¯ start_ARG italic_L end_ARG ≥ 0时，L¯ρ+η:ρ+η+α=0subscript¯𝐿:𝜌𝜂𝜌𝜂𝛼0\overline{L}_{\rho+\eta:\rho+\eta+\alpha}=0over¯ start_ARG italic_L end_ARG start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0；当L¯<0¯𝐿0\overline{L}<0over¯ start_ARG italic_L end_ARG < 0时，(L¯0:ρ+η+α+1)ρ+η:ρ+η+α=1−2αsubscriptsubscript¯𝐿:0𝜌𝜂𝛼1:𝜌𝜂𝜌𝜂𝛼1superscript2𝛼(\overline{L}_{0:\rho+\eta+\alpha}+1)_{\rho+\eta:\rho+\eta+\alpha}=1-2^{\alpha}( over¯ start_ARG italic_L end_ARG start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + 1 ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 1 - 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT。 其中(tΔp+sΔq)0:ρ+η+αsubscriptsuperscript𝑡Δ𝑝superscript𝑠Δ𝑞:0𝜌𝜂𝛼(t^{\Delta}p+s^{\Delta}q)_{0:\rho+\eta+\alpha}( italic_t start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT roman_Δ end_POSTSUPERSCRIPT italic_q ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT为算法第12步中的R[j].eformulae-sequence𝑅delimited-[]𝑗𝑒R[j].eitalic_R [ italic_j ] . italic_e，dθsubscript𝑑𝜃d_{\theta}italic_d start_POSTSUBSCRIPT italic_θ end_POSTSUBSCRIPT为算法第12步中的d𝑑ditalic_d。则上述充要条件为：当R[j].e−d≥0formulae-sequence𝑅delimited-[]𝑗𝑒𝑑0R[j].e-d\geq 0italic_R [ italic_j ] . italic_e - italic_d ≥ 0时，(R[j].e−d)ρ+η:ρ+η+α=0(R[j].e-d)_{\rho+\eta:\rho+\eta+\alpha}=0( italic_R [ italic_j ] . italic_e - italic_d ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0；当R[j].e−d<0formulae-sequence𝑅delimited-[]𝑗𝑒𝑑0R[j].e-d<0italic_R [ italic_j ] . italic_e - italic_d < 0时，(R[j].e−d+1)ρ+η:ρ+η+α=1−2α(R[j].e-d+1)_{\rho+\eta:\rho+\eta+\alpha}=1-2^{\alpha}( italic_R [ italic_j ] . italic_e - italic_d + 1 ) start_POSTSUBSCRIPT italic_ρ + italic_η : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 1 - 2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT。 上述条件即算法步骤12的判断条件， 从而定理成立。 ∎ 结束语:根据定理2，上述算法在第14步之后，基本已经找到了公式（2）中的t𝑡titalic_t和s𝑠sitalic_s（第15步又选出最优的），则可以求出∑i=1w(ui+vi)superscriptsubscript𝑖1𝑤subscript𝑢𝑖subscript𝑣𝑖\sum_{i=1}^{w}(u_{i}+v_{i})∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT )，从其中的明文区可以获得我们要解密的m𝑚mitalic_m。 6 关键实现方法 6.1 计算预计算表的通用部分 先分别计算tp𝑡𝑝tpitalic_t italic_p、sq𝑠𝑞sqitalic_s italic_q的值，t∈[0,2κ+1]𝑡0superscript2𝜅1t\in[0,2^{\kappa+1}]italic_t ∈ [ 0 , 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT ]，s∈[0,2κ+1]𝑠0superscript2𝜅1s\in[0,2^{\kappa+1}]italic_s ∈ [ 0 , 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT ]。 6.2 计算预计算表T𝑇Titalic_T 回顾一下，表T𝑇Titalic_T的目标是寻找t𝑡titalic_t和s𝑠sitalic_s使得 T[i][j].e=(tp+sq)0:ρ+η+αformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗𝑒subscript𝑡𝑝𝑠𝑞:0𝜌𝜂𝛼T[i][j].e=(tp+sq)_{0:\rho+\eta+\alpha}italic_T [ italic_i ] [ italic_j ] . italic_e = ( italic_t italic_p + italic_s italic_q ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT 且 T[i][j].eρ+η+α−μ(i+1):ρ+η+α=jformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗subscript𝑒:𝜌𝜂𝛼𝜇𝑖1𝜌𝜂𝛼𝑗T[i][j].e_{\rho+\eta+\alpha-\mu(i+1):\rho+\eta+\alpha}=jitalic_T [ italic_i ] [ italic_j ] . italic_e start_POSTSUBSCRIPT italic_ρ + italic_η + italic_α - italic_μ ( italic_i + 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = italic_j，j∈[0,2μ−1]𝑗0superscript2𝜇1j\in[0,2^{\mu}-1]italic_j ∈ [ 0 , 2 start_POSTSUPERSCRIPT italic_μ end_POSTSUPERSCRIPT - 1 ]。 观察上式可以发现，对于T𝑇Titalic_T中的第i𝑖iitalic_i行，我们需要让e𝑒eitalic_e中的μ(i+1)𝜇𝑖1\mu(i+1)italic_μ ( italic_i + 1 )位(即 eρ+η+α−μ(i+1):ρ+η+αsubscript𝑒:𝜌𝜂𝛼𝜇𝑖1𝜌𝜂𝛼e_{\rho+\eta+\alpha-\mu(i+1):\rho+\eta+\alpha}italic_e start_POSTSUBSCRIPT italic_ρ + italic_η + italic_α - italic_μ ( italic_i + 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT)符合特定的值。 当i=0𝑖0i=0italic_i = 0时，即让e𝑒eitalic_e中的μ𝜇\muitalic_μ位符合特定的值，此时只需要在[0,2μ]0superscript2𝜇[0,2^{\mu}][ 0 , 2 start_POSTSUPERSCRIPT italic_μ end_POSTSUPERSCRIPT ]内暴力搜索t𝑡titalic_t和s𝑠sitalic_s。 当i>0𝑖0i>0italic_i > 0时, e𝑒eitalic_e中要符合特定值的位数增加，暴力搜索效率下降。对于特定的i𝑖iitalic_i，T[i][j]𝑇delimited-[]𝑖delimited-[]𝑗T[i][j]italic_T [ italic_i ] [ italic_j ]的建表过程如下(参见Figure 3)： 1）由于只需要考虑e𝑒eitalic_e中的μ(i+1)𝜇𝑖1\mu(i+1)italic_μ ( italic_i + 1 )位符合特定的值，此时只要搜索t∈[0,2μ(i+1)/2+δ]𝑡0superscript2𝜇𝑖12𝛿t\in[0,2^{\mu(i+1)/2+\delta}]italic_t ∈ [ 0 , 2 start_POSTSUPERSCRIPT italic_μ ( italic_i + 1 ) / 2 + italic_δ end_POSTSUPERSCRIPT ], s∈[0,2μ(i+1)/2+δ]𝑠0superscript2𝜇𝑖12𝛿s\in[0,2^{\mu(i+1)/2+\delta}]italic_s ∈ [ 0 , 2 start_POSTSUPERSCRIPT italic_μ ( italic_i + 1 ) / 2 + italic_δ end_POSTSUPERSCRIPT ](δ𝛿\deltaitalic_δ是一个小量),即可使每一个e𝑒eitalic_e中的μ(i+1)𝜇𝑖1\mu(i+1)italic_μ ( italic_i + 1 )位特定值，都对应有至少一对t,s𝑡𝑠t,sitalic_t , italic_s符合条件。 2）建立tp𝑡𝑝tpitalic_t italic_p表。将t∈[0,2μ(i+1)/2+δ]𝑡0superscript2𝜇𝑖12𝛿t\in[0,2^{\mu(i+1)/2+\delta}]italic_t ∈ [ 0 , 2 start_POSTSUPERSCRIPT italic_μ ( italic_i + 1 ) / 2 + italic_δ end_POSTSUPERSCRIPT ]的tp𝑡𝑝tpitalic_t italic_p的值按照(tp)ρ+η+α−μ(i+1)/2:ρ+η+αsubscript𝑡𝑝:𝜌𝜂𝛼𝜇𝑖12𝜌𝜂𝛼(tp)_{\rho+\eta+\alpha-\mu(i+1)/2:\rho+\eta+\alpha}( italic_t italic_p ) start_POSTSUBSCRIPT italic_ρ + italic_η + italic_α - italic_μ ( italic_i + 1 ) / 2 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT的取值进行分组，每种取值各分为一组，共2μ(i+1)/2superscript2𝜇𝑖122^{\mu(i+1)/2}2 start_POSTSUPERSCRIPT italic_μ ( italic_i + 1 ) / 2 end_POSTSUPERSCRIPT个组。每组中保存符合满足取值要求的所有的t𝑡titalic_t。注意，平均每个小组中大约有2δsuperscript2𝛿2^{\delta}2 start_POSTSUPERSCRIPT italic_δ end_POSTSUPERSCRIPT个t𝑡titalic_t。 3）同理，建立sp𝑠𝑝spitalic_s italic_p表。 4）按照预计算表的建设要求，T[i][j].eρ+η+α−μ(i+1):ρ+η+α=jformulae-sequence𝑇delimited-[]𝑖delimited-[]𝑗subscript𝑒:𝜌𝜂𝛼𝜇𝑖1𝜌𝜂𝛼𝑗T[i][j].e_{\rho+\eta+\alpha-\mu(i+1):\rho+\eta+\alpha}=jitalic_T [ italic_i ] [ italic_j ] . italic_e start_POSTSUBSCRIPT italic_ρ + italic_η + italic_α - italic_μ ( italic_i + 1 ) : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = italic_j, 则 (tp)ρ+η+α−μ(i+1)/2:ρ+η+α+(sq)ρ+η+α−μ(i+1)/2:ρ+η+αsubscript𝑡𝑝:𝜌𝜂𝛼𝜇𝑖12𝜌𝜂𝛼subscript𝑠𝑞:𝜌𝜂𝛼𝜇𝑖12𝜌𝜂𝛼(tp)_{\rho+\eta+\alpha-\mu(i+1)/2:\rho+\eta+\alpha}+(sq)_{\rho+\eta+\alpha-\mu% (i+1)/2:\rho+\eta+\alpha}( italic_t italic_p ) start_POSTSUBSCRIPT italic_ρ + italic_η + italic_α - italic_μ ( italic_i + 1 ) / 2 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT + ( italic_s italic_q ) start_POSTSUBSCRIPT italic_ρ + italic_η + italic_α - italic_μ ( italic_i + 1 ) / 2 : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT近似为0。所以tp𝑡𝑝tpitalic_t italic_p表中的每一个小组，只需跟2个sq𝑠𝑞sqitalic_s italic_q表中的小组匹配。 5）遍历tp𝑡𝑝tpitalic_t italic_p表中的所有小组。对于每一个tp𝑡𝑝tpitalic_t italic_p表中的小组，遍历与其匹配的sq𝑠𝑞sqitalic_s italic_q表中的小组。对于每一对tp𝑡𝑝tpitalic_t italic_p小组和sq𝑠𝑞sqitalic_s italic_q小组，再遍历其中每种t𝑡titalic_t和s𝑠sitalic_s的取值可能，寻找符合要求的t𝑡titalic_t和s𝑠sitalic_s。 Figure 3: 预计算表搜索过程 6.3 计算预计算表R𝑅Ritalic_R 表R𝑅Ritalic_R的建立过程与表T𝑇Titalic_T类似，但是需要多建立一个索引，以方便根据t𝑡titalic_t和s𝑠sitalic_s的范围索引目标表项。索引建立方法如下（参见Figure 4）： 1）建立两层索引，第一层为根据t𝑡titalic_t值进行的索引。把R𝑅Ritalic_R中t𝑡titalic_t的可能取值空间[−2κ+1,2κ+1]superscript2𝜅1superscript2𝜅1[-2^{\kappa+1},2^{\kappa+1}][ - 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT , 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT ]按照2α/2superscript2𝛼22^{\alpha/2}2 start_POSTSUPERSCRIPT italic_α / 2 end_POSTSUPERSCRIPT大小进行分块，分为2κ+2−α/2superscript2𝜅2𝛼22^{\kappa+2-\alpha/2}2 start_POSTSUPERSCRIPT italic_κ + 2 - italic_α / 2 end_POSTSUPERSCRIPT块，每块是一个索引项。 2）第一层索引的每一项指向一个不同的第二层索引。第二层索引为根据s𝑠sitalic_s值进行的索引，把R𝑅Ritalic_R中s𝑠sitalic_s的可能取值空间[−2κ+1,2κ+1]superscript2𝜅1superscript2𝜅1[-2^{\kappa+1},2^{\kappa+1}][ - 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT , 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT ]按照2α/2superscript2𝛼22^{\alpha/2}2 start_POSTSUPERSCRIPT italic_α / 2 end_POSTSUPERSCRIPT大小进行分块，分为2κ+2−α/2superscript2𝜅2𝛼22^{\kappa+2-\alpha/2}2 start_POSTSUPERSCRIPT italic_κ + 2 - italic_α / 2 end_POSTSUPERSCRIPT块（分块的方式与t𝑡titalic_t相同），每块是一个索引项。每个索引项指向的是目标的表项列表(t,s,e)𝑡𝑠𝑒(t,s,e)( italic_t , italic_s , italic_e )。 要指出的是： 1）因为每个索引项代表的t𝑡titalic_t和 s𝑠sitalic_s取值的可能性各为2α/2superscript2𝛼22^{\alpha/2}2 start_POSTSUPERSCRIPT italic_α / 2 end_POSTSUPERSCRIPT，则总共为2αsuperscript2𝛼2^{\alpha}2 start_POSTSUPERSCRIPT italic_α end_POSTSUPERSCRIPT种取值，与查找区的全部可能性相同。又因为表R𝑅Ritalic_R的查找区允许4个值，所以每个第二层索引项指向的“表项列表”大约指向4个表项。 2）算法第10步的R[j].tformulae-sequence𝑅delimited-[]𝑗𝑡R[j].titalic_R [ italic_j ] . italic_t和R[j].sformulae-sequence𝑅delimited-[]𝑗𝑠R[j].sitalic_R [ italic_j ] . italic_s的搜索空间为2α/2superscript2𝛼22^{\alpha/2}2 start_POSTSUPERSCRIPT italic_α / 2 end_POSTSUPERSCRIPT。所以平均命中一个“表项列表”，大约4个表项。 Figure 4: 查找表R的索引结构 7 算法复杂度分析 7.1 建表复杂度 预计算表时，主要操作为全量扫描tp𝑡𝑝tpitalic_t italic_p，其复杂度为O(2κ+1)𝑂superscript2𝜅1O(2^{\kappa+1})italic_O ( 2 start_POSTSUPERSCRIPT italic_κ + 1 end_POSTSUPERSCRIPT )复杂度; 7.2 解密复杂度 解密算法第3-9步，共需要θ𝜃\thetaitalic_θ次循环，共θ𝜃\thetaitalic_θ次大整数加法运算。θ𝜃\thetaitalic_θ一般不大，比如示例中为5。 算法第10步筛选出来的表项大约4项，大约需要4次大整数加法运算。 整体来看，解密大约需要9次左右大整数加法运算。 8 局限性说明 1、加法次数泄漏 2、解密所得明文为近似结果，低位可能有误差 3、支持的加法次数有上限 4、预计算消耗资源较大，但仅需在密钥生成时做一次 算法2 1 变量 𝐗𝐠:𝐡subscript𝐗:𝐠𝐡\mathbf{X_{g:h}}bold_X start_POSTSUBSCRIPT bold_g : bold_h end_POSTSUBSCRIPT： Xg:hsubscript𝑋:𝑔ℎX_{g:h}italic_X start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT是指X𝑋Xitalic_X从第g𝑔gitalic_g比特到第hℎhitalic_h比特的数据(含g𝑔gitalic_g，不含hℎhitalic_h；g≤h𝑔ℎg\leq hitalic_g ≤ italic_h;第00比特为最低位)。若X𝑋Xitalic_X为负数，令Xg:h=−|X|g:hsubscript𝑋:𝑔ℎsubscript𝑋:𝑔ℎX_{g:h}=-|X|_{g:h}italic_X start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT = - | italic_X | start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT。 Xg:∞subscript𝑋:𝑔X_{g:\infty}italic_X start_POSTSUBSCRIPT italic_g : ∞ end_POSTSUBSCRIPT指X𝑋Xitalic_X从第g𝑔gitalic_g比特到最高位的数据（含g𝑔gitalic_g）。 记Xg:h¯=2gXg:hsubscript𝑋¯:𝑔ℎsuperscript2𝑔subscript𝑋:𝑔ℎX_{\overline{g:h}}=2^{g}X_{g:h}italic_X start_POSTSUBSCRIPT over¯ start_ARG italic_g : italic_h end_ARG end_POSTSUBSCRIPT = 2 start_POSTSUPERSCRIPT italic_g end_POSTSUPERSCRIPT italic_X start_POSTSUBSCRIPT italic_g : italic_h end_POSTSUBSCRIPT，Xg:∞¯=2gXg:∞subscript𝑋¯:𝑔superscript2𝑔subscript𝑋:𝑔X_{\overline{g:\infty}}=2^{g}X_{g:\infty}italic_X start_POSTSUBSCRIPT over¯ start_ARG italic_g : ∞ end_ARG end_POSTSUBSCRIPT = 2 start_POSTSUPERSCRIPT italic_g end_POSTSUPERSCRIPT italic_X start_POSTSUBSCRIPT italic_g : ∞ end_POSTSUBSCRIPT 数据结构：算法及证明过程中部分变量采用下面的数据结构： 高位随机数(ρ𝜌\rhoitalic_ρ) ∥∥\|∥ 明文区(η𝜂\etaitalic_η) ∥∥\|∥ 缓冲区(α𝛼\alphaitalic_α) ∥∥\|∥ 低位随机数(ρ𝜌\rhoitalic_ρ) • 高、低位随机数各ρ𝜌\rhoitalic_ρ比特,用于存放随机数。 • 明文区为η𝜂\etaitalic_η（例如64）比特。 • 缓冲区为α𝛼\alphaitalic_α(例如32)比特，用于解决低位随机数运算进位对明文的影响，要求密文的最大加减法运算次数为2α−4superscript2𝛼42^{\alpha-4}2 start_POSTSUPERSCRIPT italic_α - 4 end_POSTSUPERSCRIPT。 • 上述变量满足2ρ+α+η=γ2𝜌𝛼𝜂𝛾2\rho+\alpha+\eta=\gamma2 italic_ρ + italic_α + italic_η = italic_γ。 密钥：{p,q,a,b}𝑝𝑞𝑎𝑏\{p,q,a,b\}{ italic_p , italic_q , italic_a , italic_b }，其中p,q𝑝𝑞p,qitalic_p , italic_q为γ𝛾\gammaitalic_γ（例如1024）比特大素数，且明文区和缓冲区对应的位置为0，即pρ:ρ+η+α=0subscript𝑝:𝜌𝜌𝜂𝛼0p_{\rho:\rho+\eta+\alpha}=0italic_p start_POSTSUBSCRIPT italic_ρ : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0，qρ:ρ+η+α=0subscript𝑞:𝜌𝜌𝜂𝛼0q_{\rho:\rho+\eta+\alpha}=0italic_q start_POSTSUBSCRIPT italic_ρ : italic_ρ + italic_η + italic_α end_POSTSUBSCRIPT = 0；a,b𝑎𝑏a,bitalic_a , italic_b为γ𝛾\gammaitalic_γ比特。 明文：m𝑚mitalic_m，满足m∈[−2η−1,2η−1−1]𝑚superscript2𝜂1superscript2𝜂11m\in[-2^{\eta-1},2^{\eta-1}-1]italic_m ∈ [ - 2 start_POSTSUPERSCRIPT italic_η - 1 end_POSTSUPERSCRIPT , 2 start_POSTSUPERSCRIPT italic_η - 1 end_POSTSUPERSCRIPT - 1 ]的整数，且执行同态运算后m𝑚mitalic_m仍需保证在该范围内。 密文：(x,y)𝑥𝑦(x,y)( italic_x , italic_y ), 为ψ𝜓\psiitalic_ψ比特(ψ≥2γ𝜓2𝛾\psi\geq 2\gammaitalic_ψ ≥ 2 italic_γ,这里暂时取ψ𝜓\psiitalic_ψ为2γ2𝛾2\gamma2 italic_γ,例如2048)。 2 加密 加密的核心思想与算法一相同，把明文分成两个分片，然后把两个分片按照前述数据结构使用随机数“夹在中间”，最后再分别将两个分片隐藏在近似公因子问题的误差部分中，具体过程如下： 生成两个ρ𝜌\rhoitalic_ρ比特正随机数ξ,ζ𝜉𝜁\xi,\zetaitalic_ξ , italic_ζ，一个γ𝛾\gammaitalic_γ比特正随机数τ𝜏\tauitalic_τ，定义明文m𝑚mitalic_m的秘密分享为： {u=2ρ+η+αξ+2ρ+αm+ζ−τρ:ρ+η+α¯v=τcases𝑢superscript2𝜌𝜂𝛼𝜉superscript2𝜌𝛼𝑚𝜁subscript𝜏¯:𝜌𝜌𝜂𝛼𝑣𝜏\left\{\begin{array}[]{l}u=2^{\rho+\eta+\alpha}\xi+2^{\rho+\alpha}m+\zeta-\tau% _{\overline{\rho:\rho+\eta+\alpha}}\\ v=\tau\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_u = 2 start_POSTSUPERSCRIPT italic_ρ + italic_η + italic_α end_POSTSUPERSCRIPT italic_ξ + 2 start_POSTSUPERSCRIPT italic_ρ + italic_α end_POSTSUPERSCRIPT italic_m + italic_ζ - italic_τ start_POSTSUBSCRIPT over¯ start_ARG italic_ρ : italic_ρ + italic_η + italic_α end_ARG end_POSTSUBSCRIPT end_CELL end_ROW start_ROW start_CELL italic_v = italic_τ end_CELL end_ROW end_ARRAY 计算密文(x,y)𝑥𝑦(x,y)( italic_x , italic_y )： {x=(au)%p+r1py=(bv)%q+r2qcases𝑥percent𝑎𝑢𝑝subscript𝑟1𝑝𝑦percent𝑏𝑣𝑞subscript𝑟2𝑞\left\{\begin{array}[]{l}x=(au)\%p+r_{1}p\\ y=(bv)\%q+r_{2}q\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_x = ( italic_a italic_u ) % italic_p + italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT italic_p end_CELL end_ROW start_ROW start_CELL italic_y = ( italic_b italic_v ) % italic_q + italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT italic_q end_CELL end_ROW end_ARRAY , 其中r1,r2subscript𝑟1subscript𝑟2r_{1},r_{2}italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT是分别满足[0,2ψ/p−1],[0,2ψ/q−1]0superscript2𝜓𝑝10superscript2𝜓𝑞1[0,2^{\psi}/p-1],[0,2^{\psi}/q-1][ 0 , 2 start_POSTSUPERSCRIPT italic_ψ end_POSTSUPERSCRIPT / italic_p - 1 ] , [ 0 , 2 start_POSTSUPERSCRIPT italic_ψ end_POSTSUPERSCRIPT / italic_q - 1 ]的均匀分布的随机数。 3 同态加 记(x1,y1)subscript𝑥1subscript𝑦1(x_{1},y_{1})( italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT )和(x2,y2)subscript𝑥2subscript𝑦2(x_{2},y_{2})( italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT )为两个密文，则它们的和(x,y𝑥𝑦x,yitalic_x , italic_y)的计算方法为： x=x1+x2𝑥subscript𝑥1subscript𝑥2x=x_{1}+x_{2}italic_x = italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT + italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，y=y2+y2𝑦subscript𝑦2subscript𝑦2y=y_{2}+y_{2}italic_y = italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT + italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT 4 同态减 记(x1,y1)subscript𝑥1subscript𝑦1(x_{1},y_{1})( italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT )和(x2,y2)subscript𝑥2subscript𝑦2(x_{2},y_{2})( italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT )为两个密文，则它们的差(x,y𝑥𝑦x,yitalic_x , italic_y)的计算方法为： x=x1−x2𝑥subscript𝑥1subscript𝑥2x=x_{1}-x_{2}italic_x = italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT - italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，y=y2−y2𝑦subscript𝑦2subscript𝑦2y=y_{2}-y_{2}italic_y = italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT - italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT 5 解密 令M′=(a−1x)%p+(b−1y)%qsuperscript𝑀′percentsuperscript𝑎1𝑥𝑝percentsuperscript𝑏1𝑦𝑞M^{{}^{\prime}}=(a^{-1}x)\%p+(b^{-1}y)\%qitalic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x ) % italic_p + ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y ) % italic_q，则 若Mρ+α−1:ρ+α′=0subscriptsuperscript𝑀′:𝜌𝛼1𝜌𝛼0M^{{}^{\prime}}_{\rho+\alpha-1:\rho+\alpha}=0italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α - 1 : italic_ρ + italic_α end_POSTSUBSCRIPT = 0, 当m≥0𝑚0m\geq 0italic_m ≥ 0时，m=Mρ+α:ρ+α+η′𝑚subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂m=M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}italic_m = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT 当m<0𝑚0m<0italic_m < 0时，m=Mρ+α:ρ+α+η′−2η𝑚subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂superscript2𝜂m=M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}-2^{\eta}italic_m = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT 若Mρ+α−1:ρ+α′=1subscriptsuperscript𝑀′:𝜌𝛼1𝜌𝛼1M^{{}^{\prime}}_{\rho+\alpha-1:\rho+\alpha}=1italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α - 1 : italic_ρ + italic_α end_POSTSUBSCRIPT = 1, 当m−1≥0𝑚10m-1\geq 0italic_m - 1 ≥ 0时，m=Mρ+α:ρ+α+η′+1𝑚subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂1m=M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}+1italic_m = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT + 1 当m−1<0𝑚10m-1<0italic_m - 1 < 0时，m=Mρ+α:ρ+α+η′+1−2η𝑚subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂1superscript2𝜂m=M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}+1-2^{\eta}italic_m = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT + 1 - 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT 6 解密思路 假设密文(x,y)𝑥𝑦(x,y)( italic_x , italic_y )（对应明文记为m𝑚mitalic_m，对应明文的秘密分享记为u𝑢uitalic_u，v𝑣vitalic_v）是由 (x1,y1)subscript𝑥1subscript𝑦1(x_{1},y_{1})( italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT )，(x2,y2)subscript𝑥2subscript𝑦2(x_{2},y_{2})( italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT )，…，(xw,yw)subscript𝑥𝑤subscript𝑦𝑤(x_{w},y_{w})( italic_x start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT )相加减得来的（对应的明文记为m1subscript𝑚1m_{1}italic_m start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，m2subscript𝑚2m_{2}italic_m start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，mwsubscript𝑚𝑤m_{w}italic_m start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT。对应的秘密分享分别为u1subscript𝑢1u_{1}italic_u start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，u2subscript𝑢2u_{2}italic_u start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，uwsubscript𝑢𝑤u_{w}italic_u start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT；v1subscript𝑣1v_{1}italic_v start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，v2subscript𝑣2v_{2}italic_v start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…，vwsubscript𝑣𝑤v_{w}italic_v start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT）。 由加密、同态加和同态减部分可知 {x=a∑i=1w(−1)σ(i)ui+r1′py=b∑i=1w(−1)σ(i)vi+r2′qcases𝑥𝑎superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖superscriptsubscript𝑟1′𝑝𝑦𝑏superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖superscriptsubscript𝑟2′𝑞\left\{\begin{array}[]{l}x=a\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}+r_{1}^{{}^{% \prime}}p\\ y=b\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}+r_{2}^{{}^{\prime}}q\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_x = italic_a ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p end_CELL end_ROW start_ROW start_CELL italic_y = italic_b ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q end_CELL end_ROW end_ARRAY , 其中(−1)σ(i)=1superscript1𝜎𝑖1(-1)^{\sigma(i)}=1( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT = 1代表对相应密文做加法，(−1)σ(i)=−1superscript1𝜎𝑖1(-1)^{\sigma(i)}=-1( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT = - 1代表对相应密文做减法。r1′superscriptsubscript𝑟1′r_{1}^{{}^{\prime}}italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT, r2′superscriptsubscript𝑟2′r_{2}^{{}^{\prime}}italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT分别对应为p𝑝pitalic_p, q𝑞qitalic_q前的系数和。 即 {∑i=1w(−1)σ(i)ui≡a−1x(modp)∑i=1w(−1)σ(i)vi≡b−1y(modq)casessuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖annotatedsuperscript𝑎1𝑥pmod𝑝superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖annotatedsuperscript𝑏1𝑦pmod𝑞\left\{\begin{array}[]{l}\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}\equiv a^{-1}x% \pmod{p}\\ \sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}\equiv b^{-1}y\pmod{q}\end{array}\right.{ start_ARRAY start_ROW start_CELL ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≡ italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x start_MODIFIER ( roman_mod start_ARG italic_p end_ARG ) end_MODIFIER end_CELL end_ROW start_ROW start_CELL ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ≡ italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y start_MODIFIER ( roman_mod start_ARG italic_q end_ARG ) end_MODIFIER end_CELL end_ROW end_ARRAY 记 ∑i=1w(−1)σ(i)ui=(a−1x(modp))+tpsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖annotatedsuperscript𝑎1𝑥pmod𝑝𝑡𝑝\displaystyle\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}=(a^{-1}x\pmod{p})+tp∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x start_MODIFIER ( roman_mod start_ARG italic_p end_ARG ) end_MODIFIER ) + italic_t italic_p (8) ∑i=1w(−1)σ(i)vi=(b−1y(modq))+sqsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖annotatedsuperscript𝑏1𝑦pmod𝑞𝑠𝑞\displaystyle\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}=(b^{-1}y\pmod{q})+sq∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y start_MODIFIER ( roman_mod start_ARG italic_q end_ARG ) end_MODIFIER ) + italic_s italic_q 则有∑i=1w(−1)σ(i)ui+∑i=1w(−1)σ(i)vi=(a−1x(modp))+(b−1y(modq))+tp+sq=M′+tp+sqsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖annotatedsuperscript𝑎1𝑥pmod𝑝annotatedsuperscript𝑏1𝑦pmod𝑞𝑡𝑝𝑠𝑞superscript𝑀′𝑡𝑝𝑠𝑞\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}+\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}=(a^{-1% }x\pmod{p})+(b^{-1}y\pmod{q})+tp+sq=M^{{}^{\prime}}+tp+sq∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x start_MODIFIER ( roman_mod start_ARG italic_p end_ARG ) end_MODIFIER ) + ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y start_MODIFIER ( roman_mod start_ARG italic_q end_ARG ) end_MODIFIER ) + italic_t italic_p + italic_s italic_q = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t italic_p + italic_s italic_q，注意，此时t𝑡titalic_t和s𝑠sitalic_s可以为负。 由于p𝑝pitalic_p的ρ𝜌\rhoitalic_ρ到ρ+α+η𝜌𝛼𝜂\rho+\alpha+\etaitalic_ρ + italic_α + italic_η位为0，tp𝑡𝑝tpitalic_t italic_p可以看成t𝑡titalic_t与p𝑝pitalic_p的高位部分和低位部分分别相乘。当t𝑡titalic_t比较小的时候，t𝑡titalic_t与p𝑝pitalic_p的低位部分相乘最高影响到ρ+α𝜌𝛼\rho+\alphaitalic_ρ + italic_α位，则tp𝑡𝑝tpitalic_t italic_p的ρ+α𝜌𝛼\rho+\alphaitalic_ρ + italic_α到ρ+α+η𝜌𝛼𝜂\rho+\alpha+\etaitalic_ρ + italic_α + italic_η位为0。同理，(tp+sq)𝑡𝑝𝑠𝑞(tp+sq)( italic_t italic_p + italic_s italic_q )的ρ+α𝜌𝛼\rho+\alphaitalic_ρ + italic_α到ρ+α+η𝜌𝛼𝜂\rho+\alpha+\etaitalic_ρ + italic_α + italic_η位为0，从而(tp+sq)𝑡𝑝𝑠𝑞(tp+sq)( italic_t italic_p + italic_s italic_q )最多只会对M′superscript𝑀′M^{\prime}italic_M start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT明文区产生一位的影响。若第ρ+α+η−1𝜌𝛼𝜂1\rho+\alpha+\eta-1italic_ρ + italic_α + italic_η - 1位为0，说明低位没有向高位产生借位，则，∑i=1wui+∑i=1wvisuperscriptsubscript𝑖1𝑤subscript𝑢𝑖superscriptsubscript𝑖1𝑤subscript𝑣𝑖\sum_{i=1}^{w}u_{i}+\sum_{i=1}^{w}v_{i}∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT与M′superscript𝑀′M^{{}^{\prime}}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT的ρ+α𝜌𝛼\rho+\alphaitalic_ρ + italic_α到ρ+α+η𝜌𝛼𝜂\rho+\alpha+\etaitalic_ρ + italic_α + italic_η位相同；若第ρ+α+η−1𝜌𝛼𝜂1\rho+\alpha+\eta-1italic_ρ + italic_α + italic_η - 1位为1，说明低位向高位产生了借位，则，∑i=1wui+∑i=1wvisuperscriptsubscript𝑖1𝑤subscript𝑢𝑖superscriptsubscript𝑖1𝑤subscript𝑣𝑖\sum_{i=1}^{w}u_{i}+\sum_{i=1}^{w}v_{i}∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT等于M′superscript𝑀′M^{{}^{\prime}}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT的ρ+α𝜌𝛼\rho+\alphaitalic_ρ + italic_α到ρ+α+η𝜌𝛼𝜂\rho+\alpha+\etaitalic_ρ + italic_α + italic_η位的值加1。从而解密过程成立。 严格的证明参见下一章。 7 解密正确性证明 假设密文(x,y)𝑥𝑦(x,y)( italic_x , italic_y )（对应明文记为m𝑚mitalic_m，对应明文的秘密分享记为u𝑢uitalic_u，v𝑣vitalic_v）是由 (x1,y1)subscript𝑥1subscript𝑦1(x_{1},y_{1})( italic_x start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT )，(x2,y2)subscript𝑥2subscript𝑦2(x_{2},y_{2})( italic_x start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT )，…,(xw,yw)subscript𝑥𝑤subscript𝑦𝑤(x_{w},y_{w})( italic_x start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT , italic_y start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT )相加减得来的（对应的明文记为m1subscript𝑚1m_{1}italic_m start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，m2subscript𝑚2m_{2}italic_m start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…,mwsubscript𝑚𝑤m_{w}italic_m start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT，对应的秘密分享分别为u1subscript𝑢1u_{1}italic_u start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，u2subscript𝑢2u_{2}italic_u start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…,uwsubscript𝑢𝑤u_{w}italic_u start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT，v1subscript𝑣1v_{1}italic_v start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT，v2subscript𝑣2v_{2}italic_v start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT，…,vwsubscript𝑣𝑤v_{w}italic_v start_POSTSUBSCRIPT italic_w end_POSTSUBSCRIPT）。 由加密章节可知，(ui+vi)ρ+α:ρ+α+η=misubscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝛼𝜌𝛼𝜂subscript𝑚𝑖(u_{i}+v_{i})_{\rho+\alpha:\rho+\alpha+\eta}=m_{i}( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = italic_m start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT，(ui+vi)ρ:ρ+αsubscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝜌𝛼(u_{i}+v_{i})_{\rho:\rho+\alpha}( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ : italic_ρ + italic_α end_POSTSUBSCRIPT = 0或1。 定理： 解密算法正确。 Proof. 由 {x=a∑i=1w(−1)σ(i)ui+r1′py=b∑i=1w(−1)σ(i)vi+r2′qcases𝑥𝑎superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖superscriptsubscript𝑟1′𝑝𝑦𝑏superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖superscriptsubscript𝑟2′𝑞\left\{\begin{array}[]{l}x=a\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}+r_{1}^{{}^{% \prime}}p\\ y=b\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}+r_{2}^{{}^{\prime}}q\end{array}\right.{ start_ARRAY start_ROW start_CELL italic_x = italic_a ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_r start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p end_CELL end_ROW start_ROW start_CELL italic_y = italic_b ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_r start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q end_CELL end_ROW end_ARRAY 可知，存在t𝑡titalic_t和s𝑠sitalic_s使得∑i=1w(−1)σ(i)ui=(a−1x)%p+tpsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖percentsuperscript𝑎1𝑥𝑝𝑡𝑝\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}=(a^{-1}x)\%p+tp∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x ) % italic_p + italic_t italic_p, ∑i=1w(−1)σ(i)vi=(b−1y)%q+sqsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖percentsuperscript𝑏1𝑦𝑞𝑠𝑞\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}=(b^{-1}y)\%q+sq∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y ) % italic_q + italic_s italic_q 则 ∑i=1w(−1)σ(i)(ui+vi)=∑i=1w(−1)σ(i)ui+∑i=1w(−1)σ(i)vi=(a−1x)%p+tp+(b−1y)%q+sq=(∑i=1w(−1)σ(i)ui)%p+tp+(∑i=1w(−1)σ(i)vi)%q+sq=M′+tp+sqsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖subscript𝑣𝑖superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖percentsuperscript𝑎1𝑥𝑝𝑡𝑝percentsuperscript𝑏1𝑦𝑞𝑠𝑞percentsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖𝑝𝑡𝑝percentsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑣𝑖𝑞𝑠𝑞superscript𝑀′𝑡𝑝𝑠𝑞\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})\\ =\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}+\sum_{i=1}^{w}(-1)^{\sigma(i)}v_{i}\\ =(a^{-1}x)\%p+tp+(b^{-1}y)\%q+sq\\ =(\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i})\%p+tp+(\sum_{i=1}^{w}(-1)^{\sigma(i)}v_% {i})\%q+sq\\ =M^{{}^{\prime}}+tp+sq∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ( italic_a start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_x ) % italic_p + italic_t italic_p + ( italic_b start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_y ) % italic_q + italic_s italic_q = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) % italic_p + italic_t italic_p + ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) % italic_q + italic_s italic_q = italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT + italic_t italic_p + italic_s italic_q 由于ui<2psubscript𝑢𝑖2𝑝u_{i}<2pitalic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT < 2 italic_p，从而−2p<(−1)σ(i)ui<2p2𝑝superscript1𝜎𝑖subscript𝑢𝑖2𝑝-2p<(-1)^{\sigma(i)}u_{i}<2p- 2 italic_p < ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT < 2 italic_p, 从而−2wp<∑i=1w(−1)σ(i)ui<2wp2𝑤𝑝superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖2𝑤𝑝-2wp<\sum_{i=1}^{w}(-1)^{\sigma(i)}u_{i}<2wp- 2 italic_w italic_p < ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT < 2 italic_w italic_p，可知t∈(−2w,2w)𝑡2𝑤2𝑤t\in(-2w,2w)italic_t ∈ ( - 2 italic_w , 2 italic_w )，同理可知s∈(−2w,2w)𝑠2𝑤2𝑤s\in(-2w,2w)italic_s ∈ ( - 2 italic_w , 2 italic_w )。 则上式可以改写为M′=∑i=1w(−1)σ(i)(ui+vi)−tp−sq=∑i=1w(−1)σ(i)(ui+vi)+t′p+s′qsuperscript𝑀′superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖subscript𝑣𝑖𝑡𝑝𝑠𝑞superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖subscript𝑣𝑖superscript𝑡′𝑝superscript𝑠′𝑞M^{{}^{\prime}}=\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})-tp-sq=\sum_{i=1}^{% w}(-1)^{\sigma(i)}(u_{i}+v_{i})+t^{{}^{\prime}}p+s^{{}^{\prime}}qitalic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) - italic_t italic_p - italic_s italic_q = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q，其中t′=−tsuperscript𝑡′𝑡t^{{}^{\prime}}=-titalic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = - italic_t, s′=−ssuperscript𝑠′𝑠s^{{}^{\prime}}=-sitalic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = - italic_s，t′∈(−2w,2w)superscript𝑡′2𝑤2𝑤t^{{}^{\prime}}\in(-2w,2w)italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ ( - 2 italic_w , 2 italic_w )，s′∈(−2w,2w)superscript𝑠′2𝑤2𝑤s^{{}^{\prime}}\in(-2w,2w)italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ ( - 2 italic_w , 2 italic_w )。 M′=∑i=1w(−1)σ(i)(ui+vi)+t′p+s′q=∑i=1w((−1)σ(i)(ui+vi)ρ+α+η:∞¯+(−1)σ(i)(ui+vi)ρ+α:ρ+α+η¯+(−1)σ(i)(ui+vi)0:ρ+α)+t′p0:ρ+t′pρ+α+η:∞¯+s′q0:ρ+s′qρ+α+η:∞¯=(∑i=1w(−1)σ(i)(ui+vi)ρ+α+η:∞¯+t′pρ+α+η:∞¯+s′qρ+α+η:∞¯)+∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η¯+(∑i=1w(−1)σ(i)(ui+vi)0:ρ+α+t′p0:ρ+s′q0:ρ)superscript𝑀′superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑢𝑖subscript𝑣𝑖superscript𝑡′𝑝superscript𝑠′𝑞superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜂superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscript𝑡′subscript𝑝:0𝜌superscript𝑡′subscript𝑝¯:𝜌𝛼𝜂superscript𝑠′subscript𝑞:0𝜌superscript𝑠′subscript𝑞¯:𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜂superscript𝑡′subscript𝑝¯:𝜌𝛼𝜂superscript𝑠′subscript𝑞¯:𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscript𝑡′subscript𝑝:0𝜌superscript𝑠′subscript𝑞:0𝜌M^{{}^{\prime}}=\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})+t^{{}^{\prime}}p+s% ^{{}^{\prime}}q\\ =\sum_{i=1}^{w}((-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha+\eta:% \infty}}+(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta% }}+(-1)^{\sigma(i)}(u_{i}+v_{i})_{0:\rho+\alpha})+t^{{}^{\prime}}p_{0:\rho}+t^% {{}^{\prime}}p_{\overline{\rho+\alpha+\eta:\infty}}+s^{{}^{\prime}}q_{0:\rho}+% s^{{}^{\prime}}q_{\overline{\rho+\alpha+\eta:\infty}}\\ =(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha+\eta:% \infty}}+t^{{}^{\prime}}p_{\overline{\rho+\alpha+\eta:\infty}}+s^{{}^{\prime}}% q_{\overline{\rho+\alpha+\eta:\infty}})+\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v% _{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta}}+(\sum_{i=1}^{w}(-1)^{\sigma(i)% }(u_{i}+v_{i})_{0:\rho+\alpha}+t^{{}^{\prime}}p_{0:\rho}+s^{{}^{\prime}}q_{0:% \rho})italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT + ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT + ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT ) + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α + italic_η : ∞ end_ARG end_POSTSUBSCRIPT ) + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT + ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT ) 由于(ui+vi)ρ:ρ+αsubscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝜌𝛼(u_{i}+v_{i})_{\rho:\rho+\alpha}( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ : italic_ρ + italic_α end_POSTSUBSCRIPT = 0或1，当加法次数w<2α−4𝑤superscript2𝛼4w<2^{\alpha-4}italic_w < 2 start_POSTSUPERSCRIPT italic_α - 4 end_POSTSUPERSCRIPT时，|∑i=1w(−1)σ(i)(ui+vi)0:ρ+α|≤∑i=1w(ui+vi)0:ρ+α=∑i=1w(ui+vi)0:ρ+1<2ρ+1*2α−4<2ρ+α−2superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscriptsubscript𝑖1𝑤subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscriptsubscript𝑖1𝑤subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌1superscript2𝜌1superscript2𝛼4superscript2𝜌𝛼2\left|\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{0:\rho+\alpha}\right|\leq% \sum_{i=1}^{w}(u_{i}+v_{i})_{0:\rho+\alpha}=\sum_{i=1}^{w}(u_{i}+v_{i})_{0:% \rho+1}<2^{\rho+1}*2^{\alpha-4}<2^{\rho+\alpha-2}| ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT | ≤ ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + 1 end_POSTSUBSCRIPT < 2 start_POSTSUPERSCRIPT italic_ρ + 1 end_POSTSUPERSCRIPT * 2 start_POSTSUPERSCRIPT italic_α - 4 end_POSTSUPERSCRIPT < 2 start_POSTSUPERSCRIPT italic_ρ + italic_α - 2 end_POSTSUPERSCRIPT。 由于t′∈(−2w,2w)superscript𝑡′2𝑤2𝑤t^{{}^{\prime}}\in(-2w,2w)italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT ∈ ( - 2 italic_w , 2 italic_w ), 从而|t′|<2w≤2*2α−4=2α−3superscript𝑡′2𝑤2superscript2𝛼4superscript2𝛼3\left|t^{{}^{\prime}}\right|<2w\leq 2*2^{\alpha-4}=2^{\alpha-3}| italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT | < 2 italic_w ≤ 2 * 2 start_POSTSUPERSCRIPT italic_α - 4 end_POSTSUPERSCRIPT = 2 start_POSTSUPERSCRIPT italic_α - 3 end_POSTSUPERSCRIPT, 同理, |s′|<2α−3superscript𝑠′superscript2𝛼3\left|s^{{}^{\prime}}\right|<2^{\alpha-3}| italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT | < 2 start_POSTSUPERSCRIPT italic_α - 3 end_POSTSUPERSCRIPT, 易得|(t′p0:ρ+s′q0:ρ)|<2ρ+α−2superscript𝑡′subscript𝑝:0𝜌superscript𝑠′subscript𝑞:0𝜌superscript2𝜌𝛼2\left|(t^{{}^{\prime}}p_{0:\rho}+s^{{}^{\prime}}q_{0:\rho})\right|<2^{\rho+% \alpha-2}| ( italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT ) | < 2 start_POSTSUPERSCRIPT italic_ρ + italic_α - 2 end_POSTSUPERSCRIPT。 由上述分析可得，|(∑i=1w(−1)σ(i)(ui+vi)0:ρ+α+t′p0:ρ+s′q0:ρ)|<2ρ+α−1superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscript𝑡′subscript𝑝:0𝜌superscript𝑠′subscript𝑞:0𝜌superscript2𝜌𝛼1\left|(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{0:\rho+\alpha}+t^{{}^{% \prime}}p_{0:\rho}+s^{{}^{\prime}}q_{0:\rho})\right|<2^{\rho+\alpha-1}| ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT ) | < 2 start_POSTSUPERSCRIPT italic_ρ + italic_α - 1 end_POSTSUPERSCRIPT。 下面进行分类讨论： 情况1. (∑i=1w(−1)σ(i)(ui+vi)0:ρ+α+t′p0:ρ+s′q0:ρ)≥0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscript𝑡′subscript𝑝:0𝜌superscript𝑠′subscript𝑞:0𝜌0(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{0:\rho+\alpha}+t^{{}^{\prime}}p_% {0:\rho}+s^{{}^{\prime}}q_{0:\rho})\geq 0( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT ) ≥ 0 此时有Mρ+α−1:ρ+α′=0subscriptsuperscript𝑀′:𝜌𝛼1𝜌𝛼0M^{{}^{\prime}}_{\rho+\alpha-1:\rho+\alpha}=0italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α - 1 : italic_ρ + italic_α end_POSTSUBSCRIPT = 0，即未产生借位。 当∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η¯≥0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂0\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha% +\eta}}\geq 0∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT ≥ 0时，Mρ+α:ρ+α+η′=(∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η¯)ρ+α:ρ+α+η=(∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η)=∑i=1w(−1)σ(i)misubscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂subscriptsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂:𝜌𝛼𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝛼𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑚𝑖M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}=(\sum_{i=1}^{w}(-1)^{\sigma(i)}% (u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta}})_{\rho+\alpha:\rho+% \alpha+\eta}=(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\rho+\alpha:\rho+% \alpha+\eta})=\sum_{i=1}^{w}(-1)^{\sigma(i)}m_{i}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT ) = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_m start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT。 当∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η¯<0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂0\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha% +\eta}}<0∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT < 0时，Mρ+α:ρ+α+η′=(2ρ+α+η+∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η¯)ρ+α:ρ+α+η=(2η+∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η)=2η+∑i=1w(−1)σ(i)misubscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂subscriptsuperscript2𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂:𝜌𝛼𝜌𝛼𝜂superscript2𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝛼𝜌𝛼𝜂superscript2𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑚𝑖M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}=(2^{\rho+\alpha+\eta}+\sum_{i=1% }^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta}})_% {\rho+\alpha:\rho+\alpha+\eta}=(2^{\eta}+\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+% v_{i})_{\rho+\alpha:\rho+\alpha+\eta})=2^{\eta}+\sum_{i=1}^{w}(-1)^{\sigma(i)}% m_{i}italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( 2 start_POSTSUPERSCRIPT italic_ρ + italic_α + italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT ) = 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_m start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT。 情况2. (∑i=1w(−1)σ(i)(ui+vi)0:ρ+α+t′p0:ρ+s′q0:ρ)<0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:0𝜌𝛼superscript𝑡′subscript𝑝:0𝜌superscript𝑠′subscript𝑞:0𝜌0(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{0:\rho+\alpha}+t^{{}^{\prime}}p_% {0:\rho}+s^{{}^{\prime}}q_{0:\rho})<0( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT 0 : italic_ρ + italic_α end_POSTSUBSCRIPT + italic_t start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_p start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT + italic_s start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT italic_q start_POSTSUBSCRIPT 0 : italic_ρ end_POSTSUBSCRIPT ) < 0 此时有Mρ+α−1:ρ+α′=1subscriptsuperscript𝑀′:𝜌𝛼1𝜌𝛼1M^{{}^{\prime}}_{\rho+\alpha-1:\rho+\alpha}=1italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α - 1 : italic_ρ + italic_α end_POSTSUBSCRIPT = 1，即低位向明文区产生借位。 当∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η¯−2ρ+α≥0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscript2𝜌𝛼0\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha% +\eta}}-2^{\rho+\alpha}\geq 0∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_ρ + italic_α end_POSTSUPERSCRIPT ≥ 0时，Mρ+α:ρ+α+η′=(∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η¯−2ρ+α)ρ+α:ρ+α+η=(∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η−1)=∑i=1w(−1)σ(i)mi−1subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂subscriptsuperscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscript2𝜌𝛼:𝜌𝛼𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝛼𝜌𝛼𝜂1superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑚𝑖1M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}=(\sum_{i=1}^{w}(-1)^{\sigma(i)}% (u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta}}-2^{\rho+\alpha})_{\rho% +\alpha:\rho+\alpha+\eta}=(\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\rho+% \alpha:\rho+\alpha+\eta}-1)=\sum_{i=1}^{w}(-1)^{\sigma(i)}m_{i}-1italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_ρ + italic_α end_POSTSUPERSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT - 1 ) = ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_m start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT - 1。 当∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η¯−2ρ+α<0superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscript2𝜌𝛼0\sum_{i=1}^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha% +\eta}}-2^{\rho+\alpha}<0∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_ρ + italic_α end_POSTSUPERSCRIPT < 0时，Mρ+α:ρ+α+η′=(2ρ+α+η+∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η¯−2ρ+α)ρ+α:ρ+α+η=(2η+∑i=1w(−1)σ(i)(ui+vi)ρ+α:ρ+α+η−1)=2η+∑i=1w(−1)σ(i)mi−1subscriptsuperscript𝑀′:𝜌𝛼𝜌𝛼𝜂subscriptsuperscript2𝜌𝛼𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖¯:𝜌𝛼𝜌𝛼𝜂superscript2𝜌𝛼:𝜌𝛼𝜌𝛼𝜂superscript2𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscriptsubscript𝑢𝑖subscript𝑣𝑖:𝜌𝛼𝜌𝛼𝜂1superscript2𝜂superscriptsubscript𝑖1𝑤superscript1𝜎𝑖subscript𝑚𝑖1M^{{}^{\prime}}_{\rho+\alpha:\rho+\alpha+\eta}=(2^{\rho+\alpha+\eta}+\sum_{i=1% }^{w}(-1)^{\sigma(i)}(u_{i}+v_{i})_{\overline{\rho+\alpha:\rho+\alpha+\eta}}-2% ^{\rho+\alpha})_{\rho+\alpha:\rho+\alpha+\eta}=(2^{\eta}+\sum_{i=1}^{w}(-1)^{% \sigma(i)}(u_{i}+v_{i})_{\rho+\alpha:\rho+\alpha+\eta}-1)=2^{\eta}+\sum_{i=1}^% {w}(-1)^{\sigma(i)}m_{i}-1italic_M start_POSTSUPERSCRIPT start_FLOATSUPERSCRIPT ′ end_FLOATSUPERSCRIPT end_POSTSUPERSCRIPT start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( 2 start_POSTSUPERSCRIPT italic_ρ + italic_α + italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT over¯ start_ARG italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_ARG end_POSTSUBSCRIPT - 2 start_POSTSUPERSCRIPT italic_ρ + italic_α end_POSTSUPERSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT = ( 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT ( italic_u start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT + italic_v start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) start_POSTSUBSCRIPT italic_ρ + italic_α : italic_ρ + italic_α + italic_η end_POSTSUBSCRIPT - 1 ) = 2 start_POSTSUPERSCRIPT italic_η end_POSTSUPERSCRIPT + ∑ start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_w end_POSTSUPERSCRIPT ( - 1 ) start_POSTSUPERSCRIPT italic_σ ( italic_i ) end_POSTSUPERSCRIPT italic_m start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT - 1。 综上所述，解密算法成立。 ∎ 8 局限性说明 1、解密方可知密文产生过程经历的加法次数的大概范围； 2、加法次数具有上限； 蚂蚁集团 潘无穷,顾洪良 wuqiong.pwq@antfin.com December 12, 2023 ；