Skip to content

Performance gap on particular lattices #145

@DotanGazith

Description

@DotanGazith

In my research in astronomy, I use g6k to sample many short vectors in particular lattices I define.
The way I do so is by doing BKZ->pump-up of the lattice, and in most instances, I generate from my data, the performance is great and roughly matches the measurements from the 2019 G6K paper.
However, for some specific lattices this process breaks at some late stage of the pump-up, to the point that a sieve instruction in dimension ~80 requires ~1h.

I attach an example lattice that recreates this odd behaviour, specifically, here I used:

  • BKZ with dimension 45
  • The bgj1 sieving algorithm
  • Context going from (0, 43, 88) -> (0, 8, 88) in the (EL, S)*(43-8), with the run-time significantly increasing around (0, 14, 88)

Is there some common wisdom on the way to "amortize" the runtime of such an operation?

slow_lattice.txt

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions