-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLLL.cpp
More file actions
154 lines (135 loc) · 9.71 KB
/
LLL.cpp
File metadata and controls
154 lines (135 loc) · 9.71 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <vector>
#include <tuple>
#include <cmath>
double dot(const std::vector<int> x, const std::vector<double> y);
double dot(const std::vector<double> x, const std::vector<double> y);
double dot(const std::vector<int> x, const std::vector<int> y);
std::tuple<std::vector<double>, std::vector<std::vector<double>>> Gram_Schmidt_squared(const std::vector<std::vector<int>> b);
void SizeReduce(std::vector<std::vector<int>>& b, std::vector<std::vector<double>>& mu, const int i, const int j);
void LLLReduce(std::vector<std::vector<int>>& b, const float d);
void PrintMat(const std::vector<std::vector<int>> b, int n, int m){
for(int i = 0, j; i < n; ++i){
for(j = 0; j < m; ++j) printf("%d, ", b[i][j]);
puts("\b\b");
}
}
int main(){
std::vector<std::vector<int>> b = {
{-1, 3, 0, -1, -1, 0, -6, 0, -28, -2, 0, -1, 0, -1, 0, -15, 0, -6, 0, -1, -1, -1, -1, -28, -99, -2, 2, -1, -1, -1, 1, 11, 1, -3, 0, 0, 2, 1, -2, 0 },
{1, -1, 13, 1, -1, -1, 3, -10, 1, 1, -3, 1, 1, 2, 2, -1, -1, -1, 1, 0, 2, -2, -1, 1, 1, 3, 1, -1, 2, -2, -9, -3, 1, -3, 0, -2, -1, -4, -1, 1 },
{-3, 0, -3, 1, 1, -3, -3, 6, 2, -1, 1, 0, 0, -4, -1, -1, -4, 1, 1, 3, 0, 2, -1, -1, -9, -1, -1, -1, 1, 0, 0, 1, 0, -1, 1, -1, 0, 2, 13, 0 },
{-1, -1, 1, 1, 0, 0, -2, 0, -9, 2, 1, -1, -1, 1, 2, -2, 1, 1, -1, -20, 0, 1, 0, -1, -1, -1, -1, 296, -3, -1, 1, 2, -11, 2, 8, 14, -1, 0, -3, 1 },
{-2, 0, -1, 1, -1, -1, 1, -1, 1, 6, -1, 0, -1, 1, -11, 1, 1, -1, 1, 1, -3, -1, -1, -1, 4, 5, -4, -1, 3, 0, 1, -5, -1, -2, 1, -1, 1, -3, 0, -5 },
{0, 0, 6, 2, -1, 1, 1, 0, 1, 12, 1, -6, 3, 1, 0, -1, 0, 0, 0, 2, 0, 3, -1, 0, 0, -1, 1, 1, 0, 12, -1, 0, 119, -2, -11, 29, 0, 1, 2, -2 },
{0, 1, 14, -2, 1, 2, 1, -3, -1, 0, 1, 1, -3, 0, 2, -2, -1, -1, -2, 0, 1, 15, 14, -4, 1, 0, -1, 1, 1, 1, 4, -1, 17, 1, -2, 1, 3, 0, 3, -1 },
{1, -3, -1, 0, -1, 1, -3, 13, -1, -1, 3, -2, 1, 1, 1, 1, -3, 2, -6, -13, 1, 0, 1, -2, -1, 2, 0, -1, -3, 0, -1, 11, -3, 11, -4, 1, 1, -2, -4, -3 },
{0, -7, -1, 0, 1, 0, -37, 0, 0, 1, -16, 0, 1, -2, 0, -7, 5, 2, 2, -1, 1, 2, -12, 0, 0, 4, -1, -1, 1, 17, 13, 0, 2, 2, -1, 0, 0, -1, 5, -8 },
{1, 1, -1, 1, 3, 0, -1, 2, -1, 2, -1, -7, 2, -1, 1, -4, 3, 1, 2, -1, 0, 4, 1, -11, 6, -144, 1, -3, 0, -35, 2, 3, 1, -1, 1, 4, 12, 3, 0, 2 },
{-1, -1, 1, -1, 9, 0, 1, 1, 0, 2, 6, -2, -2, 1, -1, 142, 0, 1, 0, 3, 2, -1, 1, 0, -1, -2, -12, -13, -1, 3, 5, 2, -4, -1, -2, -2, -3, 0, 0, 1 },
{0, 17, 0, 2, -16, -3, 0, 0, 1, 26, 1, -3, 3, -2, -4, 0, -2, 0, 1, 1, -1, -6, 1, -5, 1, 1, 1, 0, -1, -3, 18, 4, 2, -3, -107, -5, -6, 0, -3, 1 },
{2, -2, 3, 1, 3, -7, -1, 1, 1, 0, 7, -5, 0, -1, 0, 68, 2, 1, -1, 4, 0, 7, 0, 3, 11, 1, -1, -2, 0, 0, 26, -1, 5, -4, -1, 4, -1, -3, 1, -1 },
{1, 1, -5, 1, -1, -1, 0, 1, -40, 1, -1, -1, 1, 1, 2, 1, 0, -30, 1, -1, 0, 2, 1, 0, -2, -1, 0, -6, 1, 2, 1, 2, 1, -1, 0, 0, 1, -2, 1, 3 },
{-7, 5, -2, 2, 3, 0, -1, 1, 1, -218, 2, -1, -1, 2, -2, -1, 0, -1, 0, 5, 1, -1, -1, 1, 0, 1, 1, 1, 1, 1, 0, -3, 3, -1, 1, -1, 0, 1, -2, 1 },
{0, 0, -3, -4, 1, -1, -12, -3, 9, 2, 0, -1, -15, -1, -1, 1, -1, -3, 0, -1, -1, 0, 1, 0, 1, 0, -9, 0, 0, 6, 0, 1, -1, -1, -10, -1, 23, 8, 0, 5 },
{2, 1, -4, 0, 0, 1, 1, -1, 2, 6, 1, 2, 4, 0, 2, -1, 22, -1, 0, 1, -3, 2, 1, 0, 1, 0, -3, -2, 0, 4, 0, -2, 1, 3, 1, 1, 0, 1, 1, 0 },
{-12, -1, 0, 1, 0, 1, 1, -1, 1, -27, -1, 2, 1, 1, 1, 5, -1, 2, 1, 0, 2, -8, 0, 0, 11, 95, 2, 1, -1, 1, -1, -2, -3, 0, -2, -2, 2, -1, -3, -2 },
{9, -1, -1, 1, -1, 4, -1, -1, 1, 0, -3, 1, 1, 6, 1, -1, -1, 1, 1, 0, 0, 0, 0, -1, 3, 2, 0, -1, -1, -1, 3, 1, 0, -1, 0, -1, -1, -3, 1, -1 },
{-5, -4, -7, -2, 1, -1, 3, 2, -3, -1, 1, 0, 14, 1, 0, 0, 0, 1, -1, 3, -1, -1, 2, -1, -4, 1, -4, 1, 0, 0, 142, -1, 2, -1, 0, -10, 3, -4, 1, -2 },
{0, 1, 0, 1, -2, -1, 0, 0, 1, 0, -1, 1, 2, 0, 0, 3, -1, 1, -1, 0, -1, 0, 156, 5, 0, -3, -3, 7, 1, 184, 4, 1, -33, 1, -5, 0, 8, 0, 1, 0 },
{-1, -1, 1, -1, 2, 0, 0, 1, 1, 5, -47, 1, 1, -3, -15, 0, 3, 1, 2, 3, 1, -2, -9, -15, 49, -3, 0, -16, -1, 0, -1, 1, 0, -1, 3, 1, -1, 6, -29, -1 },
{0, -7, -1, -1, -3, 2, -2, 20, 0, -1, 170, 30, 0, -1, 1, 1, -1, 3, 1, 2, -1, 2, 4, 1, -2, 3, -1, 0, 1, 0, -7, 1, -1, 323, -1, -1, 0, 0, 8, -22 },
{-1, -18, 1, -2, -4, -1, 1, 0, 1, -2, 1, -1, 7, -1, 1, -1, 3, -1, -3, 0, 3, 2, 3, -1, -1, 1, 0, -1, 1, 3, -1, 0, -12, -1, 4, 0, -3, 1, -1, 0 },
{1, 1, -17, 0, -1, 3, 4, -1, -4, -1, 2, 1, -2, 2, 0, 0, 0, 1, 1, 1, 1, 1, 0, 2, 3, 5, 1, 2, -1, 2, 1, -4, 0, 0, 4, 1, 24, 0, -1, 2 },
{0, -2, 8, 2, -1, 4, 1, -1, 10, 1, -1, 2, 3, 0, 7, -1, 8, -1, -6, 5, -1, 1, -123, -1, 1, 3, -1, -2, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, -1 },
{3, 1, 7, -1, -3, -1, 3, -1, 3, -1, -65154, -1, 1, 2, -2, 3, 1, -23, 10, -2, 0, 0, 0, 3, -1, 2, 0, -1, -1, 8, -5, 1, 0, -2, 0, 0, 0, 1, -1, 3 },
{0, -1, -4, 2, 4, 19, 3, 0, -1, 1, -2, -2, 2, -1, 0, -1, 0, -1, -1, 0, 1, -1, -1, -2, 0, 8, 0, 0, 0, -8, -1, -1, 1, 2, 1, 3, -1, 9, -2, 1 },
{1, -1, 1, 1, 25, 2, -2, 0, 4, 1, 1, 0, -1, 0, 1, -6, 0, 1, -1, -1, -3, 0, 1, -2, 59, 0, 1, -2, 1, 1, -1, -1, 0, 2, 1, -1, 1, 0, 1, -3 },
{1, 4, 1, 4, 1, -2, -58, 0, -9, -1, -1, -1, -1, 0, -20, 0, -1, 0, -2, 0, 1, 4, 2, 5, 19, -1, -3, 1, 140, 1, -2, -1, 0, -1, 3, 2, -1, 0, -2, -1 },
{18, -1, 1, -3, -1, -1, 0, 2, 14, -2, -1, 1, 0, -1, 2, -1, -1, 0, -4, 1, 1, -7, -2, -1, -4, 2, 3, -1, -2, -1, -6, -1, -1, 0, -39, 3, 0, 0, -2, 40 },
{-5, 1, 0, -1, 2, 0, 3, 0, 1, 6, 1, 0, 2, 0, -3, -4, -1270, 1, -1, 1, -2, 2, -2, -1, -4, 1, -1, -2, 1, -2, 2, 0, -3, 2, 0, 1, -1, 0, -1, 1 },
{-49, 0, 0, -1, 1, 1, -3, -9, 0, 0, 0, -2, 1, 1, -47, 0, 0, 0, 4, 6, -2, -2, 0, 2, 1, 2, 1, -1, 1, 4, 7, 0, 1, -1, 0, -1, -1, 1, 0, -1 },
{-2, -1, -2, 1, 17, 1, 10, 6, 0, -1, -1, -2, -3, 1, 1, 1, 5, 18, 1, 0, 49, 7, 0, 2, 0, 0, -1, 0, 0, 0, 2, -2, 1, 0, 0, -1, 0, 0, -2, 3 },
{-1, -1, 166, 0, -46, 0, -2, 0, 1, 1, 15, -2, 1, 12, 1, 4, 0, -2, 1, -1, 0, -1, 0, 0, -25, -6, 0, -1, -4, 0, 1, 2, 78, -15, 2, 0, 0, -1, 17, 17 },
{-13, 4, -16, -1, 0, 1, 0, 1222, 1, -1, 1, 0, 0, 1, 1, 1, 0, 0, -1, 1, 0, 0, 0, 0, -1, 0, -5, 3, 1, 1, -1, -1, -1, -1, 3, 0, 0, -4, 2, -1 },
{1, 2, -2, 0, 0, -4, 1, -1, 9, -1, -1, -13, 24, -1, -1, -8, 1, -1, -29, 0, 1, 0, -1, 1, 1, 1, 1, 4, 9, -1, -1, 0, -18, -1, -1, 1, 6, -1, -4, 0 },
{6, -13, 0, 0, 0, 15, 0, -3, 0, -2, 0, -2, 1, -1, -2, -1, 0, 1, -2, 0, 1, -1, 1, -1, -9, 1, 6, -5, -9, 0, 1, -2, -1, -2, 9, 1, 1, 3, 0, 1 },
{1, 3, -2, -1, -3, 1, -2, -1, -1, -2, 460, 1, 2, -8, 0, 2, 0, 4, 0, 1, -1, 0, 0, -1, -1, 4, 23, -1, -1, -1, -1, -4, 2, 15, -2, 3, 0, -1, 2, -1 },
{0, 0, -1, 1, 69, 4, 0, -2, 0, 8, 1, 4, 1, 2, -2, 0, -2, -1, 8, -4, 1, -11, 0, -1, -1, 0, -1, 0, 1, -1, -11, 0, 505, 3, 8, -1, -1, 1, -3, 1}
};
LLLReduce(b, 0.99);
PrintMat(b, 40, 40);
printf("norm = %lf\n", sqrt(dot(b[0], b[0])));
return 0;
}
/* 内積 */
double dot(const std::vector<int> x, const std::vector<double> y){
double z = 0.0;
const int n = x.size();
for(int i = 0; i < n; ++i) z += x.at(i) * y.at(i);
return z;
}
double dot(const std::vector<double> x, const std::vector<double> y){
double z = 0.0;
const int n = x.size();
for(int i = 0; i < n; ++i) z += x.at(i) * y.at(i);
return z;
}
double dot(const std::vector<int> x, const std::vector<int> y){
double z = 0.0;
const int n = x.size();
for(int i = 0; i < n; ++i) z += x.at(i) * y.at(i);
return z;
}
/* Gram-Schmidtの直交化 */
std::tuple<std::vector<double>, std::vector<std::vector<double>>> Gram_Schmidt_squared(const std::vector<std::vector<int>> b){
const int n = b.size(), m = b.at(0).size(); int i, j, k;
std::vector<double> B(n);
std::vector<std::vector<double>> GSOb(n, std::vector<double>(m)), mu(n, std::vector<double>(n));
for(i = 0; i < n; ++i){
mu.at(i).at(i)= 1.0;
for(j = 0; j < m; ++j) GSOb.at(i).at(j) = b.at(i).at(j);
for(j = 0; j < i; ++j){
mu.at(i).at(j) = dot(b.at(i), GSOb.at(j)) / dot(GSOb.at(j), GSOb.at(j));
for(k = 0; k < m; ++k) GSOb.at(i).at(k) -= mu.at(i).at(j) * GSOb.at(j).at(k);
}
B.at(i) = dot(GSOb.at(i), GSOb.at(i));
}
return std::forward_as_tuple(B, mu);
}
/* 部分サイズ基底簡約 */
void SizeReduce(std::vector<std::vector<int>>& b, std::vector<std::vector<double>>& mu, const int i, const int j){
int q;
const int m = b.at(0).size();
if(mu.at(i).at(j) > 0.5 || mu.at(i).at(j) < -0.5){
q = round(mu.at(i).at(j));
for(int k = 0; k < m; ++k) b.at(i).at(k) -= q * b.at(j).at(k);
for(int k = 0; k <= j; ++k) mu.at(i).at(k) -= mu.at(j).at(k) * q;
}
}
/* LLL基底簡約 */
void LLLReduce(std::vector<std::vector<int>>& b, const float d = 0.99){
const int n = b.size(), m = b.at(0).size(); int j, i, h;
double t, nu, BB, C;
std::vector<std::vector<double>> mu;
std::vector<double> B; std::tie(B, mu) = Gram_Schmidt_squared(b);
int tmp;
for(int k = 1; k < n;){
h = k - 1;
for(j = h; j > -1; --j) SizeReduce(b, mu, k, j);
//Checks if the lattice basis matrix b satisfies Lovasz condition.
if(k > 0 && B.at(k) < (d - mu.at(k).at(h) * mu.at(k).at(h)) * B.at(h)){
for(i = 0; i < m; ++i){tmp = b.at(h).at(i); b.at(h).at(i) = b.at(k).at(i); b.at(k).at(i) = tmp;}
nu = mu.at(k).at(h); BB = B.at(k) + nu * nu * B.at(h); C = 1.0 / BB;
mu.at(k).at(h) = nu * B.at(h) * C; B[k] *= B.at(h) * C; B.at(h) = BB;
for(i = 0; i <= k - 2; ++i){
t = mu.at(h).at(i); mu.at(h).at(i) = mu.at(k).at(i); mu.at(k).at(i) = t;
}
for(i = k + 1; i < n; ++i){
t = mu.at(i).at(k); mu.at(i).at(k) = mu.at(i).at(h) - nu * t;
mu.at(i).at(h) = t + mu.at(k).at(h) * mu.at(i).at(k);
}
--k;
}else ++k;
}
}