source: trunk/linbox/linbox/algorithms/lattice.inl @ 4085

Revision 4085, 8.8 KB checked in by bboyer, 3 years ago (diff)

clang

Line 
1/* -*- mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
2// vim:sts=8:sw=8:ts=8:noet:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s
3/* linbox/algorithms/lattice.inl
4 * Copyright (C) 2011 The LinBox group
5 * Written by Brice Boyer <bboyer@imag.fr>
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the
19 * Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
20 * Boston, MA 02110-1301, USA.
21 */
22#ifndef __LINBOX_algorithms_lattice_INL
23#define __LINBOX_algorithms_lattice_INL
24
25
26/*!@internal
27 * @file algorithms/lattice.inl
28 * @brief  LLL reduction
29 * @ingroup algorithms
30 * @ingroup lattice
31 *
32 * Implements the various wrappers
33 */
34
35/*  Interface to NTL LLL */
36namespace LinBox
37{
38#ifdef __LINBOX_HAVE_NTL
39
40        //! @todo we should use mat_ZZ here instead of BlasMatrix<Ring>
41        template<class Ring, bool withU>
42        void
43        lllReduceInBase(BlasMatrix<Ring>                      & H,
44                        BlasMatrix<Ring>                      & UU,
45                        const latticeMethod::latticeNTL_LLL   & meth)
46        {
47                // convert to mat_ZZ
48                NTL::mat_ZZ B ;
49                NTL::mat_ZZ U ;
50                B.SetDims(H.rowdim(),H.coldim());
51                NTL::clear(B);
52                // XXX Maybe Bij, maybe Bji...
53                NTL_ZZ Ints ;
54                NTL_ZZ::Element Bij ;
55                for (size_t i = 0 ; i < H.rowdim(); ++i) {
56                        for (size_t j = 0  ; j < H.coldim() ; ++j) {
57                                Ints.init(Bij,H.getEntry(i,j));
58                                B[(long)i][(long)j] = Bij ;
59                        }
60                }
61                if (withU) {
62                        U.SetDims(UU.rowdim(),UU.coldim());
63                        NTL::clear(U);
64                }
65                // do NTL's LLL
66                if (withU) {
67                        switch (meth.getMeth()) {
68                        case (latticeMethod::latticeNTL_LLL::FP) :
69                                {
70                                        if (meth.givens()) {
71                                                G_LLL_FP(B,U,meth.getDelta(),meth.getDepth());
72                                        }
73                                        else {
74                                                LLL_FP(B,U,meth.getDelta(),meth.getDepth());
75                                        }
76                                }
77                                break;
78                        case (latticeMethod::latticeNTL_LLL::RR) :
79                                {
80                                        if (meth.givens()) {
81                                                G_LLL_RR(B,U,meth.getDelta(),meth.getDepth());
82                                        }
83                                        else {
84                                                LLL_RR(B,U,meth.getDelta(),meth.getDepth());
85                                        }
86                                }
87                                break;
88                        case (latticeMethod::latticeNTL_LLL::XD) :
89                                {
90                                        if (meth.givens()) {
91                                                G_LLL_XD(B,U,meth.getDelta(),meth.getDepth());
92                                        }
93                                        else {
94                                                LLL_XD(B,U,meth.getDelta(),meth.getDepth());
95                                        }
96                                }
97                                break;
98                        case (latticeMethod::latticeNTL_LLL::QP) :
99                                {
100                                        if (meth.givens()) {
101                                                G_LLL_QP(B,U,meth.getDelta(),meth.getDepth());
102                                        }
103                                        else {
104                                                LLL_QP(B,U,meth.getDelta(),meth.getDepth());
105                                        }
106                                }
107                                break;
108
109                        }
110                }
111                else {
112                        switch (meth.getMeth()) {
113                        case (latticeMethod::latticeNTL_LLL::FP) :
114                                {
115                                        if (meth.givens()) {
116                                                G_LLL_FP(B,meth.getDelta(),meth.getDepth());
117                                        }
118                                        else {
119                                                LLL_FP(B,meth.getDelta(),meth.getDepth());
120                                        }
121                                }
122                                break;
123                        case (latticeMethod::latticeNTL_LLL::RR) :
124                                {
125                                        if (meth.givens()) {
126                                                G_LLL_RR(B,meth.getDelta(),meth.getDepth());
127                                        }
128                                        else {
129                                                LLL_RR(B,meth.getDelta(),meth.getDepth());
130                                        }
131                                }
132                                break;
133                        case (latticeMethod::latticeNTL_LLL::XD) :
134                                {
135                                        if (meth.givens()) {
136                                                G_LLL_XD(B,meth.getDelta(),meth.getDepth());
137                                        }
138                                        else {
139                                                LLL_XD(B,meth.getDelta(),meth.getDepth());
140                                        }
141                                }
142                                break;
143                        case (latticeMethod::latticeNTL_LLL::QP) :
144                                {
145                                        if (meth.givens()) {
146                                                G_LLL_QP(B,meth.getDelta(),meth.getDepth());
147                                        }
148                                        else {
149                                                LLL_QP(B,meth.getDelta(),meth.getDepth());
150                                        }
151                                }
152                                break;
153
154                        }
155                }
156                // convert from mat_ZZ
157                Integer Hij;
158                for (size_t i = 0 ; i < H.rowdim(); ++i) {
159                        for (size_t j = 0  ; j < H.coldim() ; ++j) {
160                                Ints.convert(Hij,B[(long)i][(long)j]);
161                                H.setEntry( i,j,Hij );
162                        }
163                }
164                if (withU) {
165                        Integer Uij;
166                        for (size_t i = 0 ; i < H.rowdim(); ++i) {
167                                for (size_t j = 0  ; j < H.coldim() ; ++j) {
168                                        Ints.convert(Uij,U[(long)i][(long)j]);
169                                        UU.setEntry(i,j,Uij );
170                                }
171                        }
172                }
173
174        }
175#endif // __LINBOX_HAVE_NTL
176}
177
178/*  Interface to NTL BKZ */
179namespace LinBox
180{
181#ifdef __LINBOX_HAVE_NTL
182
183        //! @todo we should use mat_ZZ here instead of BlasMatrix<Ring>
184        template<class Ring, bool withU>
185        void
186        lllReduceInBase(BlasMatrix<Ring>                      & H,
187                        BlasMatrix<Ring>                      & UU,
188                        const latticeMethod::latticeNTL_BKZ   & meth)
189        {
190                // convert to mat_ZZ
191                NTL::mat_ZZ B ;
192                NTL::mat_ZZ U ;
193                B.SetDims(H.rowdim(),H.coldim());
194                NTL::clear(B);
195                // XXX Maybe Bij, maybe Bji...
196                NTL_ZZ Ints ;
197                NTL_ZZ::Element Bij ;
198                for (size_t i = 0 ; i < H.rowdim(); ++i) {
199                        for (size_t j = 0  ; j < H.coldim() ; ++j) {
200                                Ints.init(Bij, H.getEntry(i,j));
201                                B[(long)i][(long)j] = Bij ;
202                        }
203                }
204                if (withU) {
205                        U.SetDims(UU.rowdim(),UU.coldim());
206                        NTL::clear(U);
207                }
208                // do NTL's BKZ
209                if (withU) {
210                        switch (meth.getMeth()) {
211                        case (latticeMethod::latticeNTL_BKZ::FP) :
212                                {
213                                        if (meth.givens()) {
214                                                G_BKZ_FP(B,U,meth.getBlockSize(),meth.getPrune());
215                                        }
216                                        else {
217                                                BKZ_FP(B,U,meth.getBlockSize(),meth.getPrune());
218                                        }
219                                }
220                                break;
221                        case (latticeMethod::latticeNTL_BKZ::RR) :
222                                {
223                                        if (meth.givens()) {
224                                                G_BKZ_RR(B,U,meth.getBlockSize(),meth.getPrune());
225                                        }
226                                        else {
227                                                BKZ_RR(B,U,meth.getBlockSize(),meth.getPrune());
228                                        }
229                                }
230                                break;
231                        case (latticeMethod::latticeNTL_BKZ::XD) :
232                                {
233                                        if (meth.givens()) {
234                                                G_BKZ_XD(B,U,meth.getBlockSize(),meth.getPrune());
235                                        }
236                                        else {
237                                                BKZ_XD(B,U,meth.getBlockSize(),meth.getPrune());
238                                        }
239                                }
240                                break;
241                        case (latticeMethod::latticeNTL_BKZ::QP) :
242                                {
243                                        if (meth.givens()) {
244                                                G_BKZ_QP(B,U,meth.getBlockSize(),meth.getPrune());
245                                        }
246                                        else {
247                                                BKZ_QP(B,U,meth.getBlockSize(),meth.getPrune());
248                                        }
249                                }
250                                break;
251
252                        }
253                }
254                else {
255                        switch (meth.getMeth()) {
256                        case (latticeMethod::latticeNTL_BKZ::FP) :
257                                {
258                                        if (meth.givens()) {
259                                                G_BKZ_FP(B,meth.getBlockSize(),meth.getPrune());
260                                        }
261                                        else {
262                                                BKZ_FP(B,meth.getBlockSize(),meth.getPrune());
263                                        }
264                                }
265                                break;
266                        case (latticeMethod::latticeNTL_BKZ::RR) :
267                                {
268                                        if (meth.givens()) {
269                                                G_BKZ_RR(B,meth.getBlockSize(),meth.getPrune());
270                                        }
271                                        else {
272                                                BKZ_RR(B,meth.getBlockSize(),meth.getPrune());
273                                        }
274                                }
275                                break;
276                        case (latticeMethod::latticeNTL_BKZ::XD) :
277                                {
278                                        if (meth.givens()) {
279                                                G_BKZ_XD(B,meth.getBlockSize(),meth.getPrune());
280                                        }
281                                        else {
282                                                BKZ_XD(B,meth.getBlockSize(),meth.getPrune());
283                                        }
284                                }
285                                break;
286                        case (latticeMethod::latticeNTL_BKZ::QP) :
287                                {
288                                        if (meth.givens()) {
289                                                G_BKZ_QP(B,meth.getBlockSize(),meth.getPrune());
290                                        }
291                                        else {
292                                                BKZ_QP(B,meth.getBlockSize(),meth.getPrune());
293                                        }
294                                }
295                                break;
296
297                        }
298                }
299                // convert from mat_ZZ
300                Integer Hij;
301                for (size_t i = 0 ; i < H.rowdim(); ++i) {
302                        for (size_t j = 0  ; j < H.coldim() ; ++j) {
303                                Ints.convert(Hij,B[(long)i][(long)j]);
304                                H.setEntry( i,j,Hij );
305                        }
306                }
307                if (withU) {
308                        Integer Uij;
309                        for (size_t i = 0 ; i < H.rowdim(); ++i) {
310                                for (size_t j = 0  ; j < H.coldim() ; ++j) {
311                                        Ints.convert(Uij,U[(long)i][(long)j]);
312                                        UU.setEntry(i,j,Uij );
313                                }
314                        }
315                }
316
317        }
318#endif // __LINBOX_HAVE_NTL
319
320}
321
322/* Interface to FPLLL */
323namespace LinBox
324{
325#ifdef __LINBOX_HAVE_FPLLL
326        //! @bug we suppose Ring and mpz_t understand eachother...
327        template<class Ring, bool withU>
328        void
329        lllReduceInBase(BlasMatrix<Ring>                   & H,
330                        BlasMatrix<Ring>                   & UU,
331                        const latticeMethod::latticeFPLLL  & meth)
332        {
333                typedef mpz_t ZT ;
334                if (withU)
335                        throw NotImplementedYet("not U");
336                // Convert H
337                ZZ_mat<ZT> B(H.rowdim(),H.coldim()) ;
338                for (size_t i = 0 ; i < H.rowdim() ; ++i) {
339                        for (size_t j = 0 ; j < H.coldim() ; ++j) {
340                                B.Set(i,j,Z_NR<ZT>(H.getEntry(i,j)) );
341                        }
342                }
343                // LLL()
344                switch (meth.getMeth()) {
345                case (latticeMethod::latticeFPLLL::P) :
346                        {
347                                ::proved<ZT,double> lllMethod(&B,meth.getPrecision(),
348                                                              meth.getEta(),meth.getDelta());
349                                lllMethod.LLL();
350                        }
351                        break;
352                case (latticeMethod::latticeFPLLL::W) :
353                        {
354                                ::wrapper lllMethod(&B,meth.getPrecision(),
355                                                    meth.getEta(),meth.getDelta());
356                                lllMethod.LLL();
357                        }
358                        break;
359                case (latticeMethod::latticeFPLLL::H) :
360                        {
361                                ::heuristic<ZT,double> lllMethod(&B,meth.getPrecision(),
362                                                                 meth.getEta(),meth.getDelta(),
363                                                                 meth.getSiegel());
364                                lllMethod.LLL();
365                        }
366                        break;
367                }
368
369
370
371                // Convert back H
372                for (size_t i = 0 ; i < H.rowdim() ; ++i) {
373                        for (size_t j = 0 ; j < H.coldim() ; ++j) {
374                                H.setEntry(i,j, B.Get(i,j) );
375                        }
376                }
377
378        }
379#endif // __LINBOX_HAVE_FPLLL
380
381
382}
383
384#endif // __LINBOX_algorithms_lattice_INL
Note: See TracBrowser for help on using the repository browser.