LLL (jl)

module LLLmodule
using LinearAlgebra
function GS(B)
    C=deepcopy(B)
    for i in 1:size(C)[1]-1
        v=C[i,:]
        R= hcat(C[i+1:end,:]*v)/(v'*v)
        C[i+1:end,:]-= R*v'
    end
    C
end


function LLL(B,eps=3/4)
    C=deepcopy(B)
    n=size(C)[1]
    Bs=GS(C*1.)
    μ=function(i,j)
        C[i,:]'*Bs[j,:]/(Bs[j,:]'*Bs[j,:])
    end
    k=2
    while(k≤n)
        for j in k-1:-1:1
            C[k,:]-=round(μ(k,j))*C[j,:]
        end
        Bs=GS(C*1.)
        if Bs[k,:]'*Bs[k,:] ≥ (eps-μ(k,k-1)^2)*Bs[k-1,:]'*Bs[k-1,:]
            k+=1
        else
            C[k-1,:],C[k,:]=C[k,:],C[k-1,:]
            Bs=GS(C*1.)
            k=max(k-1,2)
        end
    end
    C
end

export LLL
end

using .LLLmodule


function gcdxLLL(X,γ=10^5)
    n=length(X)
    Λ=zeros(n,n+1)
    for i in 1:n
        Λ[i,i]=1
    end
    Λ[:,n+1]=X*γ
    Λ=LLL(Λ)
    Λ[:,n+1]/=γ
    Λ[n,:]
end

function gcdx_my(X)
    local a,b=X
    local U=[oneunit(a),zero(a),a]
    local V=[zero(b),oneunit(b),b]
    while V[3]!=zero(a)
        q=U[3]÷V[3]
        U,V=V,U-V*q
    end
    U
end