To install the package, enter the following in the Julia REPL:
Pkg.clone("git://github.com/pikachau/LatticeBasisReduction.jl.git")
LLL(x::Array, α::Number[; return_c = false, verbose=Bool])
Return an α-reduced basis of the lattice generated by `x`, where 1/4 < α <= 1.
Handles matrices of size (m, n), where m <= n.
If return_c is set to true, return the matrix C for which Y = C * X,
where Y is the α-reduced basis.
If verbose is set to true, also print the reduce/exchange operations.
# Example
julia> x = [[-2 7 7 -5]
[3 -2 6 -1]
[2 -8 -9 -7]
[8 -9 6 -4]]
4×4 Array{Int64,2}:
-2 7 7 -5
3 -2 6 -1
2 -8 -9 -7
8 -9 6 -4
julia> LLL(x, 1, verbose=true)
iteration 1 exchange k=2
iteration 2 reduce k=2 ℓ=1 [μ[k,l]] = 1.0
iteration 3 reduce k=3 ℓ=2 [μ[k,l]] = -1.0
iteration 4 reduce k=3 ℓ=1 [μ[k,l]] = -1.0
iteration 5 exchange k=4
iteration 6 reduce k=3 ℓ=2 [μ[k,l]] = -1.0
iteration 7 exchange k=3
iteration 8 reduce k=2 ℓ=1 [μ[k,l]] = 1.0
iteration 9 reduce k=3 ℓ=2 [μ[k,l]] = 1.0
iteration 10 reduce k=3 ℓ=1 [μ[k,l]] = -1.0
iteration 11 reduce k=4 ℓ=3 [μ[k,l]] = -1.0
iteration 12 exchange k=4
iteration 13 reduce k=3 ℓ=2 [μ[k,l]] = 1.0
iteration 14 exchange k=3
iteration 15 exchange k=2
iteration 16 exchange k=3
iteration 17 reduce k=2 ℓ=1 [μ[k,l]] = 1.0
iteration 18 exchange k=2
iteration 19 exchange k=4
iteration 20 reduce k=3 ℓ=2 [μ[k,l]] = 1.0
iteration 21 exchange k=3
iteration 22 reduce k=2 ℓ=1 [μ[k,l]] = -1.0
iteration 23 exchange k=2
4×4 Array{Float64,2}:
2.0 3.0 1.0 1.0
2.0 0.0 -2.0 -4.0
-2.0 2.0 3.0 -3.0
3.0 -2.0 6.0 -1.0
Given a list of n distinct real numbers, the LLL algorithm allows one to find rational approximations using the same denominator.
sda(x...; β = 2, ε = 1/100)
Input: list of real distinct numbers.
Output: list of numerators and the common denominator.
# Example
julia> sda(sqrt(2), sqrt(3), sqrt(5), sqrt(7))
([22253,27132,35112,41514],15708)