#integer #lattice #basis #described #precision #sieve #sieving

svp

任意精度整数上的格筛法

2个不稳定版本

0.2.0 2022年10月13日
0.1.0 2022年10月12日

#768 in 科学

MITLGPL-3.0+

35KB
758 代码行

SVP

任意精度整数上的格筛法。

包括由 [GPV08]描述的采样算法和 [MV10]中描述的高斯筛法。

示例

use svp::*;

// LLL/BKZ reduced basis
let mut b = vec![
    nvec![
        Integer::new(),
        Integer::new(),
        Integer::new(),
        Integer::from(-1),
        Integer::from(-1)
    ],
    nvec![
        Integer::from(-1),
        Integer::from(-2),
        Integer::from(-2),
        Integer::from(-1),
        Integer::from(1)
    ],
    nvec![
        Integer::from(3),
        Integer::new(),
        Integer::from(-1),
        Integer::from(-1),
        Integer::from(1)
    ],
    nvec![
        Integer::from(-1),
        Integer::from(3),
        Integer::from(-2),
        Integer::from(2),
        Integer::from(-2)
    ],
    nvec![
        Integer::from(2),
        Integer::from(-3),
        Integer::from(1),
        Integer::from(2),
        Integer::from(-2)
    ],
];

// Compute squared norms
for i in 0..b.len() {
    b[i].norm = Some(&b[i] * &b[i]);
}

// Init lattice
let l = Lattice { basis: b.clone() };

// Rejection sampling parameter
let t = Float::with_val(53, b.len()).ln();

// Init Gasuss Sieve
let mut gs = gsieve![l, t];

// Short vectors sorted in ascending order
let short_vecs = gs.sieve();

依赖项

~3MB
~52K SLoC