DOCSEARCHbyAlgolia
Submit Docs

flatter

repository·main·Indexed 42 days ago

https://github.com/keeganryan/flatter

A high-performance library for fast lattice reduction of integer lattice bases. It implements an iterated compression algorithm that achieves quality comparable to LLL but is significantly faster for high-dimensional lattices and large entries. It includes a CLI for reduction on FPLLL format bases and a C++ API featuring classes such as ColumnwiseDouble, LazyRefine, and RecursiveGeneric for custom reduction strategies.

Tokens
2.7K
Snippets
9
Records
15
Agent score
54%

What's inside flatter

  1. Visualize the lattice reduction profile

    main

    You can visualize how the Gram-Schmidt norms (the profile) evolve during the reduction process. This is done by logging the profile to a file using the FLATTER_LOG environment variable and then using the provided Python visualization script.

    # 1. Run flatter with logging enabled
$ latticegen q 100 50 100 b | FLATTER_LOG=./log flatter -q

# 2. Visualize the log file
$ python scripts/visualize_profile.py ./log

  2. Install flatter from source

    main

    To install flatter, you must first install the required system dependencies via apt, then build the project using cmake and make. Ensure you have libgmp-dev, libmpfr-dev, fplll-tools, libfplll-dev, libeigen3-dev, and libopenblas-dev installed on your system.

    sudo apt install libgmp-dev libmpfr-dev fplll-tools \
	libfplll-dev libeigen3-dev libopenblas-dev
mkdir build && cd ./build
cmake ..
make
sudo make install
sudo ldconfig

  3. Configure reduction quality in flatter

    main

    You can specify the target reduction quality using one of the following flags. If none are provided, it defaults to a Root Hermite Factor (RHF) of 1.0219.

    • -alpha ALPHA: Reduce to a given parameter alpha.
    • -rhf RHF: Reduce analogous to a given root hermite factor RHF.
    • -delta DELTA: Reduce analogous to LLL with a particular delta (approximate).

    Additionally, you can use -logcond LOGCOND to set a bound on the condition number.

    # Example: Reduce using a specific alpha
$ flatter -alpha 0.0625081 input.lat

# Example: Reduce using a specific RHF
$ flatter -rhf 1.0219 input.lat

  4. Configure flatter output and verbosity

    main

    Use these flags to control the CLI output:

    • -h: Display the help message.
    • -v: Enable verbose output (useful for seeing input/output metadata and reduction statistics).
    • -q: Do not output the resulting lattice (useful when piping to another tool).
    • -p: Output profiles (the base-2 logarithm of the Gram-Schmidt norms).
    # Example: Verbose output with profiles, suppressing lattice output
$ flatter -q -v -p input.lat

  5. Use the flatter CLI for lattice reduction

    main

    The flatter command-line tool performs (f)ast (lat)tice (r)eduction on integer lattice bases provided in the FPLLL format. It reads from INFILE (defaults to STDIN) and writes to OUTFILE (defaults to STDOUT).

    $ latticegen q 4 2 10 b | flatter

  6. Implement a custom lattice reduction strategy using RecursiveGeneric

    main

    To implement a custom recursive lattice reduction algorithm, inherit from flatter::LatticeReductionImpl::RecursiveGeneric. This class provides a framework for recursive reduction strategies that manage sublattices, precision, and basis representations.

    When implementing a subclass, you should override the following lifecycle and operational methods:

    Lifecycle Methods

    • init_solver() / fini_solver(): Initialize and clean up the solver state.
    • init_iter() / fini_iter(): Initialize and clean up iteration-specific state.
    • do_checks(): Perform validity checks on the current state.

    Reduction Logic

    • is_reduced(): Return true if the lattice is currently reduced according to your criteria.
    • setup_sublattice_reductions() / cleanup_sublattice_reductions(): Manage the setup and teardown of recursive calls on sublattices.
    • reduce_sublattices(): Execute the recursive reduction steps.
    • update_representation(): Update the internal basis representation after reduction.
    • collect_U(): Collect the transformation matrices.
    • final_sr(): Perform final steps of the reduction process.

    Precision and Compression

    • set_precision(unsigned int prec): Set the working precision.
    • get_precision_from_spread(double spread): Calculate required precision based on a given spread.
    • get_shifts_for_compression(int* shifts): Determine shifts used for basis compression.
    • compress_R(): Perform basis compression on the floating-point representation R.

  7. Configure and solve iterated fused QR size reduction

    main

    The flatter::FusedQRSizeRedImpl::Iterated class provides an implementation for iterated fused QR size reduction. To use it, instantiate the class with FusedQRSizeReductionParams and a ComputationContext, then call configure() to set parameters and solve() to execute the reduction process.

    Key methods:

    • Iterated(const FusedQRSizeReductionParams& params, const ComputationContext& cc): Constructor initializing the implementation with reduction parameters and the computation context.
    • configure(const FusedQRSizeReductionParams& params, const ComputationContext& cc): Configures the solver with the provided parameters and context.
    • solve(): Executes the iterated reduction algorithm.
    • impl_name(): Returns the implementation name as a std::string.
    #include "problems/fused_qr_sizered/iterated.h"

// Assuming FusedQRSizeReductionParams and ComputationContext are defined elsewhere
flatter::FusedQRSizeRedImpl::Iterated solver(params, cc);
solver.configure(params, cc);
solver.solve();

  8. Use the LazyRefine class for fused QR/size reduction

    main

    The LazyRefine class implements a fused QR/size reduction procedure based on the L2 algorithm's lazy size reduction. It is designed for scenarios where you have a lattice containing two sublattices that are already size-reduced; it allows vectors in the second sublattice to be size-reduced by vectors in the first sublattice in parallel.

    To use LazyRefine, you must provide FusedQRSizeReductionParams and a ComputationContext during construction. The procedure is executed by calling solve() after the object has been configured.

    // Example usage pattern
flatter::FusedQRSizeRedImpl::LazyRefine refiner(
    params, // FusedQRSizeReductionParams
    cc      // ComputationContext
);

refiner.configure(params, cc);
refiner.solve();

  10. Use ColumnwiseDouble for fused QR size reduction

    main

    The ColumnwiseDouble class is used to perform columnwise double reduction within the fused_qr_sizered problem context. It follows a lifecycle of configuration followed by solving.

    To use it, you must instantiate it with FusedQRSizeReductionParams and a ComputationContext, call configure() to set up the specific reduction parameters, and then call solve() to execute the reduction process.

    // Conceptual usage pattern
flatter::FusedQRSizeRedImpl::ColumnwiseDouble solver(
    params, // FusedQRSizeReductionParams
    cc      // ComputationContext
);

solver.configure(params, cc);
solver.solve();

  11. Use the Irregular Lattice reduction implementation

    main

    The Irregular class is a specialized implementation of LatticeReduction used when the input basis is rectangular or not in upper triangular form. It follows the standard lifecycle of a lattice reduction implementation: initialization, configuration, and solving.

    To use it, you must provide LatticeReductionParams and a ComputationContext during construction or via the configure method. Once configured, call solve() to perform the reduction.

    // Conceptual usage based on the class interface
flatter::LatticeReductionImpl::Irregular solver(params, context);
solver.configure(params, context);
solver.solve();