Gauss-SVP (jl)


using Primes
prec=1200
setprecision(prec)
q=rand(BigInt(10)^Int(prec/6):BigInt(10)^Int(prec/3))
f,g=0,0
while(gcd(f,g*q)!=1) 
    global f,g
    f=rand(1:BigInt(round(sqrt(q)/2)))
    g=rand(BigInt(round(sqrt(q)/4)):BigInt(round(sqrt(q)/2)))
end
finv=(q+gcdx(f,q)[2]) % q
h=(finv*g) % q


function gaussSVP(v1,v2)
    m=1
    while(m!=0)
        if (v2'*v2 < v1'*v1)
            v1,v2=v2,v1
        end
        m=BigInt(round((v1'*v2)/(v1'*v1)))
        v2-=m*v1
    end
    v1,v2
end

v1,v2=gaussSVP([1,h],[0,q])
[ abs(x) for x in v1]-[f,g]