Lattices 0.0.1 → 0.0.2

raw patch · 7 files changed

+80/−40 lines, 7 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Lattices.cabal +4/−1
• src/Math/Lattices/CloseVector.hs +45/−0
• src/Math/Lattices/Internal.hs +16/−0
• src/Math/Lattices/LLL.hs +2/−39
• src/Math/Lattices/LLLFP.hs +11/−0
• src/Math/LinearAlgebra/GramSchmidt.hs +1/−0
• tests/Math/Lattices/LLL/Tests.hs +1/−0

@@ -1,5 +1,5 @@ Name:                Lattices-Version:             0.0.1+Version:             0.0.2 Category:            Math Synopsis:            A library for lattices Description:         A library for lattices, in particular for computing an LLL reduced basis for a lattice and finding a close lattice vector@@ -14,6 +14,7 @@ Extra-Source-Files:   README   TODO+  src/Math/Lattices/Internal.hs   tests/TestSuite.hs   tests/Math/LinearAlgebra/GramSchmidt/Tests.hs   tests/Math/Lattices/LLL/Tests.hs@@ -31,7 +32,9 @@    Exposed-modules:     Math.LinearAlgebra.GramSchmidt+    Math.Lattices.CloseVector     Math.Lattices.LLL+    Math.Lattices.LLLFP    Hs-Source-Dirs: src 

@@ -0,0 +1,45 @@+-- | Approximation algorithm for the Closest Vector Problem. The default implementation+--   uses Babai's Nearest Plane Method. References:+--+--   * On Lovász' Lattice Reduction And The Nearest Lattice Point Problem, László Babai. Combinatorica 6 (1), 1-13 (1986).+--+--   * Mathematics of Public Key Cryptography, Steven Galbraith. Chapter 18 of draft 1.0+--+module Math.Lattices.CloseVector (+    closeVector+) where++import           Prelude                        hiding ((*>))+import           Data.Array+import           Data.Ratio+import           Math.Algebra.LinearAlgebra     hiding ((!))+import           Math.Lattices.Internal+import           Math.Lattices.LLL+import           Math.LinearAlgebra.GramSchmidt+++-- Babai's Algorithm for CVP++-- | Find a lattice vector in 'basis close to 'x'. 'basis' is assumed to be LLL-reduced+closeVector :: [[Rational]] -> [Ratio Integer] -> [Rational]+closeVector basis x = foldl1 (<+>) $ babaiNP (reverse $ [0..d]) basis' b' x+    where+        d      = length basis - 1+        b'     = listArray (0, d) $ gramSchmidtBasis basis+        basis' = listArray (0, d) basis++projectTo v b = (v <.> b) / (norm2 b)++vsum zero = foldl (<+>) zero++-- | Find a close vector to 'x using Babai's Nearest Plane Method. 'b is an LLL-reduced basis, 'b'' is its Gram-Schmidt basis d is the size of the (sub)space.+babaiNP []     _ _  _ = []+babaiNP (i:is) b b' w = y_i : recurse+    where+        l_i     = projectTo w $ b' ! i+        delta   = toRational $ rnd $ l_i+        y_i     = delta *> b ! i++        w_i1    = w <-> (l_i - delta) *> (b' ! i) <-> y_i++        recurse = babaiNP is b b' w_i1

@@ -0,0 +1,16 @@+-- | Some internal convenience functions for use in Math.Lattices+--+module Math.Lattices.Internal (+        norm2,+        rnd+) where++import           Data.Ratio+import           Math.Algebra.LinearAlgebra     hiding ((!))+++-- | Just an easy way to write $||v||^2$+norm2 v = v <.> v++-- | Closest 'Integral to the given n, rounding up. $\lfloor n\rceil$+rnd x = floor $ x + 1%2

@@ -7,22 +7,17 @@ -- --   * Modern Computer Algebra, second edition, Joachim von zur Gathen and Jürgen Gerhard. Chapter 16. -----   References for Babai's Nearest Plane Method for the Closest Vector Problem:------   * On Lovász' Lattice Reduction And The Nearest Lattice Point Problem, László Babai. Combinatorica 6 (1), 1-13 (1986).------   * Mathematics of Public Key Cryptography, Steven Galbraith. Chapter 18 of draft 1.0--- module Math.Lattices.LLL (     lll,     lllDelta,-    closeVector,     Basis(..) ) where +import           Prelude                        hiding ((*>)) import           Data.Array import           Data.Ratio import           Math.Algebra.LinearAlgebra     hiding ((!))+import           Math.Lattices.Internal import           Math.LinearAlgebra.GramSchmidt  -- | A matrix representing a basis@@ -31,12 +26,6 @@  -- The $B_i$ set is called 'bb in this file, because of course we cannot call it 'B in Haskell. --- | Just an easy way to write $||v||^2$-norm2 v = v <.> v---- | Closest 'Integral to the given n, rounding up. $\lfloor n\rceil$-rnd x = floor $ x + 1%2- -- |Return an LLL reduced basis. This calls 'lllDelta with a default parameter $\delta = 3/4$ lll :: [[Rational]] -> Basis lll basis = lllDelta basis $ 3%4@@ -128,29 +117,3 @@ -- Two small test cases (will put into unit tests): -- lll $ [ [12, 2], [13, 4] ] -- lll $ [ [1, 0, 0], [4, 2, 15], [0, 0, 3] ]---- Babai's Algorithm for CVP---- | Find a lattice vector in 'basis close to 'x'. 'basis' is assumed to be LLL-reduced-closeVector :: [[Rational]] -> [Ratio Integer] -> [Rational]-closeVector basis x = foldl1 (<+>) $ babaiNP (reverse $ [0..d]) basis' b' x-    where-        d      = length basis - 1-        b'     = listArray (0, d) $ gramSchmidtBasis basis-        basis' = listArray (0, d) basis--projectTo v b = (v <.> b) / (norm2 b)--vsum zero = foldl (<+>) zero---- | Find a close vector to 'x using Babai's Nearest Plane Method. 'b is an LLL-reduced basis, 'b'' is its Gram-Schmidt basis d is the size of the (sub)space.-babaiNP []     _ _  _ = []-babaiNP (i:is) b b' w = y_i : recurse-    where-        l_i     = projectTo w $ b' ! i-        delta   = toRational $ rnd $ l_i-        y_i     = delta *> b ! i--        w_i1    = w <-> (l_i - delta) *> (b' ! i) <-> y_i--        recurse = babaiNP is b b' w_i1

@@ -0,0 +1,11 @@+-- | Implements a LLL lattice reduction algorithm with floating point arithmetic. References for this algorithm:+--+--   * Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems, C. P. Schorr and M. Euchner (1993)+--+module Math.Lattices.LLLFP (+    lllFP,+    lllFPDelta+) where++lllFP = undefined+lllFPDelta = undefined

@@ -4,6 +4,7 @@     gramSchmidtOrthogonalization ) where +import           Prelude                    hiding ((*>)) import           Math.Algebra.LinearAlgebra  -- | Given a basis, return the Gram-Schmidt orhthogonal basis

@@ -9,6 +9,7 @@ import           Data.Ratio import           Data.Array import           Math.Lattices.LLL+import           Math.Lattices.CloseVector  equalsArray computed ok = H.assert $ elems computed == ok