# Equations
“Phương trình” có nghĩa là “tuyên bố rằng giá trị của hai biểu thức toán học bằng nhau (được biểu thị bằng dấu =)”.
Các phương trình có thể trivial (không có biến chưa biết liên quan):
```
0 = 0
1 = 1
1 + 1 = 2
1,9 = 2
```
... hoặc với các biến (còn gọi là vô định) dẫn đến tập nghiệm hoặc một giải pháp hoặc không có giải pháp (không thể giải quyết được):
```
x + x = 10
x + y = 10
x + y = z
x1 + x2 + x3 + · · · + x10 = z
```
Trong SageMath chúng ta có thể dễ dàng khởi tạo các biến:
```
sage: x = var(’x’)
```
Bây giờ, chúng ta có thể xây dựng phương trình, ví dụ như:
```
sage: leq1 = x + 2*x**2 + x**3
```
Ta giải phương trình leq1=100 bằng cách:
```
sage: eq_sol= solve(leq1==100, x)
```
Khai báo biến x trong domain integer number:
```
sage: x = var('x', domain=ZZ)
```
ZZ có nghĩa là miền của số nguyên Z. Số nguyên có thể được giới hạn hơn nữa ở loại Boolean (true hoặc false) hoặc số nguyên theo modulo n (IntegerModRing(n) hoặc GF(n), nếu n là số nguyên tố)
## Challenge 1
We found this strange list of (independent) equations. Can you find the hidden message? Consider the found values for the variable of each equation as the ascii value of a character. The correct ascii values build the correct word in the same order as the 8 equations appear here.
Mỉnh giải bài ấy như sau:
```
x=var('x', domain=ZZ)
f1=x**4 - 150*x**3 + 4389*x**2 - 43000*x + 131100
f2=x**10 - 177*x**9 + 9143*x**8 - 228909*x**7 + 3264597*x**6 - 28298835*x**5 +152170893*x**4 - 502513551*x**3 + 974729862*x**2 - 995312448*x**1 + 396179424
f3=x**10 - 196*x**9 + 12537*x**8 - 397764*x**7 + 7189071*x**6 - 77789724*x**5 +506733203*x**4 - 1941451916*x**3 + 4165661988*x**2 - 4501832400*x + 1841875200
f4=x**5 - 153*x**4 + 5317*x**3 - 77199*x**2 + 510274*x - 1269840
f5=x**8 - 194*x**7 + 11791*x**6 - 352754*x**5 + 6011644*x**4 - 61295576*x**3 + 370272864*x**2 - 1222050816*x + 1696757760
f6=x**6 - 169*x**5 + 7702*x**4 - 153082*x**3 + 1477573*x**2 - 6672349*x + 11042724
f7=x**8 - 202*x**7 + 12936*x**6 - 406082*x**5 + 7170059*x**4 -74124708*x**3 + 439747164*x**2 - 1365683328*x + 1701311040
f8=x**9 - 206*x**8 + 13919*x**7 - 467924*x**6 + 8975099*x**5 - 102829454*x**4 +699732361*x**3 - 2673468816*x**2 + 4956440220*x - 2888395200
x1=solve(f1==0, x)[-1]
x2=solve(f2==0, x)[-1]
x3=solve(f3==0, x)[-1]
x4=solve(f4==0, x)[-1]
x5=solve(f5==0, x)[-1]
x6=solve(f6==0, x)[-1]
x7=solve(f7==0, x)[-1]
x8=solve(f8==0, x)[-1]
print(chr(x1), end="")
print(chr(x2), end="")
print(chr(x3), end="")
print(chr(x4), end="")
print(chr(x5), end="")
print(chr(x6), end="")
print(chr(x7), end="")
print(chr(x8), end="")
```
=> thông điệp là **`sonorous`**.
# System of Linear Equations
Ví dụ như ta có phương trình 2 biến x+y=10 thì ta sẽ khai báo như sau:
```
sage: x = var(’x’, domain=ZZ)
sage: y = var(’y’, domain=ZZ)
sage: solve(x+y==10, (x,y))
(t_0, -t_0 + 10)
```
Nếu ta có thêm 1 phương trình nữa thì sẽ tìm được x,y, mình ví dụ ở đây là x=y, giờ đây ta có hệ phương trình 2 ẩn 2 phương trình => đủ điều kiện để giải hệ phương trình.
```
sage: x=var('x', domain=ZZ)
sage: y=var('y', domain=ZZ)
sage: solve([x+y==10,x==y],(x,y))
[[x == 5, y == 5]]
```
## Áp dụng
A rich collection of mathematical problems can be solved by using systems of linear equations. Let’s take as example the simple puzzle in fig. 4.1 and solve it with SageMath.
Một bài toán đơn giản để ta làm quen với sagemath:
```
sage: x=var('x', domain=ZZ)
sage: y=var('y', domain=ZZ)
sage: z=var('z', domain=ZZ)
sage: solve([2*x+y==15, x+y+z==20, 3*z==30], (x,y,z))
[[x == 5, y == 5, z == 10]]
```
## Challenge 2
Can you recover the hidden message in the picture puzzle in fig. 4.2 on the next page? Each symbol represents a distinct decimal digit. There is a balance that each left side equals the corresponding right side. Automate the process by using SageMath. Hint: ASCII (American Standard Code for Information Interchange) is involved.
# Matrices
Có cách nào thuận tiện hơn để viết ra các hệ phương trình tuyến tính lớn không? Mình sẽ giới thiệu cách này bằng việc sử dụng augmented matrices ( ma trận bổ sung ).
Chúng ta có 2 hàng và 3 cột và tổng cộng có 6 phần tử. Chúng ta định nghĩa một phần tử là a[i,j] khi chúng ta muốn nhấn mạnh rằng phần tử đó nằm ở hàng thứ i và cột thứ j.
Ví dụ: a[1,1] = 1, a[1,3] = 3, a[2,2] = 4.
Trong hệ phương trình tuyến tính sau, các biến độc lập được gọi là a, b, c, d, e và f.
Chúng ta có thể dễ dàng viết hệ phương trình tuyến tính này dưới dạng ma trận. Hãy viết tất cả các hệ số đứng trước biến a vào cột đầu tiên của ma trận mới, tất cả các hệ số đứng trước biến b trong cột thứ hai, v.v. Điều này tạo thành ma trận hệ số.
Vế phải của mỗi phương trình tạo thành một cột khác – cột cuối cùng. Để rõ ràng, chúng tôi sẽ tách nó khỏi các cột khác bằng một đường thẳng đứng. Chúng ta gọi ma trận đó là ma trận bổ sung.
**Các tính chất của ma trận:**
• Hoán đổi vị trí của hai phương trình không ảnh hưởng đến việc giải hệ phương trình tuyến tính.
• Nhân phương trình với một số khác 0 không ảnh hưởng đến việc giải hệ phương trình tuyến tính.
• Việc cộng một phương trình được chọn ngẫu nhiên này vào một phương trình được chọn ngẫu nhiên khác không ảnh hưởng đến việc giải hệ phương trình tuyến tính.
Trong [đại số tuyến tính](https://vi.wikipedia.org/wiki/%C4%90%E1%BA%A1i_s%E1%BB%91_tuy%E1%BA%BFn_t%C3%ADnh "Đại số tuyến tính"), **phép khử Gauss** là một [thuật toán](https://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n "Thuật toán") có thể được sử dụng để tìm nghiệm của một [hệ phương trình tuyến tính](https://vi.wikipedia.org/wiki/H%E1%BB%87_ph%C6%B0%C6%A1ng_tr%C3%ACnh_tuy%E1%BA%BFn_t%C3%ADnh "Hệ phương trình tuyến tính"), tìm hạng (hay [rank](https://vi.wikipedia.org/wiki/H%E1%BA%A1ng_(%C4%91%E1%BA%A1i_s%E1%BB%91_tuy%E1%BA%BFn_t%C3%ADnh) "Hạng (đại số tuyến tính)")) của một [ma trận](https://vi.wikipedia.org/wiki/Ma_tr%E1%BA%ADn "Ma trận"), để tính [ma trận nghịch đảo](https://vi.wikipedia.org/wiki/Ma_tr%E1%BA%ADn_kh%E1%BA%A3_ngh%E1%BB%8Bch "Ma trận khả nghịch") của một ma trận vuông khả nghịch. Phép khử Gauss được đặt theo tên của nhà toán học Đức là [Carl Friedrich Gauss](https://vi.wikipedia.org/wiki/Carl_Friedrich_Gau%C3%9F "Carl Friedrich Gauß").
Hãy áp dụng phép khử Gaussian cho hệ phương trình tuyến tính sau:
Ta có A.X=B => X=B.A^-1
```
sage: A=matrix([[4,8,3],[5,6,2],[9,5,1]])
sage: B=matrix([[10],[15],[20]])
sage: A_nd=A.inverse()
sage: A_nd*B
[ 25]
[-75]
[170]
```
## Challenge 3
We discovered a solution to the system of linear equations by just following an algorithm and by using only 3 main operations. As an exercise, and by applying the newly discovered method of solving system of linear equations, can you solve this challenge? The system of equations is listed in fig.
```
sage: A=matrix([[115,111,108],[118,101,115],[111,114,116]])
sage: B=matrix([[2209],[2214],[2286]])
sage: C=matrix([[97,100,100],[111,110,101],[116,111,101]])
sage: D=matrix([[1582],[1748],[1786]])
sage: E=matrix([[97,99,104],[108,101,116],[116,101,114]])
sage: F=matrix([[910],[1005],[1019]])
sage: A.inverse()*B
[4]
[7]
[9]
sage: C.inverse()*D
[6]
[8]
[2]
sage: E.inverse()*F
[3]
[1]
[5]
```
b=4,h=7,f=9,q=6,m=8,a=2,r=3,n=1,t=5, mình giải đáp án thì là vậy còn thông điệp của chall này là gì thì mình không biết.
**Ma trận đường chéo**
Ma trận vuông trong đó mọi phần tử ngoại trừ các phần tử chính của đường chéo đều bằng 0 được gọi là ma trận đường chéo.
Lưu ý rằng phép nhân ma trận, giới hạn ở ma trận đường chéo, có tính chất giao hoán. Cũng lưu ý rằng chuyển vị hoạt động bình thường trên các ma trận đường chéo: A^T = A với mọi ma trận đường chéo A.
Để tiếp tục định nghĩa Lattices và các tính chất của chúng, chúng ta cần giới thiệu một số định nghĩa và ký hiệu cơ bản về vectơ, - tùy thuộc vào ngữ cảnh - đôi khi có thể được xem dưới dạng ma trận đặc biệt chỉ có một cột hoặc chỉ có một hàng.
## CTF challenge
Một ví dụ về việc sử dụng ma trận để tìm flag trong bài Just One More giải Nohamcon 2023.
jom.py
```python
import random
OUT = open('output.txt', 'w')
FLAG = open('flag.txt', 'r').read().strip()
N = 64
l = len(FLAG)
arr = [random.randint(1,pow(2, N)) for _ in range(l)]
OUT.write(f'{arr}\n')
s_arr = []
for i in range(len(FLAG) - 1):
s_i = sum([arr[j]*ord(FLAG[j]) for j in range(l)])
s_arr.append(s_i)
arr = [arr[-1]] + arr[:-1]
OUT.write(f'{s_arr}\n')
```
output.txt
```
[12407953253235233563, 3098214620796127593, 18025934049184131586, 14516706192923330501, 13439587873423175563, 17668371729629097289, 4983820371965098250, 1941436363223653079, 15491407246309500298, 8746935775477023498, 911995915798699052, 16286652540519392376, 13788248038504935294, 18140313902119960073, 11357802109616441330, 2498891881524249135, 9088680937359588259, 14593377776851675952, 2870989617629497346, 18249696351449250369, 2029516247978285970, 14734352605587851872, 8485311572815839186, 8263508188473851570, 14727305307661336083, 6229129263537323513, 17136745747103828990, 8565837800438907855, 17019788193812566822, 9527005534132814755, 1469762980661997658, 16549643443520875622, 9455193414123931504, 12209676511763563786, 271051473986116907, 17058641684143308429, 13420564135579638218, 7599871345247004229]
[35605255015866358705679, 36416918378456831329741, 35315503903088182809184, 36652502430423040656502, 34898639998194794079275, 36303059177758553252637, 35047128751853183340357, 36513205019421922844286, 35188395228735536982649, 35301216188296520201752, 35877364908848326577377, 35548407875093684038138, 36846989992339836295226, 35424096673112978582599, 35435941095923989701820, 35884660233631412675912, 35250569480372437220096, 36071512852625372107309, 35636049634203159168488, 35407704890518035619865, 35691117250745693469087, 35942285968400856168658, 35659245396595333737528, 34682110547383898878610, 36251061019324605768432, 34350337346574061914637, 36706069443188806905153, 35296365364968284652906, 34767397368306249667499, 37665777691001951216694, 33927027243025444519647, 37464577169642287783563, 34818703279589326375333, 35526731706613463585509, 36698165076109278070662, 34612009622491263626134, 37224659068886403545747]
```
Sign in with Wallet
Connect another wallet