Lenstra–Lenstra–Lovász Reduction Implementation in C++

Contains:

• l3.cpp (L3 Reduction for Integral Basis)
• l3_r.cpp (L3 Reduction for Rational/Decimal Basis)
• rational.cpp (Rational numbers implementation)
• l3_properties_satisfied.jpg (Properties Satisfied after L3 Reduction)

Instructions to run either of the file:

Compile:

g++ -std=c++14 fileName.cpp -o fileName

Run:

fileName

User Inputs:

Modifiy the following variables in int main() to provide input as per need.

std::vector<std::vector<int>> basis;
basis = {{201, 37}, {1648, 297}}; //set Column wise //basis[i] should give the i-th column

double delta = 0.99;

Paper Refered:

• Factoring polynomials with rational coefficients
• Lattice Basis Reduction Improved Practical Algorithm and Solving Subset Sum Problem

Purpose:

Part of Independent Project titled "An Experimental Study of BKZ Algorithm"" at IIIT Delhi in Monsoon 2022 Semester under the guidance of Dr. Subhabrata Samajder

Author:

• Abhimanyu Gupta

Useful Links:

• Lattice?
• Why short Orthogonal Vectors?
• Gram-Schmidt Process
• Short Example

Note:

• The l3_r.cpp is not running properly.
• The root cause for this is identified to be the imprecisions in convering double values to Rational values.
• The current algorithm (based on idea of Continued Fractions) fails to represent a subset of double values using small integer numerator and denominator.
• During computations, these numerator and denominator values grows rapidly leading to integer overflow, eventually causing code termination.