1 /*--------------------------------------------------------------------
2
3 Normalized LLL-Spectral Test for Linear Congruential Generators!
4
5 Authors: Karl Entacher, Karl.Entacher@fh-sbg.ac.at January 2000
6
7 Thomas Schell, Dept. of Scientific Computing, Univ. Salzburg
8
9 --------------------------------------------------------------------*/
10
11
12
13
14
15 /*-------------Libraries (needs Victor Shoups NTL-Lib----------------*/
16
17 #include <iostream>
18
19 #include <fstream>
20
21 #include <time.h>
22
23 #include <sys/resource.h>
24
25 #include <cmath>
26
27 #include <float.h>
28
29 #include <NTL/RR.h>
30
31 #include <NTL/LLL.h>
32
33
34
35 /*------------------------ Definitions ------------------------------*/
36
37 using namespace NTL;
38 using namespace std;
39
40 ZZ mult, modul;
41
42 const int dim_max = 24;
43
44 RR fact_RR[dim_max];
45
46 double fact[dim_max];
47
48 int x_xmax;
49
50
51
52 /*-----------------------------------------------------------------------
53
54 Call the function with:
55
56 lll_spect ["output-file"] [mult] [modul]
57
58 Example:
59
60 lll_spect "output-file" 8 16907 2147483647
61
62 ----------------------------------------------------------------------*/
63
64
65
66
67
main(int argc,char * argv[])68 int main(int argc, char *argv[]) {
69
70
71
72 /*-------------------------- Input-Check -----------------------*/
73
74 if (!(argc >= 4)) {
75
76 cout << "lll_spect <output-file-name> <dim> <mult> <modul>" << endl;
77
78 exit(0);
79
80 }
81
82 /*-------- Reads the input parameters: "file" dim mult modul -------------*/
83
84 ofstream output_file(argv[1], ios::out);
85
86 x_xmax = atoi(argv[2]);
87
88 mult = to_ZZ(argv[3]);
89
90 modul = to_ZZ(argv[4]);
91
92
93
94 /*-------------Output of mult modul ----------------------------------------*/
95
96 output_file << "==============================================================" <<endl;
97
98 output_file << "Modul:\t\t\t" << modul <<endl;
99
100 output_file << "Multiplikator:\t\t" << mult <<endl;
101
102 output_file << "Dimension bis:\t\t" << x_xmax<<endl;
103
104 output_file << "==============================================================" <<endl;
105
106 output_file << "[k]\t" << "[dim]\t" << "[n_spect]\t" << endl << endl;
107
108
109
110 /*------------- Constants for the normalized Spectral Test ----------------*/
111
112 fact_RR[0] = to_RR(0.0); // intentionally left uninitialized -> not used
113
114 fact_RR[1] = to_RR(0.2886751345948128822545744);
115
116 fact_RR[2] = to_RR(0.1767766952966368811002111);
117
118 fact_RR[3] = to_RR(0.125);
119
120 fact_RR[4] = to_RR(0.0883883476483184405501055);
121
122 fact_RR[5] = to_RR(0.0721687836487032205636436);
123
124 fact_RR[6] = to_RR(0.0625);
125
126 fact_RR[7] = to_RR(0.0625);
127
128 fact_RR[8] = to_RR(0.06007);
129
130 fact_RR[9] = to_RR(0.05953);
131
132 fact_RR[10] = to_RR(0.06136);
133
134 fact_RR[11] = to_RR(0.06559);
135
136 fact_RR[12] = to_RR(0.07253);
137
138 fact_RR[13] = to_RR(0.08278);
139
140 fact_RR[14] = to_RR(0.09735);
141
142 fact_RR[15] = to_RR(0.11774);
143
144 fact_RR[16] = to_RR(0.14624);
145
146 fact_RR[17] = to_RR(0.18629);
147
148 fact_RR[18] = to_RR(0.24308);
149
150 fact_RR[19] = to_RR(0.32454);
151
152 fact_RR[20] = to_RR(0.44289);
153
154 fact_RR[21] = to_RR(0.61722);
155
156 fact_RR[22] = to_RR(0.87767);
157
158 fact_RR[23] = to_RR(1.27241);
159
160
161
162 for (int i = 1; i < dim_max; i++) {
163
164 fact[i] = to_double(1 / (to_RR(2) * pow(fact_RR[i] * to_RR(modul), to_RR(1.0) / to_RR(i+1))));
165
166 }
167
168
169
170 /*---------------------------------for time measurements------------------*/
171
172 struct rusage cur_ru;
173
174
175
176
177
178 /*------------Definition of the Matrix (Basis) Input, LLL und Output ------*/
179
180 mat_ZZ x;
181
182 x.SetDims(x_xmax, x_xmax);
183
184 double norm;
185
186 for (int j = 2; j <= x_xmax; j++) {
187
188 x.SetDims(j,j);
189
190 x[0][0] = modul; // first Index: Rows, second Index: columns
191
192 for (int i = 1; i < j; i++) // fill in ones
193
194 x[i][i] = 1;
195
196 for (int i = 1; i < j; i++)
197
198 x[i][0] =-(power(mult, i));
199
200 ZZ det, rg;
201
202 rg = LLL(det, x, 0);
203
204 double min_x_x = to_double(x[0] * x[0]);
205
206 for (int i = 1; i < j; i++) {
207
208 double x_x = to_double(x[i] * x[i]);
209
210 if (min_x_x > x_x)
211
212 min_x_x = x_x;
213
214 }
215
216 norm = fact[j-1] * sqrt(min_x_x); //Normalization
217
218 output_file << j << "\t" << norm << endl;
219
220 }
221
222 /*-------------------------Output of Timings-----------------------------*/
223
224 getrusage(RUSAGE_SELF, &cur_ru);
225
226 cout << "total time elapsed\t" << cur_ru.ru_utime.tv_sec << endl;
227
228 output_file << endl << "Time [s]:\t" << cur_ru.ru_utime.tv_sec << endl;
229
230 output_file.close();
231
232 }
233
234
235
236