chrisvwx / lllplus.jl Goto Github PK

@JuliaRegistrator register()

A PkgEval run for a Julia pull request which changes the generated numbers for rand(a:b) indicates that the tests of this package might fail in Julia 1.5 (and on Julia current master branch).

Also, you might be interested in using the new StableRNGs.jl registered package, which provides guaranteed stable streams of random numbers across Julia releases.

Apologies if this is a false positive. Cf. https://github.com/JuliaCI/NanosoldierReports/blob/ab6676206b210325500b4f4619fa711f2d7429d2/pkgeval/by_hash/52c2272_vs_47c55db/logs/LLLplus/1.5.0-DEV-87d2a04de3.log

After writing a quick LLL implementation (gist here) using Givens rotations to get better aquainted with lattice problems while learning lattice-based cryptography, I started to benchmark the available LLL implementations.

The LLL function in this package is fairly well optimized but it does seem to make a bunch of allocations that can probably be done away with, and there may be a ~2x speedup available from getting rid of them. Tracking them down may be somewhat nontrivial but it should be a low-hanging fruit for further optimization.

I am not sure if this is a bug or I am not understanding how to call hard_sphere() ...
If I run
x = hard_sphere([1 2]', [1 2; 3 4],2)
I get
x = [0; 1]
this solution gives the lattice point
[1 2; 3 4] * [0; 1] = [2; 4]
however there are 4 lattice points ([1 1], [0 2], [1 1], [1 1], [1 3], [2 2]) that are closer to [1 2] than [2 4].
Also, if I set the Nc input parameter to values >2 I get lattice points that move farther away from the closest point, so I am not sure what is going on...

cvp([-2, 0.0], Matrix([1 1.0; 4 0]'))

It got stuck in this expression. It only has dimension 2.

Implement block Korkine-Zolotarev lattice reduction as in Schnorr87.

I have preliminary code for this; if you want a BKZ solver let me know and I'll share the code.

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

@JuliaRegistrator register()

PackageEvaluator.jl is a script that runs nightly. It attempts to load all Julia packages and run their tests (if available) on both the stable version of Julia (0.3) and the nightly build of the unstable version (0.4). The results of this script are used to generate a package listing enhanced with testing results.

On Julia 0.4

• On 2015-06-22 the testing status was Tests pass.
• On 2015-06-23 the testing status changed to Tests fail.

This issue was filed because your testing status became worse. No additional issues will be filed if your package remains in this state, and no issue will be filed if it improves. If you'd like to opt-out of these status-change messages, reply to this message saying you'd like to and @IainNZ will add an exception. If you'd like to discuss PackageEvaluator.jl please file an issue at the repository. For example, your package may be untestable on the test machine due to a dependency - an exception can be added.

Test log:

>>> 'Pkg.add("LLLplus")' log
INFO: Cloning cache of LLLplus from git://github.com/christianpeel/LLLplus.jl.git
INFO: Installing LLLplus v0.1.1
INFO: Package database updated

>>> 'Pkg.test("LLLplus")' log
INFO: Testing LLLplus
tests with small matrices...
...done

In all the following tests, the first time includes the JIT compilation; 
for the second execution the compilation is already done and the time
should be faster.

Testing LLL on 1000x1000 real matrix...
ERROR: LoadError: syntax: local declaration in global scope
 in include at ./boot.jl:254
 in include_from_node1 at loading.jl:133
 in process_options at ./client.jl:304
 in _start at ./client.jl:404
while loading /home/vagrant/.julia/v0.4/LLLplus/test/runtests.jl, in expression starting on line 46

===============================[ ERROR: LLLplus ]===============================

failed process: Process(`/home/vagrant/julia/bin/julia --check-bounds=yes --code-coverage=none --color=no /home/vagrant/.julia/v0.4/LLLplus/test/runtests.jl`, ProcessExited(1)) [1]

================================================================================
INFO: No packages to install, update or remove
ERROR: LLLplus had test errors
 in error at ./error.jl:21
 in test at pkg/entry.jl:746
 in anonymous at pkg/dir.jl:31
 in cd at file.jl:22
 in cd at pkg/dir.jl:31
 in test at pkg.jl:71
 in process_options at ./client.jl:280
 in _start at ./client.jl:404


>>> End of log

It seems to me that Eq. 8 from [1] is not necessarily satisfied when the input matrix for LLL has complex values. Indeed, said paper seems to embed complex matrices into real arithmetic and run LLL on the embedded matrix.

I started playing around with my own LLL implementation [2], based on [3], which I hope to make distributed and level 3 BLAS friendly, and I am finding that, when I check the satisfaction of Eq. (8) for complex matrices, that it does not hold, as each of the real and imaginary entries of the strictly upper triangle of inv(diag(diag(R)))*R seem to be able to have both real and imaginary entries approaching one half in magnitude. My (completely untested) hypothesis would be that this is fundamental to LLL on complex data and that Eq. (8) should, in this case, be modified to use sqrt(2)/2 instead of 1/2.

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.132.5464&rep=rep1&type=pdf
[2] elemental/Elemental@623564a
[3] http://perso.ens-lyon.fr/damien.stehle/downloads/HLLL.pdf

The tag name "v1.1" is not of the appropriate SemVer form (vX.Y.Z).
cc: @christianpeel

I am getting an error with Julia 0.6.4 under Windows:

julia> using LLLplus
WARNING: Method definition roundf(Any) in module LLLplus at C:\Users\arbenede\.julia\v0.6\LLLplus\src\lll.jl:33 overwritten at C:\Users\arbenede\.julia\v0.6\LLLplus\src\lll.jl:36.

julia> H = randn(3,3)
3×3 Array{Float64,2}:
 0.168901   0.0226148  -0.888702
 1.26764   -0.514712    0.263596
 1.07987   -1.33472     0.508937

julia> lll(H)
ERROR: UndefVarError: roundf not defined
Stacktrace:
 [1] lll(::Array{Float64,2}, ::Float64) at C:\Users\arbenede\.julia\v0.6\LLLplus\src\lll.jl:45
 [2] lll(::Array{Float64,2}) at C:\Users\arbenede\.julia\v0.6\LLLplus\src\lll.jl:24

I looked at the source code and it seems ok to me... any ideas?

I think the unexpected extra time was the result of an inefficient round(x) function.
I have improved things in DoubleFloats#master, would you mind rerunning your benchmarks and let me know if the difference is meaningful?

Hi Christian,

Great package!
I've been looking into the literature on simultaneous diophantine approximation and found something curious about the Hanrot implementation you've used for rationalapprox.

It appears that you need to ensure a lower bound on M of 2^(n(n+1)/4 in order that q = abs(B[1,1]) is in fact always non-zero. Otherwise, it can be zero and will of course 'blow up' the result. I came across this is practical examples and found the theoretical reason, I believe.

I can explain more if interested, but basically if you compare to the equivalent proof in Schrijver, he proves that (in the notation of the passage) that ||B(:,1)|| < C implies q ! = 0 (Schrijver uses 0 < \epsilon < 1 and we have our M equals his 2^(n(n+1)/4 \epsilon^(-n).

@JuliaRegistrator register()