# 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]
>>> 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]. 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-β.