作为PSF算法的推广,盆景树算法事实上是一个分级陷门函数,在盆景树模型下以某个格（一组基）作为根节点可以生成一个更大维数的格作为下一级的枝节点,同时得到格的一组基[45].这种由“根”到“枝”的“生长”可以是无陷门的,即无指导生长（Undirected Growth）,此时“盆景师”在分级过程中没有使用陷门因此没有任何特权;也可以是有陷门时由“盆景师”控制盆景树的“生长”过程,而“生长”模式又不尽相同,包括控制生长(Controlled Growth)、扩展控制(Extending Control)和随机控制(Randoming Control).而控制生长算法即本书前文所示的陷门抽样算法.

扩展控制算法在不增加范数的前提下将格Λ⊥q(A)的一组基S“扩展”为更大维数的格Λ⊥q(A′)的基S′.从而利用扩展控制算法可以将一个格的陷门基“控制生长”为另一个更大维数格的陷门基.但是该算法不能保证S 与S′是相互独立的.为此,我们需要随机控制算法来随机化扩展控制算法的输出基以保证这种“扩展”的安全性.联合扩展控制和随机控制算法,可以以一种安全的方式由一个格Λ 的陷门基产生另一个与Λ 相关的更大维数格的陷门基.所谓安全是指获得大维数格的陷门基与格Λ 的陷门基是相互独立的.本书在后续使用扩展控制算法时,总是输入陷门基.

本节以引理的方式描述扩展控制算法和随机控制算法.

引理2.8 设S ∈Zm×m 是(A)的任意一组基,其中A 的列能够生成,矩阵 是任意的.s 为高斯参数满足引理2.6.存在一个确定的多项式时间算法ExtBasis(S,A′ =(A||),s)输出格Λ⊥q(A′)的基S′,满足

事实上该算法可以很容易的实现.首先计算一个矩阵T ,使得AT = ~A 成立.令进而,如果S 是Λ⊥q(A)的陷门基,则我们可以借助PSF计算矩阵T.

算法.RandBasis(S,s)

输入: S,s ≥

对i=0 to m,执行:(www.daowen.com)

1.v ←SampleD(S,s),

2.假如v与向量组v1,v2,··· ,vi-1线性无关,令vi =v,i=i+1.

3.若不然,重复执行步骤1.

4.V=(v1,v2,··· ,vm)

输出:S′ =Tobasis(V,HNF(S))