estimator.reduction.CheNgu12#

class estimator.reduction.CheNgu12[source]#
__call__(beta, d, B=None)[source]#

Runtime estimation given β and assuming [CheNgu12] estimates are correct.

Parameters
  • beta – Block size ≥ 2.

  • d – Lattice dimension.

  • B – Bit-size of entries.

The constants in this function were derived as follows based on Table 4 in [CheNgu12]:

>>> from sage.all import var, find_fit
>>> dim = [100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250]
>>> nodes = [39.0, 44.0, 49.0, 54.0, 60.0, 66.0, 72.0, 78.0, 84.0, 96.0, 99.0, 105.0, 111.0, 120.0, 127.0, 134.0]  # noqa
>>> times = [c + log(200,2).n() for c in nodes]
>>> T = list(zip(dim, nodes))
>>> var("a,b,c,beta")
(a, b, c, beta)
>>> f = a*beta*log(beta, 2.0) + b*beta + c
>>> f = f.function(beta)
>>> f.subs(find_fit(T, f, solution_dict=True))
beta |--> 0.2701...*beta*log(beta) - 1.0192...*beta + 16.10...

The estimation 2^(0.18728 β⋅log_2(β) - 1.019⋅β + 16.10) is of the number of enumeration nodes, hence we need to multiply by the number of cycles to process one node. This cost per node is typically estimated as 64.

EXAMPLE:

>>> from math import log
>>> from estimator.reduction import RC
>>> log(RC.CheNgu12(500, 1024), 2.0)
365.70...

Methods

LLL(d[, B])

Runtime estimation for LLL algorithm based on [AC:CheNgu11].

__init__()

beta()

Estimate required block size β for a given root-hermite factor δ based on [PhD:Chen13].

delta(beta)

Compute root-Hermite factor δ from block size β.

short_vectors(beta, d[, N, B, preprocess])

Cost of outputting many somewhat short vectors.

short_vectors_simple(beta, d[, N, B, preprocess])

Cost of outputting many somewhat short vectors.

svp_repeat(beta, d)

Return number of SVP calls in BKZ-β.