estimator.reduction.ReductionCost.short_vectors_simple

estimator.reduction.ReductionCost.short_vectors_simple#

ReductionCost.short_vectors_simple(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: β

This naive baseline implementation uses rerandomize+BKZ.

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

  • d – Lattice dimension.

  • N – Number of vectors requested.

  • B – Bit-size of entries.

  • preprocess – This option is ignore.

Returns:

(ρ, c, N, β')

EXAMPLES:

>>> from estimator.reduction import RC
>>> RC.CheNgu12.short_vectors_simple(100, 500, 1)
(1.0, 1.67646160799173e17, 1, 100)
>>> RC.CheNgu12.short_vectors_simple(100, 500)
(1.0, 1.67646160799173e20, 1000, 100)
>>> RC.CheNgu12.short_vectors_simple(100, 500, 1000)
(1.0, 1.67646160799173e20, 1000, 100)