Blocksize 44 slowdown

[lducas]

I've been working on benchmarking (to see if precomputed strategy could be replace by on the fly strategies). File attached : bench_bkz2.py.zip

I have a strange phenomenon on blocksize 44, where I get a big slowdown, compared to 43, despite BKZ-preproc actually starts in dim 45 ...

`

python -u bench_bkz2.py strat 1 PRUNER_MODE = strat BKZ_PREPROC = 1

...

BLOCKSIZE 43 PREPROC : () {"enumeration": {"cputime": 0.232920, "walltime": 0.234463, "#enum": 2^22.9, "%": 0.500637}} {"preprocessing": {"cputime": 0.211310, "walltime": 0.211512}} {"postprocessing": {"cputime": 0.003666, "walltime": 0.004380}} {"pruner": {"cputime": 0.006393, "walltime": 0.007249}} {"lll": {"cputime": 0.000299, "walltime": 0.000299}} [43, 0.49019908905029297, 1.012960778811286]

BLOCKSIZE 44 PREPROC : () {"enumeration": {"cputime": 0.761055, "walltime": 0.763979, "#enum": 2^24.6, "%": 0.500115}} {"preprocessing": {"cputime": 1.890530, "walltime": 1.891528}} {"postprocessing": {"cputime": 0.004427, "walltime": 0.005234}} {"pruner": {"cputime": 0.011522, "walltime": 0.013026}} {"lll": {"cputime": 0.000305, "walltime": 0.000305}} [44, 2.7123358249664307, 1.012960778811286]

BLOCKSIZE 45 PREPROC : (6,) PREPROC : () {"enumeration": {"cputime": 0.325685, "walltime": 0.327328, "#enum": 2^23.4, "%": 0.500778}} {"preprocessing": {"cputime": 2.416480, "walltime": 2.417534}} {"postprocessing": {"cputime": 0.003567, "walltime": 0.004238}} {"pruner": {"cputime": 0.006330, "walltime": 0.007186}} {"lll": {"cputime": 0.000288, "walltime": 0.000286}} [45, 2.787945032119751, 1.012528939031581] `

If I deactivate BKZ pre-processing, then the slowdown is still here at 44, and disapears at 45 ! ` python -u bench_bkz2.py strat 0 PRUNER_MODE = strat BKZ_PREPROC = 0

... BLOCKSIZE 43 {"enumeration": {"cputime": 0.226953, "walltime": 0.228437, "#enum": 2^22.9, "%": 0.500637}} {"preprocessing": {"cputime": 0.205070, "walltime": 0.205272}} {"postprocessing": {"cputime": 0.003445, "walltime": 0.004141}} {"pruner": {"cputime": 0.006065, "walltime": 0.006899}} {"lll": {"cputime": 0.000293, "walltime": 0.000291}} [43, 0.47627806663513184, 1.012960778811286]

BLOCKSIZE 44 {"enumeration": {"cputime": 0.842579, "walltime": 0.845439, "#enum": 2^24.8, "%": 0.500099}} {"preprocessing": {"cputime": 2.303715, "walltime": 2.304846}} {"postprocessing": {"cputime": 0.003860, "walltime": 0.004590}} {"pruner": {"cputime": 0.010909, "walltime": 0.012352}} {"lll": {"cputime": 0.000286, "walltime": 0.000285}} [44, 3.203824996948242, 1.012960778811286]

BLOCKSIZE 45 {"enumeration": {"cputime": 0.529743, "walltime": 0.531450, "#enum": 2^24.1, "%": 0.500776}} {"preprocessing": {"cputime": 0.288973, "walltime": 0.289212}} {"postprocessing": {"cputime": 0.003608, "walltime": 0.004305}} {"pruner": {"cputime": 0.006313, "walltime": 0.007214}} {"lll": {"cputime": 0.000286, "walltime": 0.000285}} [45, 0.8637588024139404, 1.0124981844121996] `

[lducas]

Ok, this is the fault of the current strategy I think: for that blocksize, there is one radius (1.096..., precisely the one of GH_bound) for which the success probability is very slightly below .5 (namely 0.49987...), triggering a costly retrial, for negligible success proba.

Action: include a 1% margin in the construction of strategy ? @malb do you agree ?

[malb]

I think we're doing 0.501 at the moment, in strategizer. We could up this to 0.51?

[lducas]

:+1:

[lducas]

Closing this and opening it in fplll/strategizer