1 /* Copyright (C) 2016 Martin Albrecht
2 Copyright (C) 2019 Koen de Boer & Wessel van Woerden
3
4 This file is part of fplll. fplll is free software: you
5 can redistribute it and/or modify it under the terms of the GNU Lesser
6 General Public License as published by the Free Software Foundation,
7 either version 2.1 of the License, or (at your option) any later version.
8
9 fplll is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General Public License
15 along with fplll. If not, see <http://www.gnu.org/licenses/>. */
16
17 #include "io/json.hpp"
18 #include <cstring>
19 #include <fplll.h>
20 #include <gso_gram.h>
21 #include <gso_interface.h>
22 #include <test_utils.h>
23
24 using json = nlohmann::json;
25
26 #ifndef TESTDATADIR
27 #define TESTDATADIR ".."
28 #endif
29
30 using namespace std;
31 using namespace fplll;
32
gram_is_equal(ZZ_mat<ZT> b,ZZ_mat<ZT> G)33 template <class ZT> bool gram_is_equal(ZZ_mat<ZT> b, ZZ_mat<ZT> G)
34 {
35 int r = b.r;
36 int c = b.c;
37 ZZ_mat<ZT> G_reduced;
38 G_reduced.resize(r, r);
39 for (int i = 0; i < r; i++)
40 {
41 for (int j = 0; j < r; j++)
42 {
43 (b)[i].dot_product(G_reduced(i, j), (b)[j], c);
44 }
45 }
46 // ------------------------------------------------
47 // ************************************************
48
49 // _______________________________________________
50 // -----------------------------------------------
51 // Test whether G_reduced = G
52 for (int i = 0; i < r; i++)
53 {
54 for (int j = 0; j < i; j++)
55 {
56 if (G(i, j) != G_reduced(i, j))
57 {
58 cerr << "The gram-representation and the basis-representation of the same lattice have an "
59 "unequal gram matrix.\n";
60 return 1;
61 }
62 }
63 }
64 return 0;
65 }
66
67 /**
68 @brief Test BKZ reduction.
69
70 @param A test matrix
71 @param block_size block size
72 @param float_type floating point type to test
73 @param flags flags to use
74 @param prec precision if mpfr is used
75
76 @return zero on success.
77 */
78
79 template <class ZT>
test_bkz(ZZ_mat<ZT> & A,const int block_size,FloatType float_type,int flags=BKZ_DEFAULT,int prec=0)80 int test_bkz(ZZ_mat<ZT> &A, const int block_size, FloatType float_type, int flags = BKZ_DEFAULT,
81 int prec = 0)
82 {
83 FloatType sel_ft = (float_type != FT_DEFAULT) ? float_type : FT_DOUBLE;
84
85 ZZ_mat<ZT> U;
86 ZZ_mat<ZT> UT;
87
88 /* lllwrapper (no FloatType needed, -m ignored) */
89 if (flags & BKZ_NO_LLL)
90 zeros_last(A, U, UT);
91 else
92 {
93 Wrapper wrapper(A, U, UT, LLL_DEF_DELTA, LLL_DEF_ETA, LLL_DEFAULT);
94 if (!wrapper.lll())
95 return wrapper.status;
96 }
97
98 // _______________________________________________
99 // -----------------------------------------------
100 // Create the Gram matrix G of the basis A
101
102 ZZ_mat<ZT> G;
103 int r = A.r;
104 int c = A.c;
105 G.resize(r, r);
106 for (int i = 0; i < r; i++)
107 {
108 for (int j = 0; j < r; j++)
109 {
110 A[i].dot_product(G(i, j), A[j], c);
111 }
112 }
113 // ------------------------------------------------
114 // ************************************************
115
116 // _______________________________________________
117 // -----------------------------------------------
118 // Create a MatGSO-object M (basis gso) for A
119 // and a MatGSOGram-object Mgram (gram gso) for G.
120
121 vector<Strategy> strategies;
122 BKZParam param(block_size, strategies);
123 param.flags = flags;
124
125 if (sel_ft == FT_DOUBLE)
126 {
127 MatGSO<Z_NR<ZT>, FP_NR<double>> M(A, U, UT, 0);
128 M.update_gso();
129 MatGSOGram<Z_NR<ZT>, FP_NR<double>> Mgram(G, U, UT, 1);
130 Mgram.update_gso();
131
132 LLLReduction<Z_NR<ZT>, FP_NR<double>> LLLObj(M, LLL_DEF_DELTA, LLL_DEF_ETA, 0);
133 BKZReduction<Z_NR<ZT>, FP_NR<double>> BKZObj(M, LLLObj, param);
134 BKZObj.bkz();
135
136 LLLReduction<Z_NR<ZT>, FP_NR<double>> LLLObjgram(Mgram, LLL_DEF_DELTA, LLL_DEF_ETA, 0);
137 BKZReduction<Z_NR<ZT>, FP_NR<double>> BKZObjgram(Mgram, LLLObjgram, param);
138 BKZObjgram.bkz();
139
140 return gram_is_equal(A, G);
141 }
142 else if (sel_ft == FT_MPFR)
143 {
144 int old_prec = FP_NR<mpfr_t>::set_prec(prec);
145
146 MatGSO<Z_NR<ZT>, FP_NR<mpfr_t>> M(A, U, UT, 1);
147 M.update_gso();
148 MatGSOGram<Z_NR<ZT>, FP_NR<mpfr_t>> Mgram(G, U, UT, 1);
149 Mgram.update_gso();
150
151 LLLReduction<Z_NR<ZT>, FP_NR<mpfr_t>> LLLObj(M, LLL_DEF_DELTA, LLL_DEF_ETA, 0);
152 BKZReduction<Z_NR<ZT>, FP_NR<mpfr_t>> BKZObj(M, LLLObj, param);
153 BKZObj.bkz();
154
155 LLLReduction<Z_NR<ZT>, FP_NR<mpfr_t>> LLLObjgram(Mgram, LLL_DEF_DELTA, LLL_DEF_ETA, 0);
156 BKZReduction<Z_NR<ZT>, FP_NR<mpfr_t>> BKZObjgram(Mgram, LLLObjgram, param);
157 BKZObjgram.bkz();
158
159 FP_NR<mpfr_t>::set_prec(old_prec);
160
161 return gram_is_equal(A, G);
162 }
163 else
164 {
165 cerr << "Type not supported for test" << endl;
166 return 0;
167 }
168
169 return 0;
170 }
171
172 /**
173 @brief Test BKZ for matrix stored in file pointed to by `input_filename`.
174
175 @param input_filename a path
176 @param block_size block size
177 @param float_type floating point type to test
178 @param flags flags to use
179 @param prec precision if mpfr is used
180
181 @return zero on success
182 */
183
184 template <class ZT>
test_filename(const char * input_filename,const int block_size,FloatType float_type=FT_DEFAULT,int flags=BKZ_DEFAULT,int prec=0)185 int test_filename(const char *input_filename, const int block_size,
186 FloatType float_type = FT_DEFAULT, int flags = BKZ_DEFAULT, int prec = 0)
187 {
188 printf("%s %d\n", input_filename, block_size);
189 ZZ_mat<ZT> A, B;
190 int status = 0;
191 status |= read_file(A, input_filename);
192 B = A;
193 status |= test_bkz<ZT>(A, block_size, float_type, flags, prec);
194 return status;
195 }
196
197 /**
198 @brief Construct d × (d+1) integer relations matrix with bit size b and test BKZ.
199
200 @param d dimension
201 @param b bit size
202 @param block_size block size
203 @param float_type floating point type to test
204 @param flags flags to use
205 @param prec precision if mpfr is used
206
207 @return zero on success
208 */
209
210 template <class ZT>
test_int_rel(int d,int b,const int block_size,FloatType float_type=FT_DEFAULT,int flags=BKZ_DEFAULT,int prec=0)211 int test_int_rel(int d, int b, const int block_size, FloatType float_type = FT_DEFAULT,
212 int flags = BKZ_DEFAULT, int prec = 0)
213 {
214 cerr << "test_int_rel " << d << " " << b << " " << block_size << endl;
215 ZZ_mat<ZT> A, B;
216 A.resize(d, d + 1);
217 A.gen_intrel(b);
218 B = A;
219 int status = 0;
220 status |= test_bkz<ZT>(A, block_size, float_type, flags | BKZ_VERBOSE, prec);
221 return status;
222 }
223
main(int,char **)224 int main(int /*argc*/, char ** /*argv*/)
225 {
226
227 int status = 0;
228
229 status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/dim55_in", 10, FT_DEFAULT,
230 BKZ_DEFAULT | BKZ_AUTO_ABORT);
231 #ifdef FPLLL_WITH_QD
232 status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/dim55_in", 10, FT_DD,
233 BKZ_SD_VARIANT | BKZ_AUTO_ABORT);
234 #endif
235 status |=
236 test_filename<mpz_t>(TESTDATADIR "/tests/lattices/dim55_in", 10, FT_DEFAULT, BKZ_SLD_RED);
237 status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/dim55_in", 20, FT_MPFR,
238 BKZ_DEFAULT | BKZ_AUTO_ABORT, 128);
239 status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/dim55_in", 20, FT_MPFR,
240 BKZ_SD_VARIANT | BKZ_AUTO_ABORT, 128);
241 status |=
242 test_filename<mpz_t>(TESTDATADIR "/tests/lattices/dim55_in", 20, FT_MPFR, BKZ_SLD_RED, 128);
243
244 status |= test_int_rel<mpz_t>(50, 1000, 10, FT_DOUBLE, BKZ_DEFAULT | BKZ_AUTO_ABORT);
245 status |= test_int_rel<mpz_t>(50, 1000, 10, FT_DOUBLE, BKZ_SD_VARIANT | BKZ_AUTO_ABORT);
246 status |= test_int_rel<mpz_t>(50, 1000, 10, FT_DOUBLE, BKZ_SLD_RED);
247 status |= test_int_rel<mpz_t>(50, 1000, 15, FT_MPFR, BKZ_DEFAULT | BKZ_AUTO_ABORT, 100);
248 status |= test_int_rel<mpz_t>(50, 1000, 15, FT_MPFR, BKZ_SD_VARIANT | BKZ_AUTO_ABORT, 100);
249 status |= test_int_rel<mpz_t>(50, 1000, 15, FT_MPFR, BKZ_SLD_RED, 100);
250
251 // status |= test_int_rel<mpz_t>(30, 2000, 10, FT_DPE, BKZ_DEFAULT | BKZ_AUTO_ABORT);
252 // status |= test_int_rel<mpz_t>(30, 2000, 10, FT_DPE, BKZ_SD_VARIANT | BKZ_AUTO_ABORT);
253 // status |= test_int_rel<mpz_t>(30, 2000, 10, FT_DPE, BKZ_SLD_RED);
254 status |= test_int_rel<mpz_t>(30, 2000, 10, FT_MPFR, BKZ_DEFAULT | BKZ_AUTO_ABORT, 53);
255 status |= test_int_rel<mpz_t>(30, 2000, 10, FT_MPFR, BKZ_SD_VARIANT | BKZ_AUTO_ABORT, 53);
256 status |= test_int_rel<mpz_t>(30, 2000, 10, FT_MPFR, BKZ_SLD_RED, 53);
257
258 status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10);
259 status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10, FT_DEFAULT,
260 BKZ_SD_VARIANT);
261 status |=
262 test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10, FT_DEFAULT, BKZ_SLD_RED);
263 status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10, FT_DOUBLE);
264 status |=
265 test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10, FT_DOUBLE, BKZ_SD_VARIANT);
266 status |=
267 test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10, FT_DOUBLE, BKZ_SLD_RED);
268 status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10, FT_MPFR,
269 BKZ_AUTO_ABORT, 212);
270 status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10, FT_MPFR,
271 BKZ_SD_VARIANT | BKZ_AUTO_ABORT, 212);
272 status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10, FT_MPFR,
273 BKZ_SLD_RED | BKZ_AUTO_ABORT, 212);
274 status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10, FT_DOUBLE);
275 status |=
276 test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10, FT_DOUBLE, BKZ_SD_VARIANT);
277 status |=
278 test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_in", 10, FT_DOUBLE, BKZ_SLD_RED);
279
280 if (status == 0)
281 {
282 cerr << "All tests passed." << endl;
283 return 0;
284 }
285 else
286 {
287 return -1;
288 }
289
290 return 0;
291 }
292