并行的NTRU格规约算法

在高维NTRU格中,BKZ算法为了获取较好的规约效果不得不采用大分块,但同时也使运行时间急剧增加。设计了一种msBKZ规约算法,对一组初始基左乘随机幺模矩阵变换出多组基,分别采用小块BKZ(k<18)线程规约,筛选出规约效果最好的那组进行"短代替"后作为初始基,重复该过程以此逐步逼近格中的最短向量。实验表明msBKZ比大块BKZ(k=23)的规约效率至少提高一倍。