通過(guò)選擇 proper k
set y1=y2=...yn-k=0 with high prob
計(jì)數(shù)在xn-k+1, ..., xn上進(jìn)行
對(duì)于最短向量坐標(biāo)的后k個(gè)整數(shù)值
以及其對(duì)應(yīng)的正交整數(shù)表示
我們可以唯一確定出最短向量的前n-k格坐標(biāo), 在y1=y2=...yn-k=0的條件下
instead 搜索xi可能在的區(qū)間
我們將搜索范圍decrease by nodes
對(duì)xi的搜索在以下兩種類型的節(jié)點(diǎn)中進(jìn)行
- 零點(diǎn): 使得||xi*bi*||最小的節(jié)點(diǎn)(在算xi相關(guān)的之前, xi+1,...,xn都已經(jīng)定下了, 這里是為了確定xi)
- 平衡點(diǎn): 使得||xi*bi*||最接近平均值的節(jié)點(diǎn)
||xi*bi*||和平均值的距離有上界為0.5
set tolerance bound為0.4
如果一個(gè)平衡點(diǎn)不能讓||xi*bi*||足夠靠近平均值
我們extend這個(gè)平衡點(diǎn)為使得||xi*bi*||離平均值第二近的節(jié)點(diǎn)
零點(diǎn)有1個(gè)
平衡點(diǎn)有 4個(gè)
xi*的值得xn,xn-1,...,xi都確定好才能定出來(lái)
bi*有bi,bi-1,...,b1以及正交系數(shù)就能算好
平均值是關(guān)于最短向量長(zhǎng)度上界, bi*,維數(shù)n的值
大概看一下這個(gè)過(guò)程:
yn=xn=round(xn*)
yn-1=xn-1+round(u(n,n-1)xn)=round(xn-1*) //利用了上一步選的xn值和已知的u(n,n-1), 再確定xn-1就好
yn-2=xn-2+round(u(n-1,n-2)xn-1+u(n,n-2)xn)//利用了之前選的xn,xn-1的值和已知的正交系數(shù), 再確定xn-2就好
...
y2=x2+round(u(3,2)x3+...u(n,2)xn)//利用了之前定的xn,...,x3, 再確定x2就好
y1=x1+round(u(2,1)x2+...+u(n,1)xn)//利用之前定的xn,...,x2, 再確定x1就好
Input: BKZ-reduced basis B; upper bound for the shortest vector^2:R, k
設(shè)v在正交規(guī)范基下的坐標(biāo)為(w1,....,wn),
則各wi的值應(yīng)該是差不多大的
Output:short vector v, ||v||^2<=R
設(shè)最短向量在
1.GSO
2.sv[n]=0, slen=0
3.un[n][n]=0
ylen[n]=0
uvec[n]=0
4.d=(d1,...,dn) average value
5.poss_v[n][5]=0 5個(gè)列向量
poss_v_cnt[n]=0
poss_v_next[n]=0
6.for xn=ceil(dn), floor(dn), 0 //前兩個(gè)是使||x*nb*n||離平均值dn最近的xn, 這時(shí)候xn=xn*,
uvec[n]=xn
un[n][i]=xn*u(n,i) ,i=1,2,...,n-1
ylen[n]=xn2||bn*||2
- for t=n-1,...,1 do //t是當(dāng)前指標(biāo)
if poss_v_cnt[t]=0 //CPV函數(shù)還沒(méi)有調(diào)用
poss_v_cnt[t],poss_v_cnt[t]=CPV(t, k, dt,un[t+1][t])
//傳入當(dāng)前指標(biāo)t, k, 第k個(gè)平均值, 整系數(shù)*正交系數(shù)
poss_v_next[t]=1
else
poss_v_next[t]++
