---
# System prepended metadata

title: Lattices trong cuộc sống =(((
tags: [Writeup_CTF]

---

# Lattices trong cuộc sống =(((

## Không gian vector

Trước khi bắt đầu nói về lattices, ta nói về không gian vector. Không gian vector có thể được định nghĩa theo tính tổng quát  là một tập hợp của các đại lượng gọi là vectơ, một đại lượng có thể cộng và nhân bởi một số, được gọi là vô hướng. 

Cho một không gian vector V là một tập con của $R^m$ với tính chất:

$$\alpha_1v_1 + \alpha_2v_2 \in V\ \hspace{1cm} \forall v_1,v_2 \in V \text{và}\ \forall \alpha_1, \alpha_2 \in R. $$

## Tổ hợp tuyến tính

Ta có $v_1,v_2,...,v_k \in V$. Một tổ hợp tuyến tính của $v_1,v_2,...,v_k \in V$ có dạng:

$$w = \alpha_1v_1 + \alpha_2v_2 +...+ \alpha_kv_k\ \text{với}\ \alpha_1,...,\alpha_k\ \in\ R$$

Tập hợp các tổ hợp tuyến tính như vậy, $\{\alpha_1v_1 + ... + \alpha_kv_k:\alpha_1,...,\alpha_k \in R \}$ được gọi là **span** của $\{v_1,...,v_k\}$.

## Độc lập tuyến tính.

Một tổ hợp các vector $v_1,v_2,...,v_k \in V$ độc lập tuyến tính nếu nghiệm duy nhất của phương trình

$$\alpha_1v_1 + \alpha_2v_2 + ...+ \alpha_kv_k = 0$$

là $$\alpha_1 = \alpha_2 = ... = \alpha_k = 0$$

Từ đó, ta có được đề xuất sau:

Cho $V \subset R^m$ là một không gian vector thỏa mãn:
-    Có cơ sở cho V
-    Hai cơ sở bất kỳ cho V có cùng số phần tử vector
-    Cho $v_1,v_2,...,v_k$ làm cơ sở cho V và cho $w_1,w_2,...,w_k$ làm cơ sở cho tập hợp n khác V. Ta có thể viết được như sau:

$$w_1 = \alpha_{1_1}v_1 + \alpha_{1_2} + ... + \alpha_{1_n}v_n,$$
$$w_2 = \alpha_{2_1}v_1 + \alpha_{2_2} + ... + \alpha_{2_n}v_n,$$
$$...$$
$$w_n = \alpha_{n_1}v_1 + \alpha_{n_2} + ... + \alpha_{n_n}v_n.$$

Khi đó, $w_1,...,w_n$ cũng là cơ sở cho V khi và chỉ khi nghiệm của ma trận 

$$
\begin{pmatrix}
\alpha_{1_1} & \alpha_{1_2} & \dots & \alpha_{1_n} \\
\alpha_{2_1} & \alpha_{2_2} & \dots & \alpha_{2_n} \\
\vdots & \vdots & \ddots & \vdots \\
\alpha_{n_1} & \alpha_{n_2} & \dots & \alpha_{n_n}
\end{pmatrix}
$$
 không bằng 0.
 
## Sizes

Cho $v,w \in V \subset R^m$ như sau

$v = (x_1,x_2,...,x_n)$ và $w = (y_1,y_2,...y_n)$

Tích của hai vector đó là

$$v.w = x_1y_1 + x_2y_2 + ... + x_ny_n$$

Ta nói rằng hai vector trực giao với nhau nếu $v.w = 0$

Chiều dài của một vector ký hiệu là $||v||$ được tính theo công thức như sau

$$||v|| = \sqrt{x_1^2 + x_2^2 + ... + x_n^2}$$

hoặc cũng có thể tính như sau

$$v.v = ||v||^2$$


## Lattices: Định nghĩa và tính chất cơ bản

Định nghĩa: Cho $v_1,...,v_n  \in R^m$ tập hợp các vector độc lập tuyến tính. Lattice L được tạo bởi $v_1,...,v_n$ là tổ hợp tuyến tính với các hệ số trong tập hợp Z,

$$L = \{\alpha_1v_1 + \alpha_2v_2 + ... +\alpha_nv_n : \alpha_1, \alpha_2,...,\alpha_n \in Z \}$$

Giả sử $v_1,...,v_n$ là cơ sở cho mạng tinh thể L và $w_1,...,w_n \in L$ là một tập hợp các vectơ khác trong L. Giống như chúng ta đã làm cho các không gian vector, chúng ta có thể viết được như sau

$$w_1 = \alpha_{1_1}v_1 + \alpha_{1_2} + ... + \alpha_{1_n}v_n,$$
$$w_2 = \alpha_{2_1}v_1 + \alpha_{2_2} + ... + \alpha_{2_n}v_n,$$
$$...$$
$$w_n = \alpha_{n_1}v_1 + \alpha_{n_2} + ... + \alpha_{n_n}v_n.$$

Nhưng giờ ta đang xử lý ở Lattice, ta sẽ có được như sau

$$
A = \begin{pmatrix}
\alpha_{1_1} & \alpha_{1_2} & \dots & \alpha_{1_n} \\
\alpha_{2_1} & \alpha_{2_2} & \dots & \alpha_{2_n} \\
\vdots & \vdots & \ddots & \vdots \\
\alpha_{n_1} & \alpha_{n_2} & \dots & \alpha_{n_n}
\end{pmatrix}
$$

và ta có rằng 
$$1 = det(I) = det(AA^{-1}) = det(A)det(A^{-1})$$


Ví dụ: Cho lattice $L \subset R^3$ được tạo bởi 3 vector

$$v_1=(2,1,3),\ v_2=(1,2,0),\ v_3=(2,−3,−5)$$

Ta chuyển nó thành ma trận A như sau

$$
A = \begin{pmatrix}
2 & 1 &  3 \\
1 & 2 &  0 \\
2 & - 3 & -5\\
\end{pmatrix}
$$

Ta chọn 3 vector mới thuộc L theo công thức

$$ w_1=v_1+v_3, w_2=v_1−v_2+2v_3, w_3=v_1+2v_2.$$

Ta có được ma trận U theo các hệ số của 3 vector trên.

$$
U = \begin{pmatrix}
1 & 0 &  1 \\
1 & -1 &  2 \\
1 & 2 & 0\\
\end{pmatrix}
$$

Ta có thể thấy được 3 vector w khi mà lấy U.A

$$
B =U.A= \begin{pmatrix}
4 & -2 &  -2 \\
5 & -7 &  -7 \\
4 & 5  &  3\\
\end{pmatrix}
$$

Ma trận U có định thức là -1 != 0 thế nên các vector w cũng là cơ sở của L. Ma trận nghịch đảo của U là:

$$
U^{-1} = \begin{pmatrix}
4 & -2 &  -1 \\
-2 & 1 &  1 \\
-3 & 2 & 1\\
\end{pmatrix}
$$

Và các dòng của $U^{-1}$ cũng có thể biểu diễn các vector v theo vector w

$$v_1=4w_1−2w_2−w_3,\ v_2=−2w_1+w_2+w_3,\ v_3=−3w_1+2w_2+w_3.
$$

Giờ mình ví dụ cho một lattice cho các bạn hiểu nha.

Cho vector cơ sở của L là $v_1 = (2,3) ,\ v_2 = (4,5)$. Từ đó ta được $$L = \{\alpha_1v_1 + \alpha_2v_2 : \alpha_1, \alpha_2 \in Z \}$$ 1 điểm $(a,b)$ trong L sẽ có 2 giá trị x, y thỏa mãn 

$$x*v_1 + y*v_2 = (a,b)$$

Giờ ta sẽ lập lattice bằng sage nha.

```sage
sage: L = matrix(ZZ, [[2,3], [4,5]])
sage: L
[2 3]
[4 5]
```

Giờ để check coi điểm (a,b) này có thuộc L không thì ta sẽ dùng span.

```sage
sage: vector([1,2]) in span(L)
False
sage: vector([34,45]) in span(L) # x = 5, y = 6
True
sage: vector([100,130]) in span(L) #x = 10, y = 20
True
```

##  Lenstra, Lenstra và Lovász

Thuật toán LLL là một thuật toán giảm lattice, nghĩa là sẽ trả về một cơ sở khác cho cùng một mạng với các vector cơ sở ngắn hơn. Nếu số bé có thể sử dụng Gram-Schmidt, thế nhưng, trong nhiều trường hợp thì LLL vẫn tối ưu nhất.

Vì det() của các lattice là cố định và được tính bằng định thức của các vector cơ sở, thế nên trước và sau LLL đều sẽ có det() như nhau. 

Ta ví dụ trong bài **FIND THE LATTICE**

```python
from Crypto.Util.number import getPrime, inverse, bytes_to_long
import random
import math

FLAG = b'crypto{?????????????????????}'


def gen_key():
    q = getPrime(512)
    upper_bound = int(math.sqrt(q // 2))
    lower_bound = int(math.sqrt(q // 4))
    f = random.randint(2, upper_bound)
    while True:
        g = random.randint(lower_bound, upper_bound)
        if math.gcd(f, g) == 1:
            break
    h = (inverse(f, q)*g) % q
    return (q, h), (f, g)


def encrypt(q, h, m):
    assert m < int(math.sqrt(q // 2))
    r = random.randint(2, int(math.sqrt(q // 2)))
    e = (r*h + m) % q
    return e


def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m


public, private = gen_key()
q, h = public
f, g = private

m = bytes_to_long(FLAG)
e = encrypt(q, h, m)

print(f'Public key: {(q,h)}')
print(f'Encrypted Flag: {e}')
```

Bạn cũng có thể đọc lời giải của Drago từ Cryptohack

![image](https://hackmd.io/_uploads/Skq-3lIbA.png)


Ta có rằng 
$$h = f^{-1}*g \mod q$$
$$\iff h*f = g \mod q$$
    $$\iff h*f = g + q*k$$
$$\iff h*f - q*k = g$$

Giờ ta sẽ đặt ma trận 


$$
\begin{pmatrix}
h&1 \\
q&0\\
\end{pmatrix}
$$

Như mình có ví dụ ở trên về lattice, sẽ có 1 điểm $(a,b)$ trong L sẽ có 2 giá trị x, y thỏa mãn 

$$x*v_1 + y*v_2 = (a,b)$$

Thế nên, ta sẽ có cơ hội tìm cơ sở nhỏ nhất của lattice sao cho

$$x*v_1 + y*v_2 = (h,1)$$
$$x*v_1 + y*v_2 = (q,1)$$

Ta thấy rằng, $f\cdot(h,1)+(-k)\cdot(q,0)=(g,f)$, thế nên khi ta LLL, ta sẽ thu được giá trị g và f ở row đầu tiên. Thực ra, LLL sẽ tìm cơ sở nhỏ nhất sao cho $(h,1)$ và $(q,0)$ trong span của cơ sở đó.

Có thể bạn sẽ không hiểu, nên mình lấy số nguyên tố 8 bit cho dễ hiểu nha.

Ta có bộ key là **((179, 52), (7, 6))** và 

Giờ ta sẽ LLL ma trận trên

```sage
sage: M = matrix([[52,1],[179,0]]);M.LLL()
[  6   7]
[ 17 -10]
```

Giờ ta sẽ lấy ví dụ khác về LLL nha, lấy của Merkle Hellman đi. Chall này là bài warmup trong ACSC 2023.

```python
#!/usr/bin/env python3
import random
import binascii

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

def modinv(a, m):
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def gcd(a, b): 
	if a == 0: 
		return b 
	return gcd(b % a, a) 

flag = open("flag.txt","rb").read()
# Generate superincreasing sequence
w = [random.randint(1,256)]
s = w[0]
for i in range(6):
	num = random.randint(s+1,s+256)
	w.append(num)
	s += num

# Generate private key
total = sum(w)
q = random.randint(total+1,total+256)
r = 0
while gcd(r,q) != 1:
	r = random.randint(100, q)

# Calculate public key
b = []
for i in w:
	b.append((i * r) % q)

# Encrypting
c = []
for f in flag:
	s = 0
	for i in range(7):
		if f & (64>>i):
			s += b[i]
	c.append(s)

print(f"Public Key = {b}")
print(f"Ciphertext = {c}")
print()
# Output:
# PublicKey = [7352, 2356, 7579, 19235, 1944, 14029, 1084]
# Ciphertext = [8436, 22465, 30044, 22465, 51635, 10380, 11879, 50551, 35250, 51223, 14931, 25048, 7352, 50551, 37606, 39550]
```

Bài này sẽ kiểu có 1 public key, sau đó sẽ chuyển từng ký tự của flag thành binary, nếu là 1 thì sẽ cộng public key tương ứng lại. 
Ví dụ:
```python
A = 1000001
Ciphertext[0] = 7352 + 1084 = 8436
C = 1000011
Ciphertext[1] = 7352 + 14029 + 1084 = 22465
```

Bài này nếu nhiều giá trị hơn thì mình nghĩ nên dùng quy hoạch động, bạn có thể tham khảo cách làm của mình sau đây. Mình mất code rồi chỉ còn ảnh thui, tự chép ra nha hihihi.

![image](https://hackmd.io/_uploads/SJJG5_8bC.png)

Còn nếu dùng LLL, thì bạn nên dùng ví dụ sau đây trước đã.

Ta có 3 số là [9,7,5]. Giờ mình sẽ lấy ngẫu nhiên số 37 đi. Giờ làm sao để có thể tìm lại được các giá trị a, b, c nhỏ nhất thỏa mãn: $9a + 7b + 5c = 23$.

Ta đặt được ma trận sau đây

$$
a*\begin{pmatrix}
1 & 0 & 0 & 9 \\
\end{pmatrix}
$$

$$
b*\begin{pmatrix}
0 & 1 & 0 & 7\\
\end{pmatrix}
$$

$$
c*\begin{pmatrix}
0 & 0 & 1 & 5\\
\end{pmatrix}
$$

$$
d*\begin{pmatrix}
0 & 0 & 0 & -23\\
\end{pmatrix}
$$

Từ đó, ta sẽ 4 vector cơ sở có dạng $(a,b,c,9*a+7*b+5*c-23*d)$ định thức bằng ma trận cũ và các chỉ số cũng là đơn giản nhất.

```sage
sage: M = matrix([[1,0,0,9],[0,1,0,7],[0,0,1,5],[0,0,0,-23]])
sage: M.LLL()
[ 2  0  1  0]
[-1 -2  0  0]
[-1  1  0 -2]
[-1  0  2  1]
```

Từ đó, ta tìm được $a =2, b = 0, c  = 1$.

Giờ quay lại bài, ta sẽ làm như thế, nhưng mà phải biết xử lý code và mảng.

```python
PublicKey = [7352, 2356, 7579, 19235, 1944, 14029, 1084]
Ciphertext = [8436, 22465, 30044, 22465, 51635, 10380, 11879, 50551, 35250, 51223, 14931, 25048, 7352, 50551, 37606, 39550]

flag = ""

for i in range(len(Ciphertext)):
    I = identity_matrix(7)
    I = I.insert_row(7, [0 for x in range(8)])
    L_helper = [[x] for x in PublicKey]
    L_helper.append([-Ciphertext[i]])
    L = I.augment(matrix(L_helper))
    L.LLL()
    bs = "0" + "".join([str(x) for x in L.LLL()[0][:-1]])
    flag += (chr(int(bs,2)))

print(flag)
```

**Flag: ACSC{E4zY_P3@zy}**

## Knapsack Low-density Subset Sum Problems

Giờ mình cùng giải bài Backpack Cryptography trong Cryptohack nhé.

```python
import random
from collections import namedtuple
import gmpy2
from Crypto.Util.number import isPrime, bytes_to_long, inverse, long_to_bytes

FLAG = b'crypto{??????????????????????????}'
PrivateKey = namedtuple("PrivateKey", ['b', 'r', 'q'])

def gen_private_key(size):
    s = 10000
    b = []
    for _ in range(size):
        ai = random.randint(s + 1, 2 * s)
        assert ai > sum(b)
        b.append(ai)
        s += ai
    while True:
        q = random.randint(2 * s, 32 * s)
        if isPrime(q):
            break
    r = random.randint(s, q)
    assert q > sum(b)
    assert gmpy2.gcd(q,r) == 1
    return PrivateKey(b, r, q)

def gen_public_key(private_key: PrivateKey):
    a = []
    for x in private_key.b:
        a.append((private_key.r * x) % private_key.q)
    return a

def encrypt(msg, public_key):
    assert len(msg) * 8 <= len(public_key)
    ct = 0
    msg = bytes_to_long(msg)
    for bi in public_key:
        ct += (msg & 1) * bi
        msg >>= 1
    return ct

def decrypt(ct, private_key: PrivateKey):
    ct = inverse(private_key.r, private_key.q) * ct % private_key.q
    msg = 0
    for i in range(len(private_key.b) - 1, -1, -1):
         if ct >= private_key.b[i]:
             msg |= 1 << i
             ct -= private_key.b[i]
    return long_to_bytes(msg)

private_key = gen_private_key(len(FLAG) * 8)
public_key = gen_public_key(private_key)
encrypted = encrypt(FLAG, public_key)
decrypted = decrypt(encrypted, private_key)
assert decrypted == FLAG

print(f'Public key: {public_key}')
print(f'Encrypted Flag: {encrypted}')
```

```python
Public key: [260288377891444370372615148009023640057294926547602419331406531383682223097787288755377467188515435381259752760746, 322734358011758862401399370931929863052553602421714393280581187496537763321855751120439457234561080720455397490349, 88092359256403564783665281993130133541226601877969436905267415353041909757324746080398461245281826552421872983184,....]
Encrypted Flag: 45690752833299626276860565848930183308016946786375859806294346622745082512511847698896914843023558560509878243217521
```

Bài này sẽ lấy từng bit cuối của flag, sau đó sẽ nhân với publickey tương ứng, khá là giống bài kia. 

Giờ ta ví dụ chữ **cry** (vì chơi crypto chỉ có cry thui :cry:) đi, ta chuyển về bin thì ta sẽ được: ``01100011 01110010 01111001`` và thành int thì được ``109343314834543``.

Ta được bộ khóa sau đây
```python
Public key: [465443350468751008273841, 388551119148645079751987, 343715354189941964948557, 330832332266399085890144, 103304596681497730652466, 310926191372308658937420, 468189417003846036789371, 91380799065178968673274, 82560478948417404325909, 72910404280386082175094, 94833434312839833614073, 223734867649585469571881, 10928493595651490421109, 88276179981998524041147, 458969066633003948955271, 189316628509949317294639, 247725789070163904095505, 193849447948042202844838, 163106627729620370072474, 16908000900925708559205, 406490158737578495095064, 364171498820932152712359, 52539039291931227399734, 315410863617702072989429, 111221116449322665652614, 3528750617528780395977, 24461696115861382313779, 146319650160550984815748, 188081465522708218762065, 330105612726783049597743, 134269047352348664012240, 263333365773046655615680, 249109861465724598174638, 23816340941431473692250, 8215380269090481722943, 472256516973403457705030, 326506725965448435804152, 163026815594448541060866, 398662957842018521831786, 351091696578124718549518, 129724196813917573974560, 51097234473893552626139, 162021641317480642692620, 36525717111137166264096, 264068419426627724252212, 348176988829670665271493, 168775654796921949578917, 247289760476687024537852]
Encrypted Flag: 6303649443293291803510650
```

Vì là bị ngược từ dưới lên trên và cộng dồn các bit vào, nên ta không thể làm như merkle hellman được.

Bài này sẽ dựa vào Knapsack Problem (vấn đề cặp sách) để giải quyết vấn đề này. Bạn có thể tìm hiểu ở [**paper1**](https://eprint.iacr.org/2007/066.pdfhttps://eprint.iacr.org/2009/537.pdf) [**paper2**](https://eprint.iacr.org/2009/537.pdf) này hoặc là của anh [**Quốc**](https://hackmd.io/@nomorecaffeine/r1xstVfxC#1-Low-density-Subset-Sum-Problems) nhoeeee.

Cho các số nguyên dương $a_1, . . . , a_n$ và một số nguyên đích là $s$, tìm một dãy con nào đó mà có tổng là $s$. Giống như bài mình đang làm thôi.

Nhiều hệ thống mật mã dựa trên bài toán tổng tập hợp con đã được chứng minh là không an toàn thông qua các thuật toán giải quyết các trường hợp bài toán tổng tập hợp con (subnet sum problem) “low-density” đặc biệt. Mật độ của một tập các trọng số $a_1, . . . , a_n$ được xác định bởi:

$$d = \frac{n}{log_2 \ max(a_i)}$$

Và khi $d < 0.6463$ thì ta có thể sử dụng thuật toán Lagarias and Odlyzko’s, nhưng có lúc $d < 0.9408$, thì ta sẽ sử dụng  J.coster. Ta sẽ tao được một ma trận như sau:

$$
B' =  \begin{pmatrix}  1	&	&	&	 &Na_1	\\  	&1	&	&	 &Na_2	\\  	&	&\ddots	&	 &\vdots\\  	&	&	&1	 &Na_n	\\  1/2	&1/2	&\cdots	&1/2	 &Ns	 \end{pmatrix}
$$

Với $N > \frac{1}{2}.\sqrt{n}$

Khi đó, ta sẽ thu được $e = (e'_1,...,e'_n)$ với $e'_i = e_i - \frac{1}{2}$


Quay trở lại bài này, ta thấy được giá trị $max = 601684701300110945921036937572461050140352984401874675917155063594305583314408001377505387079690115000992094388032$, ta thu được giá trị d

```sage
sage: round(log(601684701300110945921036937572461050140352984401874675917155063594305583314408001377505387079690115000992094388032,2),10)
377.9668823969
sage: round(272/377.9668823969,10)
0.7196397692
```

Ta sẽ dùng J.coster, thay vì LO như bài đầu tiên.

Ta lấy giá trị $N = 10 > \frac{sqrt(272)}{2}$. Giờ thì làm như bình thường thôi.

```python
PublicKey = [260288377891444370372615148009023640057294926547602419331406531383682223097787288755377467188515435381259752760746, 322734358011758862401399370931929863052553602421714393280581187496537763321855751120439457234561080720455397490349, 88092359256403564783665281993130133541226601877969436905267415353041909757324746080398461245281826552421872983184, 601684701300110945921036937572461050140352984401874675917155063594305583314408001377505387079690115000992094388032, 193814643850628739958152744041743058858484088269609293429408490294552345005365776962194365813796130165113184925621, 51510606914703888409341761261103125433754505248101513818740574350196563260563818621033222936301769697693287778876, 502702742677974540308798846750017003106263447846689040491266463798703222616320168069962523670400796196343460832764, 86989835783586738140883150201327374176124588410464188692884973334241681514702306716383785095564084499563152815246, 515511378187957676256419959601984383408150348796281656976955880729383340611785836962788715725367023923811376366815, 119845178983025037005174732553931706284024826223176718982111213579707091766057320315419827781508690979405126062061, 207867794910968434026003881920029657224591376925067493713968219177352819759854486838459675245909787840416982457750, 239399986603216503029402544900610984881160101923294396792665204486222975420081300661354603175384772323551980155480, 306665236132315336961576566094908486196981556971172170145299174389720334940261512384837950321772782983903454058725, 558130280550827068212352576387713811027468233905173944680355562037815257403446113128895937326412940859588204361963, 123471925832174980344066571541132411467266736109103860421447462536930482316849470378251137263190870093702164003085, 146089706629012142384661350988216882483919264673129621404831339166566056469572087759748854086023354002641923689390, 446097892684389219719742914373867457099954499449824602532333181169038249081395758983133906564840000962001976506057, 204029934276059225352901134714823317920576872465404508059719045291560482057171052793698580294637069578017200124432, 412333373143000457741307988470055504576675151299345387733692618218275177027643785881042018546460452418506341967356, 171418413940299360322712423004114364681865276057786947919043883366302567169869592290151559269290446563185553350080, 401593473337411114258578268223784182795068785564101722335215736591292301602077751376477881087346810602041717163104, 204003688543820354337113938494979311981574571424756883928855286926734578790400322291262042466654212377708831289347, 555612926496986208337317871061684502803594375654879680702581403987248292734014139717756900004905653768133795128973, 462785612281910846822645629160953231999037081137615204334672445418078665808070086646804794186256411131615189487813, 77961961618173276050791733447969083544152711482614563228085622136316525792569658878271751219358260960116292497570, 517789370221435419776588087490678991824021927945387533283088388790482913301281733115458601414668206432512998904516, 281870328340314395150658482932699114581743200279996227099530744754750289102031518563761975024621347281374162044877, 60204977937304337797770029325498234132893935850995809547662640467737007197647697381430963693698522962733473746281, 395936787836195675178388359277761575381601972138693830435288611414489963379399027975388601714741876831895709497105, 90921357930302550361827901642067284191268695594120415817202534786924330392421221829361546010764453051928814876700, 238523907687908075601117120608130752369082206676107364350347208286323115036939777325067473364465438898353765093766, 277515010021988996116595000889051160811249034599876556819610707794016612800585201793339332495839495779526504613846, 187215937497318890199135284983515062319988136636108170852591598862524363777870331888216170582220867500042557737272, 411220029331367081136918789112083235781237730079305782620378994961505282090962448446931628731751970521853108685376, 433613620456520979627974441205441942311133790647897226320388205340695256818608765746266662314499649013982035729731, 509613591091334719216567967380183602959933686617275815879939870258332674755345348802452058256788513837941126219238, 352708166022264045150842358964512080203788453464883319778517822047480718640858804837886057264514786742694419419735, 486272357335492500753956372299255798603575392697018451800774427752724312455328655650777691830508441976819499348269, 1291533249748053824342851185451970324561531056195308125673915619130780992270420765078102812914222570167615953050, 520707501920546816250915326019351261090208813534492143136485743644939372232638461802625700978801768541842624647274, 272359456788721692618768612190222453304838934916628492701462591276450281926223118982602858211688086607842351391495, 119534191144397164327417397593964021477488683311215644770010641745736480039094209273092223959694752862193314087240, 394945131470603614379767959704654538029557537489316246092982427107641617479545488843535929537498546432123287486437, 395979428475608101765230328218274625986674115712051764903732593018454264017781340199795540039285257513438842708672, 322101629493887220159199019582810892418957941946300752245249462093036697035162212557261470168522953435341905295650, 60610073299031334532969727880668989046838926047395613981473675505442500833244137863225398782029541439420403686372, 492582431835005621441922899995666806499437611069193099072247918597047415020628078410849119945608854080040163699375, 356290614124448077864884136922409291617128370298210212357882465167338600485728936925448944675136056707929560080237, 469737185578879122378016959759297464132272432425745272107998534197014940235018335349886398896979254122985841196030, 522871107234918024128768136315123497251902274681110489386594944387181296826024289163431880961506314580935567743910, 407151723612481391724375429193917289623669496278028982297086458062111012958436324350527302865535766565677711383191, 597354385774970715448797740483856119139152021834911852144490298736330354118482480147237280491305029710326837274157, 541106433608213985607913120402276000940203625086988929757276286018099336445558864548353610869729642196223750468493, 417269959280528548156948994397262973057821055108288565091113745409730174626359955737489143948177504667498654245449, 165844467199853002181647516786815801413939363188955720855463610698066730208657222822269457713666541555820608908443, 54875733171006797537647859403084623422036246809497621662400918381496284440644503330411668895858884933248328986102, 465819050441857934210906305127374377291850450707906416261994960542649394393702032587209990932960399224341143990297, 369322923825463715724411404444452360125845865658673947242361968271863944079047696087621731311243573179527276498509, 553158781749591211954659671173145767949897795287325677938373702443265138456771264711232588438786042792968904732769, 409812013938165700887519758386718364160025926340003407045361393371862966914817952304595560620453598830906305966865, 494654868138757552768371639418237489264099471894419220273147503624077564865563661914136003656825657044284503346448, 583613295252460993144403074130901622751986348055784728175987246652496523293580989652454868505577305787293683850652, 45623098408168398769971239387495928980835555721564847009059790575158770295430426790200773274288087331109699336204, 39196430635656777174378129146834600960125068266405306877726260536750371354188413207203531511343645151492477471286, 269811462520469960288594953357779332541515563494806499705455036716689694055741096626927182558039773813984145657639, 56129158162087034209035841739296133948708529713411817898928727109770418208078239244331640522507423413446203417794, 524210107239750288249530336771864024916995632570549267972428294539507299820629133801771958736839361325798918246415, 74499040113803277306263886217659673645883223840279171192334357737741618882160648968176974754905084576184804774369, 537566085689080717108870646705458338163437075433046077845999622035879463636776663759447985884960181167857417860517, 67053890181708018909161683393261532526993578729770554741021482840348299866927821016301415949708659944497709907470, 226687291544149270579995169198961617407190234578516732237756117257869929434434889879973211444301745820066870869034, 30119130560797352224094299766590747178156378314088092947830899847927767559391822485618397327733723834195435500170, 273554685078063587415670757725663508130498751998110442807136494763920302805098071555958936900406570453984774374060, 87980277743580170573607118853300224477595233902389343863665172738347967268089655736029345194767280704236057718111, 415325115863346791298232938393411393462777451386243842830553121689594926353646948497680883539360608323603975987452, 291860381996369849963997875749710331697722876276851205203280910491894467229365951220031470367159168511107680106262, 554653569462940342418063467925252548314485118886100002832290030505991378878498660088540140703141291011055029173137, 323189774384600834625013268084915768916855209746568551595158521873406091567687194674213765428238599317205811518692, 271805885895959097314720980134407607645324820417975238169874050425279962478579515969226563851125481000349196674810, 273580504244152469063405670227951980303621824057876058884978331188257821496852334599050020207990127348359965113465, 89994080154200685717636930068317931325931168723237899144166312528962957042842197915530047017893088501681215899095, 179903529806043505032581494908566846659773117049401056767669943330229935007822437549131470977810261112485254094386, 337553339737054880017288314951575451797426862530219763936855885416298554494199226261714888518914541341927073075939, 55576723594346882914517616915509260915444308762551400560217462518909289055446940809390878002725822401595827206530, 16748220768196858904499918524709172735166549515085689048938405549141121222201553686060172878474455615920723669801, 317380564633191615800168658676142557493413060315417096622564923156521630376263849705099633192226251101432134441153, 533990888376667129575141849433166253104032964155895368357797314378260092470904627861359175864364684662961150582207, 51339665999563119517609216115086272052501396280925354694804471629521639434841281422984348587180771099209184749005, 598751671521816401429095343374521592165563401213195481604556405443389323390172923217639290327197434030974530635632, 502516418942980462174586089858060912235797554801782186782319843655355616321036648106166017773986280053024012403712, 96757697084956246010025820107260538706827163135748809142998937362457169471061108292297066769079020843197361323396, 160715027762704553320571142674023737670353756130518440136900430091151963142004047232920245715827837173811719927140, 279138292123840748082780689543574043699162822819208361733228093396335579794292477744981338016264347327181324984710, 76445842054689324523514421681098261857514827631364695255959418519245612571199123499205752729124353901548286671941, 383675319414133753635121914615218464358220814208747712016103562476157464944897131756675168140846189629485664787044, 260741648290568813857849033448155840373964568801980310694295413631289231242930901519918814851819352903132884286000, 572815144956474380133620797676157654285774633299428534205241845335783095326631133195133798583360396067031309578073, 326258465939147178368353573060965288327891986807699582822092415027094204965326681853802159504539722937811913340954, 270266570242986488258809014590807152136633692716132669770748395523214017062557603428657196661342410476403164567952, 594635668324174018778140793057815156885870465660609865234586849536688338135131804764199647040009222634146148815637, 112066852946512058163194024984815176069074331367673763590415760757313750687675218022751871678411881684718198988959, 72643140251973593561700085821570131390914743121754868577502110904091989089708201436984242838820806097191225214858, 418558767829526524235103555737958351573183096833081038769308995724925326439890724874671213539641031754157727776067, 196559288823369030489094238610617412012659194878611686482089456487889879135369906410569754176462601644487717691079, 484475844260869041475828428835126624027291693283800645559775410528136122290210564467730445814182429120097372738911, 397895531572254423225385975618860549078025992059379971480526615942245245283818149065605766495091059477544617632303, 173098235745543952336517747078283517802667869630628062474315240281111485771833849083340162673485620557610425012773, 395438744730241817782361196255681827924847041028664896503460681041226871979986416514203189980456170013127549062319, 470021990867207717347003710359490169212637212255796418181420825247262094876084196634243149241752002339736588912053, 116393009019558569654503508922282193810180596603376432764270301486325221610807518426481578453602546466299515294456, 312679236344738874814229979243462639486594453393064312671149009880980836289564409215088541509970023077739205203468, 125633612607015147027292740679836345332097512816636698981581758992992116056276272361001165705597842757882238693825, 550545747650576990464265884382499274254872311986381675090751886824037811235625095205217845451891396561893492715391, 582344947379262203945082609921047126789902458640974947174265099323728700596079597139164883619347159500887293859913, 597445807393853093495564866081359122814348105478914638258595339515168987499771664924728981250079847198831836930965, 203086100710322798737771097067197649738932976573837729229038404179992238381339090779534246758253939763462200026384, 366083021996787911206272856169665720981308167177143125303074466648545813452157612764258146407782634619278092168081, 568425067761875823198893591966757461338470700675615033946429149483970138055665377562238998722395767377075284081587, 292063178202410186631443519138674436645163233411161937085629856088259050827382985093506892763617302007759121037731, 572237520943575841301998365238940412928982617335768155394691567092595694943290938278464533099223273214233507106207, 130730938892686892107630262721901246969052318133502728671984157629171554435251506312878040499761922665301495030981, 185117108148352276973404708807613996548096583954940273525781406848525491758486946236965943611210198389159091280333, 37060990092986925132287820152354618271473589014825595897838753632315007172710154561879917551705194656825456571032, 403396730776194870459199627544122636010870768257463359235766775533882938128146112838489577777497432203020030499998, 390519053219213422305599109947414047895590808796368085342860468917268018310638864392199371679272174634278410878307, 128444781947873592602609418783055715736876557725608932301613294446934930933474014020041434831899064316552264614235, 543291373538613455155809248493830432520680330961337677793905220928838352322514565851452650441518480234729892153780, 488514444383813071753894478409325136755661751625837651637348989332739608743318097848609715931362718450900659714726, 345584582429475420526208382863826459005483455209655712636957752389218040279848223862500232738960994712140028026289, 93010878843154734421543561265196548806562081923037074596459052686633775723171466088126269822057315393084026072218, 12533412965882925987419497258660569237455714460582608620237638858642686843645624645184949324869641399446820464020, 562770032030414047557952904910126027215456025343530350248616818594366525600180778011275466074764589844321872364272, 128451705070871056157396910591766296038989235798264982434769256144115712608648937222298167066517556774062311420353, 490278961434267039693706795888817653385586689501848271165345121922956317504140732421546020494675482464550410472502, 212287543946551782522399704940695532581109453008804375002654843122502975490312129477869621998080277682674199046031, 351228167329138957128592454766411142609836239330479331051630155591459798299725613134325016512314887321869487481161, 364056580106158102895694571253671943571916920885795142960090311722444269241247963009814588199874030295862636577768, 323410613174912128865174768949092780979646178505039555025194364419990442219941948707117457621400459111231556621585, 555979459475319018276106133189578589964687373772995549423813902773304274184448885651570001083614054140692063026580, 471645896888183848879918063770091917659270906648819201901346651975957177950753583099047587304484006413716362087065, 595746107902898270905714635379070716651708771264047581902664532594897071557252807014533004074458867603957329534516, 557816517693603351719661411054144374250247040672226934534604151399902780319198098821629853612396635344596388943480, 75653615683769023911143698869320584951015514055697266638646507368530841035631560833198288977975782471517557394092, 386729218862361591185009654369415880766336899946663823664818477204172007165198875809899277634660190797185025579614, 393108265477944240661308455550612796769200470498502703905073280606596277788078742986164286625262059483908055127428, 365065802583204450004435661912506592532468753723399406740663534070289404492293680764078659588454240436160849321237, 343474792575856700080726394177083134771079426798042359193966109700850531408037245425173307797050676647933775237484, 449270583610225180914452784540333562631570453995885992409935055758994173533991695282410200635020830187612444056607, 152477148608000973940085532267319492932629609199964217167273279315109403426434432473053141371160594251975646390787, 215758046810520029171417357963508549726865838830930981174495643955719506571398771447950049727234258305885220507020, 388644732079570479249894814593945177309689613386566508292336098907992239994635374799070003303374928382563877494312, 33174396496627497383579687586254392056231321534282758587681567913835717050445163816449882425899904436708697640574, 293328356964375951072242072976851267186828242468018707810599907336525314670450502681522283876131924077746023996643, 292804486280753504026674757794166015519590385505528937148184945726179320137391480944836180610675717906694042510411, 278315915715399524055936806996907092937794467054749462150463756152176847617395557111508306851465386462011262385630, 103884040577296119486012754822466682224025370872916939490159319500421058932999421365377738193002421767097172706341, 111463652129659874006915288174831654634146152513640366449316440114829594116719772451443937868409442532699879776869, 475152124260969797265060453354454799124845717445357239027249597786029156307488697633998763174770332805926500738683, 220597335944113643138040910019263318251616203954548724660953303915089233301354511542662225751359573592406567125779, 460838912228809947843094986154780694841314087685379351551107763714127613789323858795003275958350186756130179585099, 140183105024444619512158726537661171898184380568070161231133567610679885584873426652521827961950911404383912561621, 100258312363732149931656549158547430770829888011033153048299126820116382987576385251423248018523377569893042593237, 405290867185420593972711092047858403431415058957648108848290712855486205273135789994549738296802436972506132007215, 256955277068974586752505570703153051582682851398012077625721880852140628262494489158976679841716540706155916871083, 598549159802958710401362839481280273681933957841944662088149512518476573000011803427513695903373248355980692446393, 308263288681016807641714404434630877489176754884164049322636274036076916608089721011418189274379096133290778967977, 8342859679410179631729508842147337278025979845268212054683951869690623917413242667876438120214556608223950514653, 439895086294728342454449126955941890844828534912064877350830376651948083146591737071488196253116258629344717466258, 91881226123407259536921548434174382841001791568169293198769940131230256611806601058471105885254628422499512141440, 377266324363766263400630205724731218877243980277025204567255708828742612895175112462476548764041808998472515741645, 116673062533491873681185131034931580572262852751033929144868000941380674942800523209276875356733463592351603448680, 57238242567269156027816815706946539463493497634492900168501163766058930300567388616552782194562204025116893421410, 589774086517371498643669747060802896861503240906569357013148621028285639980785543690656162836694887880501379427719, 299125626128142030020988742420785075132372751191528474146303145649473683269241675130370288768899920531289674244113, 304688395547666111898109663337992917557352968749730125549180444196974698222351897080702952045364871753888027443342, 482739851676824100473920409347215848398789318900117561465297399614115666738614477259195415015272146741220074932513, 223546862652113236935862556158177901803806229739994958195958127700830125319767534179348037800919714328649801362322, 150425375689725206871177727482717625428944121456212788472446922564113718518867636855506280578641904259888006038685, 143374483079122348274771015162872747263883105211675941440480524305910827744168931572051691220561136775398957657059, 128633351158033453796356108560970241527889904619011394383277988372280437398843373552825146090070247278923404428730, 249625701621261544438183108711205773478938560640571200325127252485779481701078452759513943692466279038851599018511, 330098489762871879773681019559732262466172018773272582308614672671671001199307865518506835519360693927579848132122, 97272570979206528424127336981516817168566955222510512261839537633559389914877185855268875504270285494647179225542, 74718841026645027941391238796126141775030441881552798010185595153873780524478674202965665888738730228577064111032, 59009205910055868684561742529451214311094377006520731342399475542159755492342086349692903126315766192176134558364, 147954106872023713951463145691216475084430006306060416221364896834795769425749212897622105818492094458111589403860, 555992830271936179812799550002813412539390844307434015514327261249472823762801208645240806724751727789206958497458, 459223438688559571249116685914649450095540121668933258507609746609794374539448063463326591749261191192370815662117, 571393209200912648822312183637054598815269397678580613768957089116765483865121162495918269935152288322187647411253, 177286186824084038346767370297094817293812392957721642873053028629715330336525966361030541938870465423944241324109, 587491267113142201933590855412985429253948652679543672927232780837039223665539177593879438262959884768626979925026, 121073719992748558849282996502703446279240313956823650619682240860630373634948798695523514085879310433388769297911, 326992821821879354165502695961028240084978294787383957718963930070776372845305415470613976088436935751047043512627, 55897462658973985554837453480984923331777372313619418297379632868358904708526448610515770876401568010074036247, 474281517111080897542557845865286041097457650249727914745876496139882777461227076272058949306156001543709356614827, 40880447006931568560802817837347288973549001731224760995212446282117046967004745589464560120352241602331262757637, 199377582253379978414081552664345738394226248383486423477706857549702059554694037264958719644482986837756496613246, 67583806809325529684782118654476643411516600285151896093983454855502714712133346956141976654071062935812737453191, 452546341988439193982297214011678766258506490290911066090290647614068455151806621409756646430532117713333419814200, 63154079944843452528208874183624055953361990336542165468695871390964383215223885775202331596927466794955939855669, 334551033942583568474606741839213957101383590286251155186668543235920975897931743928357631453433934808796703330473, 437000125133660712403788025992205090698484430907657894066272071296035483375078474260228687865444802416063967634962, 79996507523856267942889507576300340014719316733731500178081582238768493408405645914333660158893963260211116177267, 136957270824318341027124989034235585855646981093281453761145461440890955503793684517186875995202144027265329969201, 280204753198588906275980318398478729285287961542920285529979812275266316580102545873587416433404212703776245726478, 537734235993878341769434982550042490365981751251428660237179942734374485415922424357453321846937022328664895920607, 498357256878949571854248804622370932859926894994690120526235824883083753765132401863605500892090016764206939698756, 593183658694608014094449104249771865876595121367209656250471158771632486392533730913932393504513988512194994235126, 471525047958971655208534107052287853913949987926476676197514310320411235020283503103705707957701802098089852040455, 515550195522086342769232739520750768345601850976320014312405876943691700378141377151414091085616391824613041356222, 229784654767967355149909497709811119368560654037206880944035229827691011815016913131119422451043820980926353941725, 217169654015051285238559403576147518221573574303291047729813710960725792892550445720464605476174663800328177597453, 445865555254101127829958642102675927687168710569707725467286103803938348116926832834254624089519482737855028080263, 83946997792088073746354410376458121354546477090285151121896293987266118404260723878401677521317330022928683440101, 472119354862263268431251633432424976904384210603399093568806291862332048310282050100842204125396472101319620313029, 46843467515693389983627938872598324284244171067988563260495985345821466093790361374194115630948136965603015643581, 277302589126799360982750111603442360555051934636756171066424884732490616874962892980005637968336486277371298105284, 37796860324947087933757452089444569583341754367174335457777874936449439863762482510080776848131952814291888228252, 329201662631483519275850208043421059140347420462580260818216051307977255139454956805683010032538225008290753339066, 410958260744814455637908317160979333881545314073457621559204623145344687279791103290567233048673594441768330391568, 391184069150039601440639067557184862816991051523817132396666190555512106382919904848895224325098711230221328168893, 341778180155955688649827271577690269253924367106359453768062062983194302766144996692233530585116870343939549344048, 482885184891891026832543019680624112333051960746415331234199075553060933581630480706330420552017650892318225421994, 227417029879602291913898154454350465334192275455983368980997243946371067766121862949125088496933933053493304375082, 131891059077173823480681683274809296700667012054595015489329798567668841455882278540434006611778254351469315756836, 103977685400575936876007245351080422734569291709540152622222483086840011211808484758839889045266405362833100572217, 430039690420862864710328860317916251552162738538460131045295388990486621940999260820629946807283129550503791042360, 336054039341779369078755981618338727567421739252984379060088264565052065080902800664605952509539644185937023210384, 414650487301520195860820485747902373712957920758077572646321108690388934071745453432265035539090489903222596288408, 589576193361941267176015154197092338077060428665767302320550323024382985851379047593411265195718688560873123744185, 218382333622730104159935425552756841820388948639519923842495333910150980936866251625988964615764772159578862214025, 2542356543181698813075957157401385706512468063673241076844194782908937880847391489213422972872487843717747974071, 19012712934576590810330358701965194246607393288484627129050567402003333386833300009773236871643918870071025370112, 261459449945270346696260426170010104493420330959761424072408598127181246567262293489464049721489266230568086023687, 393057872763078249377870634042993942252544393136978340205701555086856991894130814830449765311294161681995357980571, 31706670785655144489258744219717253455873175486088498446357251628824725653898017817866303775262383346847940227722, 352845629675989592022318947558037109666715372268243939061740352176833050420783754677666411876876865226448815643420, 579523499570692157776642365278787278074363193157128877724940050501652213832135926670258239249988403301949338255538, 534781322034571849183222718240938369181782069830117215874801137890227720544463940037268498986061166881241864175911, 293947547828174245724554745263997068016996177889470503383528004805559670712802640725469343616840367100443153534752, 20256488447976344493484944853334005566670073013412177398480406734598723283264289836587474269370253077015786359305, 475307340957345844876811923970449788514706891727480716267956523131203845997503382023500463149439850432076379159007, 9532193777031501443256432870520743234491840911054244783623102207162388499144070592024440812057106927678514406207, 30376455906399256126534181227692885553266283699913099449205248506625206632827693466133644861846223565145288661633, 310323302397755654510284518631138079981439265632852684852876254116989091445393487579911757256043570018377230904180, 407387187512823516321154849212634322952876110252179375736935664859854509488826142049903683991617538259494461983206, 211765773488300500716796064525502573590145731868562963063378748592341237756767589777342751660513980880169703658019, 118119996850569812443799306306875048213209686043987665925365129711742300844060014347898233682054000714610165352429, 456288037921986114882644161559494182818651772335241262800783776696209877706906644069180867207555069937013686421247, 321798425169971169912343295962697085577508076571119888196289113181080013814133443673221049860354996979915353284172, 324976521789232911848337505841284978746361536915903971011255451438673522500730537005137182463678372897314198988595, 395621759076694189110473461483468243816716472466025836871653502259071450104902960119128530517955567830675053452079, 539300517585750216948117617165146582589224695990488749904551961039061424290129525221984586819908097960720708938354, 29279302128607422250205549520059282069518559284219582605487413142781822276106373289432262133635053599391124926385, 554047387889265384869858916477442181952403597250555948392949469296673941793381852004501421929101000148453680659392, 117780825424837288494479009381221759361151487239443821133102414888864152904732196195473813006762420646998382258677, 513764579681988270425418630365712613073908798769959690739998792846173650211508078458011456784363312999085649615413, 421686906289957894155024887354760839265000904451245772175308131137467275202489561700021659858819873604538650489994, 420037832423259525388141394520857134457021929872555809167052539034540217718781279113965175987358081438109891771580, 36451605745112040602804954235939462081346791770310181663631699054048414835838956409055640948581948016033003511333, 65866443469866248828119099994518897685990064406903627156894902667947376070679854260383038634727146436274230980496, 27676413701492447763964945205769602759768347623741189980278225943728587187940271050634054217590942659542302722334, 500312789935788689187812810985806111797362028998353677843819125485045576943472901976055579663665267905809820905862, 520064354401353505774803720281331074080600746212325401527048530022713769008774050816490541356142354757805595273068, 495854656037423684061417113244964481431602915324717605570975073575414392233479237472936965636133612283412033946051, 91739870792230359210043046401786959190045929124141709653873699398574077579395785555200462734509728806350612588545, 484531754577892922131892661653620989224382080321025512011181426678442547912964573223048519566085582623517825865418, 112714684344084391078866980839255594355187885339701715768009153551270432322826715969989728340963213693095849427668, 404429204723786534299525333122163342588586991421902466839808468487493896330979873416105908841447535426923681220957, 92404742424217640040375362532444172359091402942418950195520660310216430170054358290537973281349284862065214755739, 224043393969043013532511880223075809120842856165608086692928112430171548569493398551019081676395857489451126409940, 4305919427803364191555497499680058924116536587126751817219863902878291078989381194676206640960307162723876513248]
Ciphertext = 45690752833299626276860565848930183308016946786375859806294346622745082512511847698896914843023558560509878243217521



N = 10

M = []
for i in range(272):
    row = [0 for _ in range(272 + 1)]
    row[i] = 1
    row[-1] = N*PublicKey[i]
    M.append(row)
M.append([1 / 2 for _ in range(272)] + [N * Ciphertext])
M = matrix(M)
L = M.LLL()

for i in L:
    if set(i) == {0, -1/2, 1/2}:
        found = i
        break


flag = ""
for i in found:
    if i == -1/2:
        flag += "1"
    else:
        flag += "0"
print(flag[:-1][::-1])
```

**Flag: crypto{my_kn4ps4ck_1s_l1ghtw31ght}**


## Knapsack Low-density Multiple Subset Sum Problem

Cũng giống như trên, nhưng mà giờ là sẽ nhiều hơn 1 đích đến. 

Này sẽ giải quyết vấn đề cho câu hỏi recover $(e_1,e_2,...,e_n) \in \{0,1\}^n$ từ các trọng số $a_{ji} (1 \leq j \leq k, 1 \leq i \leq n)$ sao cho được các đích đến $s_1,s_2,...,s_k$.

$$\displaystyle\sum_{i=1}^{n} e_i*a_{1, i} \ = s_1$$
$$\displaystyle\sum_{i=1}^{n} e_i*a_{2, i} \ = s_2$$
$$\cdot \cdot \cdot \cdot \cdot \cdot \cdot$$
$$\displaystyle\sum_{i=1}^{n} e_i*a_{k, i} \ = s_k$$

Và mật độ của tổng nhiều tập con được xác định bởi công thức

$$d = \frac{n}{k.log_2max(a_{j, i})}$$


Giờ mình sẽ cho bạn một ví dụ để hiểu thêm về cái này.

Ta có 2 giá trị đích và 2 mảng giá trị trọng số như sau

```python
[3,7,19,43,89,195],  260
#3 + 19+43+   195 =  260

[4,12,16,36,75,162]  218
# 4,  16+36   +162 = 218
```

Từ ví dụ này, ta có thể thấy được rằng chúng có 1 vector cơ sở đó là $(1,0,1,1,0,1)$. Giờ ta sẽ sử dụng ma trận và LLL để có thể recover vector này với mật độ $d  \leq 0.9408$.

$$
\begin{pmatrix}
  1	&	&	&	 &0	 &Na_{1,1}	&Na_{2,1}	&\cdots	&Na_{k,1}	\\
  	&1	&	&	 &0	 &Na_{1,2}	&Na_{2,2}	&\cdots	&Na_{k,2}	\\
  	&	&\ddots	&	 &\vdots &\vdots	&\vdots	&\ddots	&\vdots	\\
  	&	&	&1	 &0	 &Na_{1,n}	&Na_{2,n}	&\cdots	&Na_{k,n}	\\
\frac12	&\frac12&\cdots	&\frac12 &\frac12&Ns_1	&Ns_2	&\cdots	&Ns_k		
 \end{pmatrix}
$$

với giá trị $N \geq \sqrt{\frac{n+1}{4}}$.

Sau khi LLL ma trận này, ta sẽ thu được vector ngắn nhất có dạng $\mathbf{\bar{e}} = (e_1 - \frac{1}{2}, ..., e_n - \frac{1}{2}, -\frac{1}{2}, 0,...,0)$. Đó chính là vector ta cần tìm.

Giờ mình sẽ code sage thử

```sage
M =[
     [1  ,   0,   0,   0,   0,  0,   0, 5*3  , 5*4  ],
     [0  ,   1,   0,   0,   0,  0,   0, 5*7  , 5*12 ],
     [0  ,   0,   1,   0,   0,  0,   0, 5*19 , 5*16 ],
     [0  ,   0,   0,   1,   0,  0,   0, 5*43 , 5*36 ],
     [0  ,   0,   0,   0,   1,  0,   0, 5*89 , 5*75],
     [0  ,   0,   0,   0,   0,  1,   0, 5*195, 5*162],
     [1/2, 1/2, 1/2, 1/2, 1/2,1/2, 1/2, 5*260, 5*218]
]
# [3,7,19,43,89,195],  260
#  3 + 19 + 43+ 195 =  260

# [4,12,16,36,75,162]  218
#  4,   16+36   +162 = 218
M = matrix(M)
print(M.LLL())
```

```sage
[-1/2  1/2 -1/2 -1/2  1/2 -1/2  1/2    0    0]
[  -3    0   -1    2   -1    1   -1    0    0]
[  -2   -1    1    2    3   -1   -1    0    0]
[ 3/2  1/2  1/2 -3/2 -3/2  1/2  1/2   -5    0]
[-1/2 -1/2  1/2 -3/2  1/2  1/2 -1/2    0   -5]
[ 3/2 -5/2 -5/2 -7/2  3/2  5/2 -5/2    0    0]
[-7/2  3/2 11/2 -7/2 -3/2  1/2  1/2    0    0]
```

Ta nhận thấy rằng vector đầu tiên chính là vector $(1,0,1,1,0,1)$ cần tìm, đôi khi phải đổi lại dấu để có được giá trị chính xác nhất.

## Modular Subset Sum Problem

Dạng này thì sẽ có một dãy trọng số nguyên dương $a_1,a_2,...,a_n$, số đích là $s$ và modulo $M$, tìm $e_1,e_2,...,e_n$ sao cho 

$$\displaystyle\sum_{i=1}^{n} e_i*a_{i} \ = s \ (mod \ M)$$

Bài này thì mình không thấy tài liệu nào sử dụng knapsack, cũng không thấy sử dụng ma trận để tìm, nhưng mình tìm được quả code python khá hay.

```python
import random

def ModularSubsetSum(W, m):
    p = 1234567891
    r = random.randint(0,p)
    powr = [1]
    for i in range(2*m):
        powr.append((powr[-1] * r) % p)
    tree = [0] * (2*m)
    def read(i):
        if i<=0: return 0
        return tree[i-1] + read(i-(i&-i))
    def update(i, v):
        while i < len(tree):
            tree[i] += v
            i += (i+1)&-(i+1)

    def FindNewSums(a,b,w):
        h1 = (read(b)-read(a))*powr[m-w] % p 
        h2 = (read(b+m-w)-read(a+m-w)) % p
        if h1 == h2: return []
        if b == a+1:
            if sums[a] is None: return [a]
            return []
        return FindNewSums(a,(a+b)//2,w) + FindNewSums((a+b)//2,b,w)
    def AddNewSum(s, w):
        sums[s] = w
        update(s,powr[s]), update(s+m,powr[s+m])
    sums = [None] * m
    AddNewSum(0,0)
    for w in W:
        for s in FindNewSums(0,m,w):
            AddNewSum(s,w)
    return sums

def RecoverSubset(sums, s):
    if sums[s] is None: return None
    if s <= 0: return []
    return RecoverSubset(sums, (s-sums[s]) % len(sums)) + [ sums[s] ]

sum = (ModularSubsetSum([2,3,5,7,11], 13))
print(RecoverSubset(sum,12))
```

Với các trọng số là $2,3,5,7,11$ và  modulo $m = 13$, ta có thể tìm được dãy con có giá trị đích là $s = 12$. Bạn cũng có thể thay giá trị khác vào để test thử.


## Knapsack Multiple Modular Subset Sum Problem


Giờ là kết hợp giữa 2 cái trên. Cho 1 giá trị $q$ là một số nguyên lớn hơn $\sqrt{\frac{n+1}{4}}$, và cho các trọng số $a_{ji} (1 \leq j \leq k, 1 \leq i \leq n)$ là các số nguyên ngẫu nhiên giữa 1 và q - 1. Cho vector $\bar{e} = (e_1,e_2,...,e_n)$ thỏa mãn

$$\displaystyle\sum_{i=1}^{n} e_i*a_{1, i} \ = s_1 \mod q$$
$$\displaystyle\sum_{i=1}^{n} e_i*a_{2, i} \ = s_2 \mod q$$
$$\cdot \cdot \cdot \cdot \cdot \cdot \cdot$$
$$\displaystyle\sum_{i=1}^{n} e_i*a_{k, i} \ = s_k \mod q$$

Thì nếu mật độ $d < 0.9408$ thì ta sẽ có thể tìm được $\bar{e}$ bằng cách sử dụng lattice. Ma trận sẽ khá giống phần ban nãy tìm hiểu, được build như sau:

$$
\begin{pmatrix}  1	&	&	&	 &0	 &Na_{1,1}	&Na_{2,1}	&\cdots	&Na_{k,1}	\\  	&1	&	&	 &0	 &Na_{1,2}	&Na_{2,2}	&\cdots	&Na_{k,2}	\\  	&	&\ddots	&	 &\vdots &\vdots	&\vdots	&\ddots	&\vdots	\\  	&	&	&1	 &0	 &Na_{1,n}	&Na_{2,n}	&\cdots	&Na_{k,n}	\\  	&	&	&	 &	 &NM	&	&	&	\\  	&	&	&	 &	 &	&NM	&	&	\\  	&	&	&	 &	 &	&	&\ddots	&	\\  	&	&	&	 &	 &	&	&	&NM	\\\frac12	&\frac12&\cdots	&\frac12 &\frac12&Ns_1	&Ns_2	&\cdots	&Ns_k		 \end{pmatrix}
$$

Cũng như Multiple, ta cũng sẽ thu được vector ngắn nhất $\bar{e}$

Ta có ví dụ sau
```python
[3,7,19,43,89,195],  260
 3 + 19 + 43+ 195 =  60 % 200
 q = 200
[4,12,16,36,75,162]  218
 4,   16+36   +162 = 18 % 200
```

Giờ mính sẽ code sage, build ma trận như trên.

```sage
M =[
     [1  ,   0,   0,   0,   0,  0,   0, 5*3  , 5*4  ],
     [0  ,   1,   0,   0,   0,  0,   0, 5*7  , 5*12 ],
     [0  ,   0,   1,   0,   0,  0,   0, 5*19 , 5*16 ],
     [0  ,   0,   0,   1,   0,  0,   0, 5*43 , 5*36 ],
     [0  ,   0,   0,   0,   1,  0,   0, 5*89 , 5*75],
     [0  ,   0,   0,   0,   0,  1,   0, 5*195, 5*162],
     [0  ,   0,   0,   0,   0,  0,   0, 5*200, 0    ],
     [0  ,   0,   0,   0,   0,  0,   0,     0, 5*200],
     [1/2, 1/2, 1/2, 1/2, 1/2,1/2, 1/2, 5*60, 5*18]
]
# [3,7,19,43,89,195],  260
#  3 + 19 + 43+ 195 =  60 % 200
#  q = 200
# [4,12,16,36,75,162]  218
#  4,   16+36   +162 = 18 % 200
M = matrix(M)
print(M.LLL())
```

```python
[-1/2  1/2 -1/2 -1/2  1/2 -1/2  1/2    0    0]
[  -3    0   -1    2   -1    1   -1    0    0]
[  -2   -1    1    2    3   -1   -1    0    0]
[  -1    3    0    0    1    3   -3    0    0]
[  -2    2    2    0    0   -2   -4    0    0]
[ 3/2  1/2  1/2 -3/2 -3/2  1/2  1/2   -5    0]
[-1/2 -1/2  1/2 -3/2  1/2  1/2 -1/2    0   -5]
[ 3/2 -5/2 -5/2 -7/2  3/2  5/2 -5/2    0    0]
[  -3   -2    5   -1    1    2    3    0    0]
```

Ta thấy vector đầu tiên chính là vector cần tìm.


## Hidden Number Problem
Trong Hidden Number Problem, sẽ có 1 số bí mật $\alpha$ và một số modulo public là $n$. Chọn các số random $0 < t_i < n$, tính toán $s_i= t_i.\alpha \mod n$. Và sẽ nhận được những bit quan trọng nhất của $s_i$ cùng với giá trị $t_i$. Ta có thể viết lại được là $a_i + k_i = t_i.\alpha \mod n$ với $k_i < 2^l$ với $l \in {Z}$. Từ đó, ta sẽ được các cặp $( a_i,t_i)$.


Việc triển khai MSB (những bit quan trọng nhất) có thể được tìm bằng code sage này.
```sage
p = next_prime(2^16)

n = ceil(log(p, 2))

# k - The number of significant bits revealed by the oracle.
# Using parameters from Thereom 1.
k = ceil(sqrt(n)) + ceil(log(n, 2))

def msb(query):
    """Returns the MSB of query based on the global paramters p, k.
    """
    while True:
        z = randint(1, p-1)
        answer = abs(query - z)
        if answer < p / 2^(k+1):
            break
    return z

def create_oracle(alpha):
    """Returns a randomized MSB oracle using the specified alpha value.
    """
    alpha = alpha
    def oracle():
        random_t = randint(1, p-1)
        return random_t, msb((alpha * random_t) % p)
    return oracle

alpha = 23223

oracle = create_oracle(alpha)
print(oracle())
```

Để giải quyết vấn đề này, ta có thể sử dụng ma trận của Boneh and Venkatesan 
$$
\begin{pmatrix}n	&	&	&	&	\\	&n	&	&	&	\\	&	&\ddots	&	&	\\	&	&	&n	&	\\t_1	&t_2	&\cdots	&t_m	& 1/n	 \end{pmatrix}
$$

Mục tiêu là vector $(a_0,...a_{m-1},0)$ và vector cơ sở $(t_0.\alpha\mod n,...,t_{m-1}.\alpha \mod n, \frac{\alpha}{n})$.

Ta có thể sử dụng **Babais Nearest Plane Algorithm** để có thể giải được vấn đề này. 

```sage
# Some parameters of the game, chosen for simplicity.

# p - A prime number for our field.
p = next_prime(2^16)

# n - The number of bits in `p`.
n = ceil(log(p, 2))

# k - The number of significant bits revealed by the oracle.
# Using parameters from Thereom 1.
k = ceil(sqrt(n)) + ceil(log(n, 2))

def msb(query):
    """Returns the MSB of query based on the global paramters p, k.
    """
    while True:
        z = randint(1, p-1)
        answer = abs(query - z)
        if answer < p / 2^(k+1):
            break
    return z

def create_oracle(alpha):
    """Returns a randomized MSB oracle using the specified alpha value.
    """
    alpha = alpha
    def oracle():
        random_t = randint(1, p-1)
        return random_t, msb((alpha * random_t) % p)
    return oracle


# d - The number of oracle queries.
# Using parameters from Thereom 1.
d = 2 * ceil(sqrt(n))

def build_basis(oracle_inputs):
    """Returns a basis using the HNP game parameters and inputs to our oracle
    """
    basis_vectors = []
    for i in range(d):
        p_vector = [0] * (d+1)
        p_vector[i] = p
        basis_vectors.append(p_vector)
    basis_vectors.append(list(oracle_inputs) + [QQ(1)/QQ(p)])
    return Matrix(QQ, basis_vectors)

def approximate_closest_vector(basis, v):
    """Returns an approximate CVP solution using Babai's nearest plane algorithm.
    """
    BL = basis.LLL()
    print(BL)
    G, _ = BL.gram_schmidt()
    _, n = BL.dimensions()
    print(G, BL.LLL())
    small = vector(ZZ, v)
    for i in reversed(range(n)):
        c = QQ(small * G[i]) / QQ(G[i] * G[i])
        c = c.round()
        small -= BL[i] * c
        print(small)
    return (v - small).coefficients()

# Hidden alpha scalar
alpha = randint(1, p-1)

# Create a MSB oracle using the secret alpha scalar
oracle = create_oracle(alpha)

# Using terminology from the paper: inputs = `t` values, answers = `a` values
inputs, answers = zip(*[ oracle() for _ in range(d) ])

# Build a basis using our oracle inputs
lattice = build_basis(inputs)
print("Solving CVP using lattice with basis:\n%s\n" % str(lattice))

# The non-lattice vector based on the oracle's answers
print(inputs)
u = vector(ZZ, list(answers) + [0])
print("Vector of MSB oracle answers:\n%s\n" % str(u))

# Solve an approximate CVP to find a vector v which is likely to reveal alpha.
v = approximate_closest_vector(lattice, u)
print("Closest lattice vector:\n%s\n" % str(v))

# Confirm the recovered value of alpha matches the expected value of alpha.
recovered_alpha = (v[-1] * p) % p
assert recovered_alpha == alpha
print("Recovered alpha! Alpha is %d" % recovered_alpha)
```

```
Solving CVP using lattice with basis:
[  65537       0       0       0       0       0       0       0       0       0       0]
[      0   65537       0       0       0       0       0       0       0       0       0]
[      0       0   65537       0       0       0       0       0       0       0       0]
[      0       0       0   65537       0       0       0       0       0       0       0]
[      0       0       0       0   65537       0       0       0       0       0       0]
[      0       0       0       0       0   65537       0       0       0       0       0]
[      0       0       0       0       0       0   65537       0       0       0       0]
[      0       0       0       0       0       0       0   65537       0       0       0]
[      0       0       0       0       0       0       0       0   65537       0       0]
[      0       0       0       0       0       0       0       0       0   65537       0]
[  31181   61379   53230   21935    8582   15108   60375   17258   54605   36393 1/65537]

(31181, 61379, 53230, 21935, 8582, 15108, 60375, 17258, 54605, 36393)
Vector of MSB oracle answers:
(50494, 11104, 43501, 31498, 40928, 56575, 48978, 55830, 19406, 3011, 0)

[           0            0            0            0            0            0            0            0            0            0            1]
[         155        -4548        11316        -6270         6077        -7874        -7443        -9116         1377         6045  24873/65537]
[        8509         6558         3050          395        16916          287         4075       -11237        -4320         4166  18345/65537]
[        -213         1176       -11745         4388       -17653        -2287        -1188        -8191        -4852        -8307 -18536/65537]
[        6518         8320        -1507        -9972       -12097         9678         4970        -5342         -444        -7946  15539/65537]
[       11928         -319         2350        16420         5513        -3002          991          -63         9564         6433 -10576/65537]
[      -13343         1670         6393        -3577       -14480         9347        -7037        -9737        -7336         3919 -32564/65537]
[       -5463        -1222        17220         -993        -7849         2265        -2778          375         -754       -16446   3657/65537]
[       -3619         4289        -7559         6864         9904        13449        -6339       -12096         1252       -10067   1055/65537]
[        4774         4103        -5367         3495         3668        -6586       -19526         7590       -10018       -10425  32074/65537]
[         236       -17918        -7294         3138        10944        14226        -3299        -4155       -15239         9204  17153/65537]
[                       0                        0                        0                        0                        0                        0                        0                        0                        0                        0                        1]
[                     155                    -4548                    11316                    -6270                     6077                    -7874                    -7443                    -9116                     1377                     6045                        0]
[ 3917383275181/463940749  3931248348438/463940749  -796240863982/463940749  1408477621895/463940749  6660514824080/463940749  1671809744411/463940749  3344995569211/463940749 -3431944162481/463940749 -2273303677284/463940749   751523395994/463940749                        0]
[   136322268497/54838829     86002763286/54838829   -367737216643/54838829    123026777307/54838829   -559441920212/54838829   -276669164164/54838829   -143335579478/54838829   -821348612978/54838829   -312352422239/54838829   -264716788252/54838829                        0]
[     31173132809/6065536      16743065075/3032768      34760103893/6065536     -81651565245/6065536      -9329126413/1516384      13051234791/1516384       8718845869/3032768      -6689033905/3032768      16405811673/6065536      -5573200943/1516384                        0]
[       6931389731/588643           -8061051/53513        2317912616/588643        5619535602/588643       -2779030948/588643        -265686998/588643        -102499868/588643        -204672051/588643        6843045855/588643        1699243336/588643                        0]
[        -108463735/14097            15991028/4699           85001489/14097            33358333/4699          -58131319/14097          154667320/14097          -36045350/14097           -20447544/4699           -16580861/4699          117901063/14097                        0]
[            -1376277/661              196611/1322            15794417/1322             9109643/1322             2424869/1322              -393222/661               458759/661              458759/1322             -1966110/661           -20644155/1322                        0]
[             -851981/278              -589833/278              -917518/139                        0               917518/139              1179666/139             -1376277/139             -1376277/278              2687017/278              -917518/139                        0]
[                 65537/8                  65537/8                        0                        0                        0                        0                 -65537/4                  65537/8                 -65537/8                        0                        0]
[                 65537/7                -131074/7                        0                        0                        0                  65537/7                        0                        0                 -65537/7                        0                        0] [           0            0            0            0            0            0            0            0            0            0            1]
[         155        -4548        11316        -6270         6077        -7874        -7443        -9116         1377         6045  24873/65537]
[        8509         6558         3050          395        16916          287         4075       -11237        -4320         4166  18345/65537]
[        -213         1176       -11745         4388       -17653        -2287        -1188        -8191        -4852        -8307 -18536/65537]
[        6518         8320        -1507        -9972       -12097         9678         4970        -5342         -444        -7946  15539/65537]
[       11928         -319         2350        16420         5513        -3002          991          -63         9564         6433 -10576/65537]
[      -13343         1670         6393        -3577       -14480         9347        -7037        -9737        -7336         3919 -32564/65537]
[       -5463        -1222        17220         -993        -7849         2265        -2778          375         -754       -16446   3657/65537]
[       -3619         4289        -7559         6864         9904        13449        -6339       -12096         1252       -10067   1055/65537]
[        4774         4103        -5367         3495         3668        -6586       -19526         7590       -10018       -10425  32074/65537]
[         236       -17918        -7294         3138        10944        14226        -3299        -4155       -15239         9204  17153/65537]
(50258, 29022, 50795, 28360, 29984, 42349, 52277, 59985, 34645, -6193, -17153/65537)
(50258, 29022, 50795, 28360, 29984, 42349, 52277, 59985, 34645, -6193, -17153/65537)
(46639, 33311, 43236, 35224, 39888, 55798, 45938, 47889, 35897, -16260, -16098/65537)
(57565, 35755, 8796, 37210, 55586, 51268, 51494, 47139, 37405, 16632, -23412/65537)
(57565, 35755, 8796, 37210, 55586, 51268, 51494, 47139, 37405, 16632, -23412/65537)
(21781, 36712, 1746, -12050, 39047, 60274, 48521, 47328, 8713, -2667, 8316/65537)
(8745, 20072, 4760, 7894, 63241, 40918, 38581, 58012, 9601, 13225, -22762/65537)
(7893, 24776, -42220, 25446, -7371, 31770, 33829, 25248, -9807, -20003, -96906/65537)
(-616, 18218, -45270, 25051, -24287, 31483, 29754, 36485, -5487, -24169, -115251/65537)
(4, 26, -6, -29, 21, -13, -18, 21, 21, 11, -15759/65537)
(4, 26, -6, -29, 21, -13, -18, 21, 21, 11, -15759/65537)
Closest lattice vector:
[50490, 11078, 43507, 31527, 40907, 56588, 48996, 55809, 19385, 3000, 15759/65537]

Recovered alpha! Alpha is 15759
```

Nhưng mà hầu hết sử dụng ma trận của Kannan như sau

$$
\begin{pmatrix}n	&	&	&	&	&	\\	&n	&	&	&	&	\\	&	&\ddots	&	&	&	\\	&	&	&n	&	&	\\t_1	&t_2	&\cdots	&t_m	& B/n	\\a_1	&a_2	&\cdots	&a_m	&		& B \end{pmatrix}
$$

Thắc mắc $B$ là giá trị gì đúng không, ban nãy mình có viết HNP có thể viết bằng $a_i + k_i = t_i.\alpha \mod n$ với $k_i < 2^l$ với $l \in {Z}$, thì giá trị $B = 2^l$.

Lattice này chứa vector $(k_0,k_1,...,k_{m-1}, \frac{B.\alpha}{n},-B).$ Giờ mình sẽ lấy ví dụ nha, vẫn lấy thuật toán như trên nhưng mà sẽ dụng ma trận khác. Nhưng trước hết, ta cần phải tìm giá trị B đã.

```python
def msb(query):
    """Returns the MSB of query based on the global paramters p, k.
    """
    while True:
        z = randint(1, p-1)
        answer = abs(query - z)
        if answer < p / 2^(k+1):
            break
    return z
```
Vì giá trị answer rất nhỏ, bạn tính ra thì chỉ tầm dưới 50 thuiii, nên mình sẽ lấy $B = 100$ nha.

```python
p = next_prime(2^16)

# n - The number of bits in `p`.
n = ceil(log(p, 2))

# k - The number of significant bits revealed by the oracle.
# Using parameters from Thereom 1.
k = ceil(sqrt(n)) + ceil(log(n, 2))

def msb(query):
    """Returns the MSB of query based on the global paramters p, k.
    """
    while True:
        z = randint(1, p-1)
        answer = abs(query - z)
        if answer < p / 2^(k+1):
            print(answer)
            break
    return z

def create_oracle(alpha):
    """Returns a randomized MSB oracle using the specified alpha value.
    """
    alpha = alpha
    def oracle():
        random_t = randint(1, p-1)
        return random_t, msb((alpha * random_t) % p)
    return oracle

def build_basis(oracle_inputs, answers, bound):
    """Returns a basis using the HNP game parameters and inputs to our oracle
    """
    basis_vectors = []
    for i in range(d):
        p_vector = [0] * (d+2)
        p_vector[i] = p
        basis_vectors.append(p_vector)
    basis_vectors.append(list(oracle_inputs) + [QQ(bound)/QQ(p)] + [0])
    basis_vectors.append(list(answers)  + [0] + [QQ(bound)])
    return Matrix(QQ, basis_vectors)
    # return basis_vectors

d = 2 * ceil(sqrt(n))

alpha = randint(1, p-1)

# Create a MSB oracle using the secret alpha scalar
oracle = create_oracle(alpha)

# Using terminology from the paper: inputs = `t` values, answers = `a` values
inputs, answers = zip(*[ oracle() for _ in range(d) ])

print("alpha is:",alpha)
bound = 100

M = (build_basis(inputs,answers, bound))
print(M.LLL())
```


```sage
11
24
31
3
20
15
13
29
30
12
alpha is: 3620
[             0              0              0              0              0              0              0              0              0              0           -100              0]
[           -11            -24            -31             -3            -20            -15             13            -29             30             12  -362000/65537            100]
[           502           4591           6563          -2853            -73          -3011           4175          -2950            990         -13111   872500/65537           2500]
[        -15865           2802           -846           2441          -4372           2224           2329          -1075         -12855         -10243 -1697200/65537           2700]
[        -17186          -3598           2433          -6742           5944           3303          11588          -8709           1792          -5170 -2085400/65537          -4500]
[          1994          18857          -5525           8009          -3809          -4071          -2822            926            544           8481  -796700/65537           1300]
[          9514           5381           4231         -14756           3396          10301          -5893           5749          -1174          -5866 -2724500/65537           8900]
[         -4269          -4536          -6434          12486          -8845           3016         -11589          -2188           5882         -10194 -1638900/65537          -4200]
[          2831           1900         -17206          -5266          14471           2200           6216           2735           7989          -1796 -2412400/65537          -3700]
[          6310           8674          -7348           3248          -6737          13222          11411           6340           3615          -5612 -1253700/65537           1200]
[          4930           2225          16912           1081          15879           4217            831          11965           4571           6138  2632200/65537          11400]
[        -10582           2337          -8177          -9985         -16531          -1016           2998          12659           1349          -3177 -2462600/65537          -3600]
```

Ta thấy rằng dòng thứ 2 sẽ là vector có dạng $(k_0,k_1,...,k_{m-1}, \frac{B.\alpha}{n},-B).$ Nếu mà là $B$ thì ta chỉ cần đổi dầu thôi. Do đó ta tìm được giá trị $\alpha$ cần tìm.

```python
alpha = M.LLL()[1][-2]
alpha = -alpha*p//bound % p
print(alpha)
```





## Resources
https://hackmd.io/@nomorecaffeine/r1xstVfxC
https://eprint.iacr.org/2011/525.pdf
https://kel.bz/post/hnp/
https://eprint.iacr.org/2020/1540.pdf