1 | |
---|
2 | #include <NTL/LLL.h> |
---|
3 | |
---|
4 | NTL_CLIENT |
---|
5 | |
---|
6 | long SubsetSumSolution(const vec_ZZ& z) |
---|
7 | { |
---|
8 | long n = z.length()-3; |
---|
9 | long j; |
---|
10 | |
---|
11 | if (z(n+1) != 0) return 0; |
---|
12 | if (z(n+2) != -1 && z(n+2) != 1) return 0; |
---|
13 | for (j = 1; j <= n; j++) |
---|
14 | if (z(j) != -1 && z(j) != 1) return 0; |
---|
15 | |
---|
16 | return 1; |
---|
17 | } |
---|
18 | |
---|
19 | |
---|
20 | |
---|
21 | int main() |
---|
22 | { |
---|
23 | RR::SetPrecision(150); |
---|
24 | long n, b, size; |
---|
25 | |
---|
26 | cerr << "n: "; |
---|
27 | cin >> n; |
---|
28 | |
---|
29 | cerr << "b: "; |
---|
30 | cin >> b; |
---|
31 | |
---|
32 | cerr << "size: "; |
---|
33 | cin >> size; |
---|
34 | |
---|
35 | cerr << "prune: "; |
---|
36 | long prune; |
---|
37 | cin >> prune; |
---|
38 | |
---|
39 | ZZ seed; |
---|
40 | cerr << "seed: "; |
---|
41 | cin >> seed; |
---|
42 | |
---|
43 | if (seed != 0) |
---|
44 | SetSeed(seed); |
---|
45 | |
---|
46 | char alg; |
---|
47 | cerr << "alg [fqQxr]: "; |
---|
48 | cin >> alg; |
---|
49 | |
---|
50 | double TotalTime = 0; |
---|
51 | long TotalSucc = 0; |
---|
52 | |
---|
53 | long iter; |
---|
54 | |
---|
55 | for (iter = 1; iter <= 20; iter++) { |
---|
56 | vec_ZZ a; |
---|
57 | a.SetLength(n); |
---|
58 | |
---|
59 | ZZ bound; |
---|
60 | |
---|
61 | LeftShift(bound, to_ZZ(1), b); |
---|
62 | |
---|
63 | long i; |
---|
64 | for (i = 1; i <= n; i++) { |
---|
65 | RandomBnd(a(i), bound); |
---|
66 | a(i) += 1; |
---|
67 | } |
---|
68 | |
---|
69 | ZZ S; |
---|
70 | |
---|
71 | do { |
---|
72 | RandomLen(S, n+1); |
---|
73 | } while (weight(S) != n/2+1); |
---|
74 | |
---|
75 | ZZ s; |
---|
76 | clear(s); |
---|
77 | for (i = 1; i <= n; i++) |
---|
78 | if (bit(S, i-1)) |
---|
79 | s += a(i); |
---|
80 | |
---|
81 | mat_ZZ B(INIT_SIZE, n+1, n+3); |
---|
82 | |
---|
83 | for (i = 1; i <= n; i++) { |
---|
84 | B(i, i) = 2; |
---|
85 | B(i, n+1) = a(i) * n; |
---|
86 | B(i, n+3) = n; |
---|
87 | } |
---|
88 | |
---|
89 | for (i = 1; i <= n; i++) |
---|
90 | B(n+1, i) = 1; |
---|
91 | |
---|
92 | B(n+1, n+1) = s * n; |
---|
93 | B(n+1, n+2) = 1; |
---|
94 | B(n+1, n+3) = n; |
---|
95 | B(n+1, n+3) *= n/2; |
---|
96 | |
---|
97 | swap(B(1), B(n+1)); |
---|
98 | |
---|
99 | for (i = 2; i <= n; i++) { |
---|
100 | long j = RandomBnd(n-i+2) + i; |
---|
101 | swap(B(i), B(j)); |
---|
102 | } |
---|
103 | |
---|
104 | double t; |
---|
105 | |
---|
106 | LLLStatusInterval = 10; |
---|
107 | |
---|
108 | t = GetTime(); |
---|
109 | switch (alg) { |
---|
110 | case 'f': |
---|
111 | BKZ_FP(B, 0.99, size, prune, SubsetSumSolution); |
---|
112 | break; |
---|
113 | case 'q': |
---|
114 | BKZ_QP(B, 0.99, size, prune, SubsetSumSolution); |
---|
115 | break; |
---|
116 | case 'Q': |
---|
117 | BKZ_QP1(B, 0.99, size, prune, SubsetSumSolution); |
---|
118 | break; |
---|
119 | case 'x': |
---|
120 | BKZ_XD(B, 0.99, size, prune, SubsetSumSolution); |
---|
121 | break; |
---|
122 | case 'r': |
---|
123 | BKZ_RR(B, 0.99, size, prune, SubsetSumSolution); |
---|
124 | break; |
---|
125 | default: |
---|
126 | Error("invalid algorithm"); |
---|
127 | } |
---|
128 | |
---|
129 | |
---|
130 | t = GetTime()-t; |
---|
131 | |
---|
132 | long succ = 0; |
---|
133 | for (i = 1; i <= n+1; i++) |
---|
134 | if (SubsetSumSolution(B(i))) |
---|
135 | succ = 1; |
---|
136 | |
---|
137 | TotalTime += t; |
---|
138 | TotalSucc += succ; |
---|
139 | |
---|
140 | if (succ) |
---|
141 | cerr << "+"; |
---|
142 | else |
---|
143 | cerr << "-"; |
---|
144 | } |
---|
145 | |
---|
146 | cerr << "\n"; |
---|
147 | |
---|
148 | cerr << "number of success: " << TotalSucc << "\n"; |
---|
149 | cerr << "average time: " << TotalTime/20 << "\n"; |
---|
150 | |
---|
151 | return 0; |
---|
152 | } |
---|
153 | |
---|
154 | |
---|
155 | |
---|