estimator.reduction.CheNgu12

class estimator.reduction.CheNgu12

__call__(beta, d, B=None)

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 ]
>>> nodes += [ 99.0, 105.0, 111.0, 120.0, 127.0, 134.0]  # couldn't use \ breaks stuff
>>> 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-β.