Generator crashes for Coded BKW

[johannesmono]

Here the example for the crash, let me know if you need more information:

sage: params = LWE.Parameters(1024, 2**120, ND.Uniform(-1, 1), ND.DiscreteGaussian(3.19))
sage: LWE.coded_bkw(params)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[3], line 1
----> 1 LWE.coded_bkw(params)

File .../estimator/lwe_bkw.py:298, in CodedBKW.__call__(self, params, ntest, log_level)
    296 params = LWEParameters.normalize(params)
    297 try:
--> 298     cost = self.b(params, ntest=ntest, log_level=log_level)
    299 except InsufficientSamplesError as e:
    300     m = e.args[1]

File .../estimator/lwe_bkw.py:235, in CodedBKW.b(cls, params, ntest, log_level)
    233                 y = cls.cost(b=b, t2=t2, ntest=ntest, params=params)
    234                 it_t2.update(y)
--> 235             it_b.update(it_t2.y)
    236     best = it_b.y
    238 # the search cannot fail. It just outputs some X with X["oracle"]>m.

File .../estimator/util.py:122, in local_minimum_base.update(self, res)
    119     self._best = self._last_x, res
    121 # We found something better
--> 122 if res is not False and self._smallerf(res, self._best[1]):
    123     # store it
    124     self._best = self._last_x, res
    126     # if it's a result of a long jump figure out the next direction

File .../estimator/lwe_bkw.py:223, in CodedBKW.b.<locals>.sf(x, best)
    222 def sf(x, best):
--> 223     return (x["rop"] <= best["rop"]) and (best["m"] > params.m or x["m"] <= params.m)

TypeError: 'NoneType' object is not subscriptable```

[malb]

Something is quite off with our heuristics:

sage: from estimator import *
sage: for k in (20, 30, 40, 50, 60, 70, 80, 90):
....:     print(k, repr(LWE.coded_bkw(LWE.Parameters(1024, 2**k, ND.Uniform(-1, 1), ND.DiscreteGaussian(3.19)))))
....: 
20 rop: ≈2^238.1, m: ≈2^224.1, mem: ≈2^225.1, b: 11, t1: 3, t2: 32, ℓ: 10, #cod: 895, #top: 0, #test: 97, tag: coded-bkw
30 rop: ≈2^228.4, m: ≈2^214.3, mem: ≈2^215.3, b: 7, t1: 0, t2: 39, ℓ: 6, #cod: 941, #top: 0, #test: 90, tag: coded-bkw
40 rop: ≈2^219.3, m: ≈2^204.7, mem: ≈2^205.7, b: 5, t1: 0, t2: 53, ℓ: 4, #cod: 953, #top: 0, #test: 71, tag: coded-bkw
50 rop: ≈2^219.0, m: ≈2^204.6, mem: ≈2^205.6, b: 4, t1: 0, t2: 48, ℓ: 3, #cod: 952, #top: 0, #test: 74, tag: coded-bkw
60 rop: ≈2^200.9, m: ≈2^185.5, mem: ≈2^186.5, b: 3, t1: 8, t2: 84, ℓ: 2, #cod: 953, #top: 0, #test: 47, tag: coded-bkw
70 rop: ≈2^231.3, m: ≈2^215.7, mem: ≈2^216.7, b: 3, t1: 12, t2: 95, ℓ: 2, #cod: 957, #top: 0, #test: 31, tag: coded-bkw
80 rop: ≈2^188.6, m: ≈2^172.0, mem: ≈2^166.9, b: 2, t1: 19, t2: 102, ℓ: 1, #cod: 949, #top: 0, #test: 38, tag: coded-bkw
90 rop: ≈2^292.3, m: ≈2^276.3, mem: ≈2^277.3, b: 3, t1: 45, t2: 111, ℓ: 2, #cod: 875, #top: 0, #test: 15, tag: coded-bkw

[malb]

I pushed something for this particular crash. Still, I wouldn't trust the output:

sage: from estimator import *
sage: for k in (20, 30, 40, 50, 60, 70, 80, 90):
....:     print(k, repr(LWE.coded_bkw(LWE.Parameters(400, 2**k, ND.Uniform(-1, 1), ND.DiscreteGaussian(3.19)))))
....: 
20 rop: ≈2^116.4, m: ≈2^104.0, mem: ≈2^105.0, b: 5, t1: 3, t2: 28, ℓ: 4, #cod: 353, #top: 0, #test: 33, tag: coded-bkw
30 rop: ≈2^106.7, m: ≈2^94.1, mem: ≈2^95.1, b: 3, t1: 0, t2: 34, ℓ: 2, #cod: 373, #top: 0, #test: 30, tag: coded-bkw
40 rop: ≈2^98.1, m: ≈2^84.8, mem: ≈2^85.7, b: 2, t1: 3, t2: 49, ℓ: 1, #cod: 375, #top: 0, #test: 20, tag: coded-bkw
50 rop: ≈2^162.9, m: ≈2^152.0, mem: ≈2^153.0, b: 3, t1: 0, t2: 8, ℓ: 2, #cod: 339, #top: 0, #test: 62, tag: coded-bkw
60 rop: ≈2^198.5, m: ≈2^185.1, mem: ≈2^186.1, b: 3, t1: 9, t2: 60, ℓ: 2, #cod: 366, #top: 0, #test: 8, tag: coded-bkw
70 rop: ≈2^153.4, m: ≈2^142.3, mem: ≈2^143.3, b: 2, t1: 0, t2: 10, ℓ: 1, #cod: 357, #top: 0, #test: 43, tag: coded-bkw
80 rop: ≈2^175.9, m: ≈2^163.7, mem: ≈2^164.7, b: 2, t1: 0, t2: 26, ℓ: 1, #cod: 386, #top: 0, #test: 16, tag: coded-bkw
90 rop: ≈2^286.6, m: ≈2^274.1, mem: ≈2^275.1, b: 3, t1: 0, t2: 34, ℓ: 2, #cod: 389, #top: 0, #test: 12, tag: coded-bkw