estimator.reduction.ReductionCost.short_vectors#
- ReductionCost.short_vectors(beta, d, N=None, B=None, preprocess=True)[source]#
Cost of outputting many somewhat short vectors.
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, here: 2
This baseline implementation uses rerandomize+LLL as in [EC:Albrecht17].
- Parameters:
beta – Cost parameter (≈ SVP dimension).
d – Lattice dimension.
N – Number of vectors requested.
B – Bit-size of entries.
preprocess – Include the cost of preprocessing the basis with BKZ-β. If
False
we assume the basis is already BKZ-β reduced.
- Returns:
(ρ, c, N, β')
EXAMPLES:
>>> from estimator.reduction import RC >>> RC.CheNgu12.short_vectors(100, 500, N=1) (1.0, 1.67646...e17, 1, 2) >>> RC.CheNgu12.short_vectors(100, 500, N=1, preprocess=False) (1.0, 1, 1, 2) >>> RC.CheNgu12.short_vectors(100, 500) (2.0, 1.67646...e17, 1000, 2) >>> RC.CheNgu12.short_vectors(100, 500, preprocess=False) (2.0, 125000000000, 1000, 2) >>> RC.CheNgu12.short_vectors(100, 500, N=1000) (2.0, 1.67646...e17, 1000, 2) >>> RC.CheNgu12.short_vectors(100, 500, N=1000, preprocess=False) (2.0, 125000000000, 1000, 2)