# estimator.reduction.GJ21.short_vectors#

GJ21.short_vectors(beta, d, N=None, preprocess=True, B=None, C=5.46, sieve_dim=None)[source]#

Cost of outputting many somewhat short vectors according to [AC:GuoJoh21].

The output of this function is a tuple of four values:

• ρ is a scaling factor. The output vectors are expected to be longer than the shortest vector expected from an SVP oracle by this factor.

• c is the cost of outputting N vectors

• N the number of vectors output, which may be larger than the value put in for N.

• β’ the cost parameter associated with sampling

This runs a sieve on the first β_0 vectors of the basis after BKZ-β reduction to produce many short vectors, where β_0 is chosen such that BKZ-β reduction and the sieve run in approximately the same time. [AC:GuoJoh21]

Parameters
• beta – Cost parameter (≈ SVP dimension).

• d – Lattice dimension.

• N – Number of vectors requested.

• preprocess – Include the cost of preprocessing the basis with BKZ-β. If `False` we assume the basis is already BKZ-β reduced.

• B – Bit-size of entries.

• C – Progressive overhead lim_{β → ∞} ∑_{i ≤ β} 2^{0.292 i + o(i)}/2^{0.292 β + o(β)}.

• sieve_dim – Explicit sieving dimension.

EXAMPLES:

```>>> from estimator.reduction import RC
>>> RC.GJ21.short_vectors(100, 500, 1)
(1.0, 2.7367476128136...19, 1, 100)
>>> RC.GJ21.short_vectors(100, 500)
(1.04228014727497, 5.56224438...19, 36150192, 121)
>>> RC.GJ21.short_vectors(100, 500, 1000)
(1.04228014727497, 5.56224438...19, 36150192, 121)
```