-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLLL.py
More file actions
113 lines (101 loc) · 7.6 KB
/
LLL.py
File metadata and controls
113 lines (101 loc) · 7.6 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
import numpy as np
def Gram_Schmidt(b):
m: int = b.shape[1]; n: int = b.shape[0]
GSOb = np.zeros((n, m)); mu = np.eye(n)
for i in range(n):
GSOb[i] = b[i][:]
for j in range(i):
mu[i, j] = (b[i] @ GSOb[j]) / (GSOb[j] @ GSOb[j])
GSOb[i] -= mu[i, j] * GSOb[j][:]
return GSOb, mu
# 部分サイズ基底簡約
def SizeReduce(b, mu, i, j):
n = b.shape[0]; m = b.shape[1]
if abs(mu[i, j]) > 0.5:
q = round(mu[i, j])
b[i] -= q * b[j][:]
mu[i][: j + 1] -= q * mu[j][: j + 1].copy()
return b, mu
# GSO情報の更新（LLL）
def GSOupdate_LLL(mu, B, k):
nu = mu[k, k - 1]
b = B[k] + nu ** 2 * B[k - 1]; b_inv = 1. / b
mu[k, k - 1] = nu * B[k - 1] * b_inv
B[k] *= B[k - 1] * b_inv
B[k - 1] = b
tmp = mu[k - 1][: k - 1].copy()
mu[k - 1][: k -1 ] = mu[k][: k - 1].copy()
mu[k][: k - 1] = tmp.copy()
#for j in range(k - 1):
# mu[k - 1, j], mu[k, j] = mu[k, j], mu[k - 1, j]
for i in range(k + 1, B.size):
t = mu[i, k]
mu[i, k] = mu[i, k - 1] - nu * t
mu[i, k - 1] = t + mu[k, k - 1] * mu[i, k]
return mu, B
# LLL基底簡約
def LLL_reduce(b, d):
n = b.shape[0]
GSOb, mu = Gram_Schmidt(b)
B = np.zeros(n)
B = np.sum(GSOb * GSOb, axis = 1)
k = 1
while k < n:
#partial size reduction
for j in range(k)[::-1]: b, mu = SizeReduce(b, mu, k, j)
#Satisfies Lovasz condition or not
if B[k] >= (d - mu[k, k - 1] * mu[k, k - 1]) * B[k - 1]:
k += 1
else:
b[k], b[k - 1] = b[k - 1], b[k].copy()
mu, B = GSOupdate_LLL(mu, B, k)
k = max(k - 1, 1)
return b
def main():
b = np.array([
[-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]
])
b = LLL_reduce(b, 0.99)
print(b)
print(f'norm = {np.linalg.norm(b[0])}')
if __name__ == '__main__':
main()