Martin R. Albrecht

To me this "feels" rather estimator-y, no? Why do you think it might live in FPyLLL?

To me this fits quite naturally here, I'd just "open up" `gaussian_heuristic` and do the appropriate caching "by hand", but I'm not married to that

FWIW, this is quick: ``` sage: from estimator import * sage: params = LWE.Parameters(n=2^14, q=2^438, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19)) sage: LWE.estimate.rough(params) ``` so it might be worth comparing the results...

Also, can you post some smaller scale examples that behave similarly but not quite so slowly? Easier to play with those. Say, n=1024, 2048 …

re work-factor: note that the blocksizes are all essentially the same and those fundamentally account for the work factor. The work factor difference is purely down to what cost model...

So this is an okay-ish approximation: ``` params = LWE.Parameters(n=2^11, q=2^54, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)) costs = LWE.estimate.rough(params) beta = min(cost["beta"] for cost in costs.values()) RC.BDGL16(beta, d=2*params.n).log(2.) ```

`bdd` will only offer a "small" improvement over `usvp` but it's harder to bound `bdd_hybrid`, so no promises.

Running ``` python from estimator import * params = LWE.Parameters(n=2^10, q=2^27, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)) %prun _ = LWE.estimate(params, red_cost_model=RC.BDGL16, deny_list=["bkw", "arora-gb"], red_shape_model="gsa") ``` reveals some good target for performance...

With the current `main` branch, I'm now getting: ``` python from estimator import * all_params = [LWE.Parameters(n=2^13, q=2^228, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)), LWE.Parameters(n=2^12, q=2^109, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)), LWE.Parameters(n=2^11, q=2^54,...

For the two examples on top: ``` python from estimator import * params = LWE.Parameters(n=2^14, q=2^438, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19)) %time _ = LWE.estimate(params, red_cost_model=RC.BDGL16, deny_list=["bkw", "bdd_hybrid", "bdd_mitm_hybrid", "dual_hybrid", "dual_mitm_hybrid",...