ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
—————————–

Khúc Xuân Thành

LÝ THUYẾT LƯỚI VÀ ỨNG DỤNG TRONG MẬT MÃ

LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội - Năm 2017



ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
——————————

Khúc Xuân Thành

LÝ THUYẾT LƯỚI VÀ ỨNG DỤNG TRONG MẬT MÃ

Chuyên ngành: Đại số và lý thuyết số
Mã số: 60460104

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. Lê Minh Hà

Hà Nội - Năm 2017

LỜI CẢM ƠN
Lời đầu tiên của luận văn này em xin gửi lời cảm ơn sâu sắc tới thầy
giáo hướng dẫn PGS. TS. Lê Minh Hà. Thầy đã tận tình hướng dẫn em
trong quá trình hoàn thành luận văn này. Nhân dịp này em xin gửi lời
cám ơn của mình tời toàn bộ các thầy cô giáo trong khoa Toán-Cơ-Tin
học đã giảng dạy và giúp đỡ chúng em trong suốt quá trình học tập tại
khoa.
Đồng thời, em cũng xin cảm ơn lãnh đạo Viện Khoa học-Công nghệ
mật mã, Ban Cơ yếu Chính phủ đã tạo điều kiện công việc để em có thể
hoàn thành luận văn này.
Hà nội, ngày 01 tháng 08 năm 2017
Học viên

Khúc Xuân Thành


Mục lục
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Bảng ký hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 Một số kiến thức cơ bản về lưới và lược
1.1 Lưới trong không gian thực n chiều . . .
1.2 Xây dựng cơ sở lưới . . . . . . . . . . . .
1.3 Trực giao hóa Gram-Schmidt . . . . . .
1.4 Một định nghĩa khác về lưới . . . . . . .
1.5 Lược đồ chữ ký . . . . . . . . . . . . . .
1.5.1 Lược đồ DSA . . . . . . . . . . .

1.5.2 Lược đồ ECDSA . . . . . . . . .
1.5.3 Lược đồ GOST R 34.10-2012 . .

.
.
.
.
.
.
.
.

8
8
11
16
24
26
27
29
30

2 Thuật toán LLL
2.1 Cơ sở lưới rút gọn . . . . . . . . . . . . . . . . . . . . . . .
2.2 Thuật toán LLL . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Phân tích thuật toán LLL . . . . . . . . . . . . . . . . . .

32
32
37

39

3 Ứng dụng của thuật toán LLL trong mật mã
3.1 Phương pháp Coppersmith . . . . . . . . . . . . . . . . . .
3.1.1 Giới thiệu bài toán . . . . . . . . . . . . . . . . . .
3.1.2 Xây dựng ma trận Coppersmith . . . . . . . . . .

46
46
46
48

3.1.3 Áp dụng thuật toán LLL . . . . . . . . . . . . . .
Tấn công lên lược đồ chữ ký số . . . . . . . . . . . . . . .

52
53

3.2

3

đồ
. .
. .
. .
. .
. .
. .
. .

. .

chữ
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .

ký
. .
. .
. .
. .
. .
. .
. .
. .

số
. .
. .
. .
. .
. .
. .
. .

. .

3
5
6


MỤC LỤC

3.3

3.2.1 Ý tưởng xây dựng tấn công .
3.2.2 Tấn công theo Blake 2002 . .
3.2.3 Tấn công theo Poulakis 2011
3.2.4 Tấn công theo Draziotis 2016
3.2.5 Tấn công theo Poulakis 2016
Kết quả thực nghiệm . . . . . . . . .

.
.
.
.
.
.

.
.
.
.
.

.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.


.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.

.
.
.
.

.
.
.
.
.
.

53
56
59
62
68
73

Kết luận

76

Tài liệu tham khảo

77

Phụ lục
A.1 Phương pháp dãy Sturm . . . . . . . . . . . . . . . . . . .


80
80

4


Bảng ký hiệu
N
N∗
Z
Q
R
C
Fq
..
.
..
.

tập hợp số tự nhiên
tập hợp số tự nhiên khác 0
tập hợp các số nguyên
tập hợp số hữu tỉ
tập hợp số thực
tập hợp số phức
Trường hữu hạn gồm q phần tử
phép chia hết

không chia hết
deg

bậc của đa thức
Span(S) Không gian véctơ căng bởi hệ véctơ S
GCD
Ước chung lớn nhất
f = O(g) Tồn tại c, x0 > 0 sao cho |f | ≤ c|g| với mọi x ≥ x0
Chuẩn Euclide
x·y
Tích vô hướng của véctơ x và y
a
Số nguyên gần nhất của a
a
nếu a ≤ q/2
a
Với a ∈ [1, . . . , q], a =
a − q nếu a > q/2

5


Lời nói đầu
Lý thuyết lưới đã được nghiên cứu cách đây khoảng 100 năm dưới tên
gọi là “hình học của các số” (geometry of numbers), nhưng những ứng
dụng của nó thực sự mới được phát triển từ khi có thuật toán rút gọn
cơ sở lưới do ba nhà toán học Arjen Lenstra, Hendrik Lenstra, László
Lovász tìm ra (được viết tắt là LLL) [16]. Thuật toán LLL lập tức được
xem là một trong những thuật toán quan trọng trong lý thuyết số khi
đã chỉ ra một thuật toán thời gian đa thức cho việc phân tích các đa
thức nguyên và giải các phương trình diophantine đồng thời.
Một trong những ứng dụng đầu tiên của thuật toán LLL trong mật
mã là phá vỡ hệ mật Merkle–Hellman. Sau đó là các tấn công lên hệ mật

RSA [5], [17] dựa trên phương pháp Coppersmith. Các tấn công lên lược
đồ chữ ký DSA [7], [19] và ECDSA [20] cũng là một trong những hướng
nghiên cứu được quan tâm nhiều hiện nay.
Mục đích của luận văn này là tìm hiểu lý thuyết lưới, thuật toán LLL
và một số tấn công lên các lược đồ chữ ký số dựa trên thuật toán LLL.
Cụ thể, luận văn đã trình bày một số kiến thức chuẩn bị liên quan đến lý
thuyết lưới trước khi trình bày và phân tích độ phức tạp của thuật toán
LLL. Phương pháp Coppersmith để tìm nghiệm nhỏ của đa thức là một
ứng dụng đầu tiên của thuật toán LLL mà luận văn đã trình bày. Tiếp
theo, luận văn trình bày bốn tấn công mới được công bố gần đây lên
các lược đồ chữ ký DSA, ECDSA trong [2], [23], [24], [8]. Một số nhầm
lẫn trong các bài báo này cũng đã được luận văn này chỉ ra. Chẳng hạn
như: sai sót trong tính toán bằng số để mô tả tấn công của [23], một số
định nghĩa chưa chính xác trong [8] hay tính không khả thi của tấn công
trong [24]. Các tác giả của các bài báo trên cũng đã công nhận những
nhầm lẫn này. Bên cạnh đó, luận văn cũng đã áp dụng bốn tấn công trên
sang lược đồ chữ ký GOST R 34.10-2012. Các kết quả thực nghiệm cài
đặt các tấn công trên phần mềm tính toán đại số Magma cũng là một


Lời nói đầu

trong những nội dung chính của luận văn này.
Bố cục của luận văn bao gồm 3 chương:
• Chương 1 trình bày một số kiến thức chuẩn bị như phép trực giao

hóa Gram-Schmidt, định nghĩa lưới, lưới con và cách xây dựng cơ
sở của lưới. Bên cạnh đó, một sơ lược về các lược đồ chữ ký số
DSA, ECDSA và GOST R 34.10-2012 cũng là một nội dụng của
chương này.

• Chương 2 trình bày và phân tích độ phức tạp của thuật toán rút

gọn cơ sở lưới LLL.
• Chương 3 trình bày một số ứng dụng của thuật toán LLL như

phương pháp Coppersmith và bốn tấn công lên lược đồ chữ ký
DSA, ECDSA và GOST R 34.10-2012. Các kết quả thực nghiệm
cài đặt các tấn công trên Magma cũng được trình bày trong chương
này.
Do thời gian thực hiện luận văn không nhiều, kiến thức còn hạn chế nên
khi làm luận văn không tránh khỏi những hạn chế và sai sót. Tác giả
mong nhận được sự góp ý và những ý kiến phản biện của thầy cô và bạn
đọc. Xin chân thành cảm ơn!
Hà Nội, ngày 08 tháng 08 năm 2017
Học viên

Khúc Xuân Thành

7


Chương 1
Một số kiến thức cơ bản về lưới
và lược đồ chữ ký số
Trong chương này, luận văn trình bày lại tổng quan một số kiến thức
về lý thuyết lưới như định nghĩa lưới trong không gian thực, trực giao
hóa Gram-Schmidt, xây dựng cơ sở của lưới và lược đồ chữ ký số trong
mật mã. Các nội dung của chương này về lý thuyết lưới đều được trích
dẫn từ cuốn sách của Bremer [4].


1.1

Lưới trong không gian thực n chiều

Cho n là một số nguyên dương. Tập hợp các véctơ cột cỡ n × 1 gồm
các phần tử của R cùng với các phép toán thông thường lập thành một
không gian véctơ n chiều trên trường R, ký hiệu là Rn . Rn được trang
bị thêm một tích vô hướng chính tắc, Rn cùng với tích vô hướng chính
tắc này lập thành một không gian Euclide và có cơ sở chính tắc.
Định nghĩa 1.1. Cho n ≥ 1, x1 , x2 , . . . , xn là một cơ sở của Rn . Lưới1
n chiều với cơ sở x1 , x2 , . . . , xn là tập hợp L tất cả các tổ hợp tuyến tính
của các véctơ cơ sở với hệ số nguyên.
L = Z x1 +Z x2 + . . . + Z xn =

ai xi |a1 , . . . , an ∈ Z .

Các véctơ cơ sở x1 , x2 , . . . , xn được gọi là phần tử sinh của lưới. Ta
cũng nói các véctơ này căng lưới L.
1

Lattice


1.1 Lưới trong không gian thực n chiều

Với i = 1, 2, . . . , n, xi = (xi1 , xi2 , . . . , xin ). Khi đó, các véctơ cơ sở thành
lập một ma trận X = (xij ). Định thức của lưới L với cơ sở x1 , x2 , . . . , xn
được định nghĩa là det L = |det X|. Ma trận Gram ∆(L) của lưới L là
ma trận cấp n mà vị trí ở ô (i, j) là tích vô hướng xi · xj . Nói cách khác,
∆(L) = XX t . Khi đó, định thức của lưới được định nghĩa là det L =

∆(L).
Tiếp theo, ta sẽ chỉ ra rằng định thức của lưới không phụ thuộc vào
cách chọn cơ sở lưới.
Bổ đề 1.2. Cho x1 , x2 , . . . , xn và y1 , y2 , . . . , yn là hai cơ sở của lưới L ⊂
Rn . Lấy X, Y lần lượt là các ma trận n × n nhận xi (tương ứng yi ) là
các hàng thứ i với i = 1, 2, . . . , n. Khi đó Y = CX ở đó C là một ma trận
vuông n × n với các hệ số nguyên và det(C) = ±1.
Chứng minh. Mọi yi thuộc lưới với cơ sở x1 , x2 , . . . , xn và mọi xi thuộc
lưới với cơ sở y1 , y2 , . . . , yn . Khi đó,
n

xi =

n

bij yj ,
j=1

yi =

cij xj ,

(i = 1, 2, . . . , n)

j=1

ở đây B = (bij ) và C = (cij ) là các ma trận vuông cấp n với các hệ
số nguyên. Viết hai phương trình trên theo dạng ma trận, ta có X =
BY , Y = CX . Vì vậy, X = BCX và Y = CBY . Do x1 , x2 , . . . , xn và
y1 , y2 , . . . , yn là cơ sở của Rn nên ma trận X và Y là các ma trận khả

nghịch. Do đó, BC = I , CB = I và det(B) det(C) = 1. Hơn nữa, B, C
là các ma trận với các hệ số nguyên, suy ra det(B) = det(C) = 1 hoặc
det(B) = det(C) = −1.
Bổ đề 1.3. Định thức của một lưới không phụ thuộc vào cách chọn cơ
sở.
Chứng minh. Giả sử lưới L ⊂ Rn có hai cơ sở x1 , x2 , . . . , xn và
y1 , y2 , . . . , yn . Theo Bổ đề 1.2, ta có
|det(Y )| = |det(CX)| = |det(C) det(X)| = |± det(X)| = |det(X)| .

Định nghĩa 1.4. Một ma trận vuông n × n với các hệ số nguyên và có
định thức bằng ±1 được gọi là ma trận unimodular.
9


1.1 Lưới trong không gian thực n chiều

Định nghĩa 1.5. Một phép biến đổi hàng unimodular trên một ma
trận là một trong các phép biến đổi hàng sơ cấp sau:
• Nhân một hàng với −1;
• Đổi chỗ hai hàng;
• Cộng một bội số nguyên của một hàng vào một hàng khác.

Chú ý, trong Định nghĩa 1.1 ta viết các véctơ cơ sở như các véctơ
hàng. Do đó, các phép toán trên các véctơ cơ sở có thể được xem như là
các phép biến đổi hàng unimodular của ma trận X . Nói cách khác, điều
này tương đương với việc nhân ma trận X với một ma trận nguyên C có
định thức bằng ±1.
Để xây dựng các ma trận unimodular, ta có thể xuất phát từ ma
trận đơn vị In và thực hiện (một số hữu hạn) các phép biến đổi hàng
unimodular. Nếu ta áp dụng các phép biến đổi hàng unimodular vào ma

trận X có các véctơ hàng là cơ sở của một lưới L thì sẽ thu được một cơ
sở mới của lưới này.
Sử dụng phương pháp trên, ta có thể xuất phát từ một cơ sở của một
lưới bao gồm các véctơ ngắn, và tạo ra một cơ sở mới cho cùng một lưới
bao gồm các véctơ dài hơn rất nhiều. Tất nhiên, bài toán thú vị và quan
trọng hơn là làm ngược lại: Giả sử cho trước một cơ sở của một lưới mà
nói chung, cơ sở ban đầu này sẽ gồm các véctơ dài, ta cần tìm một cơ
sở "rút gọn" khác cho lưới đó, tức là một cơ sở gồm các véctơ ngắn. Đó
chính là bài toán rút gọn cơ sở lưới 2 , bài toán trung tâm mà chúng ta
sẽ tìm hiểu trong chương 2.
Trước hết, ta cần tổng quát hóa khái niệm cơ sở lưới và định thức
lưới cho mọi tập độc lập tuyến tính gồm m ≤ n véctơ trong Rn .
Định nghĩa 1.6. Cho n ≥ 1 và x1 , x2 , . . . , xm , (m ≤ n) là một tập gồm
m véctơ độc lập tuyến tính trong Rn . Lưới m-chiều căng bởi các véctơ
này trong không gian Euclide n chiều được định nghĩa là
L = Z x1 +Z x2 + . . . + Z xm .

Với mỗi i = 1, 2, . . . m, ta viết xi = (xi1 , xi2 . . . , xim ) và lập một ma trận
X = (xij ) cỡ m × n. Khi đó, định thức của lưới L là det L = (det(XX t )1/2 .
2

lattice basis reduction

10


1.2 Xây dựng cơ sở lưới

1.2


Xây dựng cơ sở lưới

Một kết quả quan trọng trong đại số tuyến tính là mỗi hệ độc lập
tuyến tính trong một không gian véctơ đều có thể bổ sung được để trở
thành một cơ sở. Vấn đề chúng ta quan tâm là việc bổ sung vào một hệ
độc lập tuyến tính các véctơ lưới để thu được một cơ sở của lưới đang
xét.
Định nghĩa 1.7. Cho L ⊂ Rn là một lưới có cơ sở x1 , x2 , . . . , xn . Giả sử
y1 , y2 , . . . , yn ∈ L độc lập tuyến tính, và M là lưới sinh bởi y1 , y2 , . . . , yn .
Ta nói M là một lưới con của L, và viết M ⊆ L.
Mỗi véctơ cơ sở yi của lưới con M đều thuộc vào lưới L, do đó
yi =

cij xj ,

(i = 1, 2, . . . , n),

ở đó cij ∈ Z với mọi i, j . Theo ngôn ngữ ma trận, ta có
Y = CX,

ở đó C = (cij ) là ma trận không suy biến cấp n có hệ số nguyên, và X ,
Y lần lượt là các ma trận cấp n có xi , yi ở hàng i. Lấy định thức hai vế,
ta có
det Y = det C det X.

Định nghĩa 1.8. Chỉ số ρ của lưới con M trong lưới L được định nghĩa
là
ρ = | det C| =

det M

| det Y |
=
.
| det X|
det L

Chỉ số này là một số nguyên vì det C nguyên và phụ thuộc vào L, M
mà không phụ thuộc vào cách chọn các cơ sở.
Định nghĩa 1.9. Cho C là một ma trận vuông cấp n. Định thức con3
(i, j) của C là định thức của ma trận thu được từ C sau khi xóa đi hàng
i và cột j . Phần bù đại số4 (j, j) là (−1)i+j nhân với định thức con (i, j).
Ma trận phụ hợp5 của C , adj(C), là ma trận thu được khi lấy chuyển
vị ma trận của các phần bù đại số.
3

minor
cofactor
5
adjoint matrix
4

11


1.2 Xây dựng cơ sở lưới

Ta có, nếu C là một ma trận khả nghịch thì C −1 = det1 C adj(C). Quay
trở về thảo luận ở trên về lưới con M (với ma trận Y ) của lưới L (với
ma trận X ), ta thấy phương trình Y = CX dẫn đến
X = C −1 Y =


1
adj(C)Y,
det C

và do đó
ρX = | det C|X = ±adj(C)Y.

Vì các phần tử của C đều là các số nguyên nên các phần tử của adj(C)
cũng vậy, và do đó mỗi hàng của ma trận ρX là một tổ hợp tuyến tính
hệ số nguyên của các hàng của ma trận Y . Ta kết luận rằng lưới ρL bao
gồm tất cả các bội của số nguyên ρ của các véctơ trong L, là một lưới
con của lưới M . Ta đã chứng minh bổ đề sau:
Bổ đề 1.10. Nếu L là một lưới và M là một lưới con chỉ số ρ thì
ρL ⊆ M ⊆ L.

Định lý 1.11. Cho L là một lưới trong Rn và M là một lưới con của
L. Giả sử x1 , x2 , . . . , xn là một cơ sở của L. Khi đó, tồn tại một cơ sở
y1 , y2 , . . . , yn của M sao cho Y = CX , ở đó C là một ma trận vuông cấp
n, tam giác dưới, với các hệ số khác không trên đường chéo chính. Nói
cách khác, có


y1 = c11 x1 ,


 y = c x +c x ,
21 1
22 2
2

.
.

.



yn = cn1 x1 + . . . + cnn xn .

ở đó cij ∈ Z, cii = 0 với mọi i, j . Ngược lại, nếu y1 , y2 , . . . , yn là một cơ
sở của M thì tồn tại một cơ sở x1 , x2 , . . . , xn thỏa mãn hệ phương trình
trên.
Chứng minh. Bổ đề 1.10 chỉ ra rằng ρL ⊆ M , và do đó ρ xi ∈ M với
mọi i. Khi đó, tồn tại các véctơ yi ∈ M (không nhất thiết phải là một
cơ sở của M ) và các số nguyên cij thỏa mãn điều kiện trên của định
lý (ta có thể chọn cii = ρ với mọi i và cij = 0 với mọi i = j ). Do đó,
tập tất cả các n-bộ véctơ yi ∈ M thỏa mãn điều kiện của định lý là
khác rỗng, và vì vậy với mỗi i ta có thể chọn yi ∈ M là véctơ mà cii là
12


1.2 Xây dựng cơ sở lưới

dương và nhỏ nhất có thể. Ta sẽ chỉ ra rằng các véctơ y1 , y2 , . . . , yn lập
thành một cơ sở của lưới con M . Do y1 , y2 , . . . , yn ∈ M nên mọi véctơ
w1 y1 +w2 y2 + . . . + wn yn ∈ M , wi ∈ Z. Giả sử, z ∈ M không phải là một
tổ hợp tuyến tính của y1 , y2 , . . . , yn ∈ M . Do z ∈ M ⊂ L nên ta có
z = t1 x1 +t2 x2 + . . . + tk xk ,

k ≤ n, tk = 0.


Nếu có nhiều véctơ z như vậy thì ta chọn z sao cho chỉ số k là nhỏ nhất
có thể. Theo giả thiết ckk = 0, viết tk = qckk + r, 0 ≤ r < ckk Khi đó,
xét véctơ
z − qyk = (t1 x1 +t2 x2 + . . . + tk xk ) − q(ck1 x1 +ck2 x2 + . . . + ckk xk )
= (t1 − qck1 ) x1 +(t2 − qck2 )x2 + . . . + (tk − qckk )xk .

Do z, yk ∈ M và q ∈ Z nên z − qyk ∈ M . Do z và z − qyk không phải là
tổ hợp tuyến tính nguyên của y1 , y2 , . . . , yn và chỉ số k được chọn là nhỏ
nhất nên tk − qckk = 0. Điều này chỉ ra rằng véctơ z − qyk ∈ M là một
tổ hợp tuyến tính của x1 , x2 , . . . , xk mà hệ số của xk là khác không và
nhỏ hơn ckk . Điều này mâu thuẫn với việc chọn yk ở trên. Do đó véctơ z
không tồn tại và mọi véctơ của M phải là một tổ hợp tuyến tính nguyên
của y1 , y2 , . . . , yn .
Ngược lại. Cho y1 , y2 , . . . , yn là một cơ sở của M . Theo Bổ đề 1.10, ta có
ρL ⊆ M . Do đó theo phần đầu của chứng minh với ρL là lưới con của
lưới M . Ta thu được một cơ sở ρ x1 , ρ x2 , . . . , ρ xn của ρL sao cho
ρ x1 = d11 y1
ρx2 = d21 y1 +d22 y2

..
.
ρ xn = dn1 y1 +dn2 y2 + . . . + dnn yn

ở đây dij ∈ Z, dii = 0, ∀i, j . Ta có thể viết các phương trình trên thành
dạng ma trận ρX = DY ở đây D = (dij ) n×n là ma trận nguyên tam giác
dưới với các phần tử trên đường chéo khác không. Suy Y = ρD−1 X . Do
x1 , x2 , . . . , xn là một cơ sở của L và y1 , y2 , . . . , yn ∈ M ⊆ L nên ta thấy
rằng tất cả các phần tử của ma trận ρD−1 phải là nguyên, bởi tính duy
nhất của biểu diễn mỗi véctơ lưới như một tổ hợp tuyến tính nguyên của

các véctơ cơ sở.
13


1.2 Xây dựng cơ sở lưới

Hệ quả 1.12. Trong phần thứ nhất của Định lý 1.11, có thể giả thiết
rằng
cii > 0

(1 ≤ i ≤ n)

và 0 ≤ cij < cjj

(1 ≤ j < i ≤ n).

Trong phần thứ hai của Định lý 1.11, ta có thể giả sử
cii > 0

(1 ≤ i ≤ n)

và 0 ≤ cij < cii

(1 ≤ j < i ≤ n).

Chứng minh. Xét dạng phương trình ma trận
Y = CX

(1.1)


Nếu cii < 0 với i nào đó thì ta nhân hai vế của phương trình (1.1) với
−Eii (ma trận chỉ có phần tử ở vị trí (i, i) bằng 1 ngoài ra tất cả các
phần tử ở vị trí khác bằng không), tức −Eii Y = −Eii CX . Thực chất đây
là một phép biến đổi hàng unimodular: “nhân hàng thứ i với −1”.
Nếu cij < 0 hoặc cij ≥ cjj với i, j nào đó thì viết cij = qcjj + r với
0 ≤ r < cjj (ta giả sử rằng cjj > 0). Nhân hai vế của (1.1) với In − qEij ,
tức (In − qEij )Y = (In − qEij )CX . Điều này cũng tương đương với phép
biến đổi hàng unimodular “trừ q lần hàng thứ j từ hàng thứ i”
Từ hai trường hợp trên, ta có thể biểu diễn phép biến đổi hàng
unimodular như sau: U Y = U CX , ở đây U là ma trận unimodular. Do
U là ma trận tam giác dưới nên, U C cũng là ma trận tam giác dưới. Vì
vậy, ta có thể thay thế ma trận cơ sở y1 , y2 , . . . , yn của M , gồm các hàng
của ma trận Y bằng cơ sở mới gồm các hàng của ma trận U Y . Trường
hợp còn lại có thể chứng minh theo một cách tương tự.
Hệ quả 1.13. Cho L là một lưới n chiều trong Rn , và y1 , y2 , . . . , ym ,
m ≤ n, là một hệ véctơ độc lập tuyến tính trong L. Khi đó tồn tại một
cơ sở x1 , x2 , . . . , xn của L thỏa mãn hệ phương trình


y1 = c11 x1 ,



y2







= c21 x1 +c22 x2 ,

..
.

ym = cm1 x1 + . . . + cmm xm .

ở đây cij ∈ Z, cii > 0, 0 ≤ cij < cii với mọi i, j .

14


1.2 Xây dựng cơ sở lưới

Chứng minh. Ta có thể tìm n − m véctơ ym+1 , . . . , yn trong L sao cho
các véctơ y1 , y2 , . . . , yn là độc lập tuyến tính. Khi đó ta áp dụng phần
hai của Hệ quả 1.12 cho lưới M với cơ sở y1 , y2 , . . . , yn . Ta có điều phải
chứng minh.
Hệ quả 1.14. Cho L là một lưới n chiều trong Rn , và y1 , y2 , . . . ym ,
m < n là một hệ véctơ độc lập tuyến tính trong L. Khi đó các điều kiện
sau đây là tương đương.
1. Tồn tại (n − m) véctơ ym+1 , . . . , yn trong L sao cho hệ y1 , y2 , . . . , yn
lập thành một cơ sở của L.
2. Nếu z ∈ L là một tổ hợp tuyến tính của y1 , y2 , . . . , ym thì nó là một
tổ hợp tuyến tính nguyên của các véctơ đó.
Chứng minh. (1) ⇒ (2) hiển nhiên. Để chứng minh (2) ⇒ (1), giả sử rằng
y1 , y2 , . . . , ym thỏa mãn điều kiện (2). Do y1 , y2 , . . . , ym là độc lập tuyến
tính trong L, nên ta có thể áp dụng Hệ quả 1.13 để thu được một cơ sở
x1 , x2 , . . . , xn của L thỏa mãn các phương trình của Hệ quả 1.13. Xét m
véctơ cơ sở đầu tiên x1 , x2 , . . . , xm , ta có phương trình ma trận Y = CX ,

với C có kích thước m × m hay X = C −1 Y . Do điều kiện (2) suy ra các
phần tử trong C −1 là nguyên. Nhưng C là ma trận đường chéo dưới với
các phần tử trên đường chéo là c11 , c22 , . . . , cmm nên C −1 cũng là ma trận
−1
−1
đường chéo dưới với các phần tử trên đường chéo là c−1
11 , c22 , . . . , cmm . Do
đó, với mọi i = 1, 2, . . . , m, ta thấy rằng cii là một số nguyên và c−1
ii là
nguyên nên cii = ±1.
Bây giờ ta áp dụng Hệ quả 1.12 suy ra cii = 1 với 1 ≤ i ≤ m và cij = 0
với 1 ≤ j < i ≤ m. Do đó, C = Im và yi = xi với i = 1, 2, . . . m. Đặt yi = xi
với i = m + 1, . . . , n ta có điều phải chứng minh
Hệ quả 1.15. Cho L là một lưới n chiều trong Rn với cơ sở x1 , x2 , . . . xn .
Xét z ∈ L là một véctơ bất kỳ và viết
z = a1 x1 +a2 x2 + . . . + an xn

(a1 , a2 , . . . , an ∈ Z).

Khi đó các điều kiện sau đây là tương đương với mọi số nguyên m =
1, 2, . . . n:
1. Tồn tại các véctơ ym+1 , . . . , yn ∈ L sao cho hệ n véctơ sau đây lập
thành một cơ sở cho L:
x1 , x2 , . . . , xm−1 , z, ym+1 , . . . , yn .
15


1.3 Trực giao hóa Gram-Schmidt

2. Ước chung lớn nhất của các số nguyên am+1 , . . . , an bằng 1.

Chứng minh. Dễ thấy từ Hệ quả 1.14.
Định nghĩa 1.16. Cho L là một lưới m chiều trong không gian Euclidean Rn . Cực tiểu kế tiếp thứ i6 của lưới Λi (L) là số thực r nhỏ nhất
sao cho tồn tại i véctơ độc lập tuyến tính x1 , x2 , . . . , xi ∈ L thỏa mãn
x1 , x2 , . . . , xi ≤ r. Ta có thể biểu diễn như sau
Λi (L) = min max( x1 , . . . , xi ).

ở đây min được lấy trên tập hợp tất cả các hệ gồm i véctơ độc lập tuyến
tính trong L.
Ta thấy Λ1 (L) ≤ Λ2 (L) ≤ . . . ≤ Λm (L). Rõ ràng, một cơ sở lý tưởng
nhất cho lưới L m chiều là cơ sở gồm các véctơ x1 , x2 , . . . , xm ∈ L sao cho
xi = Λi (L) với mọi i = 1, 2, . . . , m. Tuy nhiên, một cơ sở như vậy là rất
khó tìm và hơn nữa không phải hệ m véctơ nào thỏa mãn yêu cầu về độ
dài như trên cũng lập thành một cơ sở của L.
Trong [11] đã đưa ra một đánh giá heuristic (dựa trên các kết quả
thực nghiệm) cho véctơ ngắn nhất (cực tiểu kế tiếp thứ 1) trong lưới.
Mệnh đề 1.17. (Gaussian heuristic). Cho L là một lưới n chiều.
n
(det L)1/n .
Khi đó chiều dài của Λ1 (L) trong lưới xấp xỉ 2πe

1.3

Trực giao hóa Gram-Schmidt

Phần này, luận văn trình bày thuật toán Gram-Schmidt cổ điển cho
việc chuyển một cơ sở bất kỳ trong Rn thành một cơ sở trực giao. Đây
là một nội dung cổ điển của đại số tuyến tính nhưng lại là một kỹ thuật
quan trọng trong thuật toán LLL.
Định nghĩa 1.18. Cho x1 , x2 , . . . , xn là một cơ sở của Rn . Trực giao hóa
Gram-Schmidt (GSO)7 của x1 , x2 , . . . , xn là một cơ sở x∗1 , x∗2 , . . . , x∗n được

6
7

i-th successive minimum
Gram-Schmidt Orthogonalization

16


1.3 Trực giao hóa Gram-Schmidt

định nghĩa như sau:
x1 = x∗1 ,
i−1

x∗i

µij x∗j

= xi −

(2 ≤ i ≤ n),

µij =

j=1

xi · x∗j
x∗j · x∗j


(1 ≤ j < i ≤ n).

Lưu ý rằng trong định nghĩa trên, các véctơ không được chuẩn hóa độ
dài. Ngoài ra, dễ thấy rằng nếu x1 , x2 , . . . , xn ∈ Qn thì x∗1 , x∗2 , . . . , x∗n ∈ Qn .
Vấn đề khó khăn ở đây là, nếu x1 , x2 , . . . , xn là một cơ sở của lưới L thì
sau khi trực giao hóa các véctơ cơ sở x∗1 , x∗2 , . . . , x∗n có thể không còn nằm
trong lưới L nữa.
Nhận xét 1.19. Nếu ta đặt µii = 1 với 1 ≤ i ≤ n thì ta có viết gọn
i

µij x∗j .

xi =
j=1

Theo ngôn ngữ ma trận, viết xi = (xi1 , . . . , xin ) và X = (xij ) là ma
trận với các hàng là xi . Tương tự, ta có ma trận X ∗ = (x∗ij ). Đặt µij = 0
với 1 ≤ i < j ≤ n thì Định nghĩa 1.18 có thể được viết lại dưới dạng
phương trình ma trận như sau:
X = M X ∗ , M = (µij )



x1
x2
x3






 ..
.

xn





1
0
0
µ21 1
0
µ31 µ32 1

 
 
 
=
  ..
 .

..
.

..
.


µn1 µn2 µn3





x∗1
... 0
 ∗ 
... 0 
  x2 
 ∗ 
... 0 
  x3  .
.  . 
. . . ..   .. 
... 1
x∗n

Định lý sau đây nhắc lại các tính chất cơ bản của cơ sở GSO.
Định lý 1.20. Cho x1 , x2 , . . . , xn là một cơ sở của Rn và x∗1 , x∗2 , . . . , x∗n
là trực giao hóa Gram-Schmidt của nó. Ký hiệu X (tương ứng, X ∗ ) là
ma trận cấp n có hàng i là véctơ xi (tương ứng, x∗i ). Khi đó
(a) x∗i · x∗j = 0 với mọi 1 ≤ i < j ≤ n.
(b) Span(x∗1 , x∗2 , . . . , x∗k ) = Span(x1 , x2 , . . . , xk ) với mọi 1 ≤ k ≤ n.
17


1.3 Trực giao hóa Gram-Schmidt


(c) Với 1 ≤ k ≤ n, véctơ x∗k là hình chiếu của xk trên phần bù trực giao
của Span(x1 , x2 , . . . , xk−1 ).
(d)

x∗k ≤ xk với mọi 1 ≤ k ≤ n.

(e) det X ∗ = det X .
Chứng minh. (a) Ta chứng minh bằng quy nạp. Hiển nhiên bất đẳng
thức đúng với j = 1. Giả sử rằng khẳng định đúng với j ≥ 1. Ta sẽ chứng
minh rằng khẳng định cũng đúng với 1 ≤ i < j + 1. Ta có
j

x∗i · x∗j+1

=

x∗i ·

µj+1,k x∗k

xj+1 −
k=1
j

µj+1,k (x∗i · x∗k )

= x∗i ·xj+1 −
k=1

− µj+1,i (x∗i · x∗i )

xj+1 · x∗
= x∗i ·xj+1 − ∗ ∗ i (x∗i · x∗i )
xi · xi

=

x∗i ·xj+1

=0

(b) Theo Nhận xét 1.19, ta có xi ∈ Span(x∗1 , x∗2 , . . . , x∗k ) với 1 ≤ i ≤ k nên
Span (x1 , x2 , . . . , xk ) ⊆ Span(x∗1 , x∗2 , . . . , x∗k )

Để chứng minh Span(x∗1 , x∗2 , . . . , x∗k ) ⊆ Span (x1 , x2 , . . . , xk ) ta chứng minh
bằng quy nạp trên k . Với k = 1, ta có x∗1 = x1 nên khẳng định đúng. Bây
giờ, giả sử khẳng định đúng với k ≥ 1 nào đó. Khi đó, theo Định nghĩa
1.18, ta có
k

x∗k+1

µk+1,j x∗j = xk+1 + y,

= xk+1 −

y ∈ Span(x∗1 , x∗2 , . . . , x∗k ).

j=1

Do giả thiết quy nạp Span(x∗1 , x∗2 , . . . , x∗k ) ⊆ Span (x1 , x2 , . . . , xk ) nên đẳng

thức cuối suy ra rằng x∗k+1 ∈ Span (x1 , x2 , . . . , xk+1 ). Do đó,
Span(x∗1 , x∗2 , . . . , x∗k+1 ) ⊆ Span (x1 , x2 , . . . , xk+1 )

(c) Đặt U = Span (x1 , x2 , . . . , xk−1 ) và U ⊥ là không gian con của Rn ,
U ⊥ = {y ∈ Rn |y ·x = 0, ∀ x ∈ U }
18


1.3 Trực giao hóa Gram-Schmidt

Khi đó, có duy nhất một phân tích xk = x k + y, ở đây xk ∈ U ⊥ và y ∈ U .
Suy ra, xk là hình chiếu của xk trên phần bù trực giao của U . Hơn nữa,
k−1

xk =

x∗k

µij x∗j

+
j=1

và U = Span(x1 ∗, x∗2 , . . . , x∗k−1 ) nên x∗k = xk .
(d) Ta có xk = x∗k +

k−1
j=1

µkj x∗j . Do vậy, xk


2

= x∗k

2

k−1

+
j=1

µ2kj x∗j

2

. Suy

ra x∗k ≤ xk với 1 ≤ k ≤ n.
(e) Ta có X = M X ∗ ở đây M = (µij ) là ma trận tam giác dưới với µii = 1
với 1 ≤ i ≤ n. Do đó det(M ) = 1 và det(X ∗ ) = det(X).
Bổ đề 1.21. (Bất đẳng thức Hadamard) Cho X = (xij ) là một ma
trận thực cấp n, và lấy B = maxi,j |xij |. Khi đó, |det X| ≤ nn/2 B n .
Chứng minh. Cho xi = (xi1 , . . . , xin ) với 1 ≤ i ≤ n là các hàng của ma
trận X . Nếu các hàng này phụ thuộc tuyến tính thì det(X) = 0. Kết quả
luôn đúng. Nếu các hàng độc lập tuyến tính thì lấy X ∗ là ma trận mà
các hàng là các véctơ cơ sở trực giao x∗1 , x∗2 , . . . , x∗n . Theo Định lý 1.20(c),
ta có
|det X ∗ | = |det X| .


Do |det X ∗ | là thể tích của hình hộp n-chiều căng bởi các véctơ trực giao
x∗1 , x∗2 , . . . , x∗n , nên theo Định lý 1.20(a) suy ra
|det X ∗ | = x∗1

x∗2 . . . x∗n .

Theo Định lý 1.20(d),
|det X| ≤ x1

x 2 . . . xn .

Với 1 ≤ i ≤ n, ta có
xi

2

=

1/2

x2i1 + . . . + x2in ≤ (nB 2 )

= n1/2 B.

n

Do đó, |det X| ≤ (n1/2 B) .
Định nghĩa 1.22. Cho x1 , x2 , . . . , xn là một cơ sở của Rn , và X là ma
trận n × n với xi là hàng thứ i với 1 ≤ i ≤ n. Với 1 ≤ k ≤ n, lấy Xk là
19



1.3 Trực giao hóa Gram-Schmidt

ma trận k × n gồm k hàng đầu tiên của ma trận X . Ma trận Gram thứ
k của cơ sở này là ma trận đối xứng k × k
Gk = Xk Xkt .

Định thức Gram thứ k của cơ sở này là dk = det Gk .
Để thuật tiện, ta đặt d0 = 1. Nếu xi ∈ Zn với mọi i thì dk ∈ Z với mọi
0 ≤ k ≤ n.
Mệnh đề 1.23. Cho x1 , x2 , . . . , xn là cơ sở của Rn , và lấy x∗1 , x∗2 , . . . , x∗n
là trực giao hóa Gram-Schmidt của nó. Với 1 ≤ k ≤ n, định thức của ma
trận Gram thứ k là
k

x∗i 2 .

dk =
i=1

Chứng minh. Theo Nhận xét 1.19, ta có thể biểu diễn trực giao hóa
Gram-Schmidt như phương trình ma trận X = M X ∗ , ở đó M là ma trận
tam giác dưới. Lấy Mk là ma trận con có kích thước k × k ở góc trên bên
trái của M và lấy Xk∗ là ma trận có kích thước k × n gồm k hàng đầu
tiên của ma trận X ∗ . Ta có phân tích Xk = Mk Xk∗ , ở đây det(Mk ) = 1.
Do đó,
dk = det(Xk Xkt )
= det((Mk Xk∗ )(Mk Xk∗ )t )
= det(Mk (Xk∗ (Xk∗ )t )Mkt )

= det(Mk ) det(Xk∗ (Xk∗ )t ) det(Mkt )
= det(Xk∗ (Xk∗ )t )

Do các hàng x∗1 , x∗2 , . . . , x∗k của ma trận Xk∗ đôi một trực giao với nhau
nên Xk∗ (Xk∗ )t là một ma trận đường chéo với các phần tử trên đường chéo
là x∗1 2 , x∗2 2 , . . . , x∗k

2

k

. Do đó dk =
i=1

x∗i

2

.

Kết quả tiếp theo cho ta một ước lượng của mẫu số của số hữu tỉ
xuất hiện trong trực giao hóa Gram-Schmidt của các véctơ với thành
phần nguyên. Cận này sẽ quan trọng việc phân tích thuật toán LLL.

20


1.3 Trực giao hóa Gram-Schmidt

Mệnh đề 1.24. Cho x1 , x2 , . . . , xn là một cơ sở của Rn với xi ∈ Zn ,

1 ≤ i ≤ n. Lấy x∗1 , . . . , x∗n ∈ Qn là trực giao Gram-Schmidt của nó. Lấy
dk là định thức thứ k của ma trận Gram tương ứng. Khi đó
(a) Véctơ dk−1 x∗k có các thành phần nguyên với mọi 1 ≤ k ≤ n.
(b) dj µkj là một số nguyên với mọi 1 ≤ j ≤ k .
(c) µkj ≤ d1/2
j−1 xk với mọi 1 ≤ j ≤ k .
Chứng minh. (a) Ta có thể biểu diễn phép trực giao hóa bằng phương
trình ma trận X = M X ∗ , hoặc tương đương, X ∗ = M −1 X , ở đây M −1 là
ma trận đường chéo dưới với các phần tử trên đường chéo bằng 1. Do đó
k−1

x∗k

= xk −

λkj xj ,

λkj ∈ Q

(1.2)

j=1

λkj được gọi là “hệ số Gram-Schmidt ngược”. Xét véctơ xi với 1 ≤ i ≤ k−1.
Theo Định lý 1.20(a,b), ta có xi · x∗k = 0. Nhân tích vô hướng của hai vế
của (1.2) với xi ta thu được
k−1

xi · xk =


(xi · xj )λkj .
j=1

Với k cố định, có k − 1 lựa chọn cho i, do đó ta có một hệ tuyến tính của
k − 1 phương trình theo k − 1 biến λk1 , λk2 , . . . , λk,k−1 . Ma trận hệ số của
hệ này là ma trận Gram Gk−1 , và định thức của Gk−1 là dk−1 . Theo qui
tắc Cramer suy ra dk−1 λkj ∈ Z với 1 ≤ j ≤ k − 1. Khi đó, ta có
k−1

k−1

dk−1 x∗k

= dk−1 (xk −

λkj xj ) = dk−1 xk −
j=1

(dk−1 λkj )xj .
j=1

Do đó, với 1 ≤ k ≤ n, véctơ dk−1 x∗k là tổ hợp tuyến tính với hệ số nguyên
của các véctơ với các thành phần nguyên.
2
(b) Từ Mệnh đề 1.23, ta có x∗j = dj /dj−1 . Khi đó,
dj µkj = dj

xk · x∗j
x∗j · x∗j


= dj

xk · x∗j
2
x∗j

= dj−1 (xk · x∗j ) = xk · (dj−1 x∗j ).
21


1.3 Trực giao hóa Gram-Schmidt

Do giả thiết xk ∈ Zn và như trong phần (a) dj−1 x∗j ∈ Zn . Do vậy dj µkj ∈
Z.
(c) Ta có
µkj =

xk · x∗j

≤

x∗j · x∗j

xk · x∗j

=

2
x∗j


xk
.
x∗j

Do x1 , x2 , . . . , xj ∈ Zn nên dj ∈ Z. Hơn nữa, dj > 0 nên dj ≥ 1. Khi đó,
ta có
x∗j

2

=

dj
1
≥
.
dj−1
dj−1

Một phần quan trọng trong thuật toán LLL là việc đổi chỗ các véctơ
cơ sở kề nhau. Mệnh đề sau đây chỉ ra việc đổi chỗ ảnh hưởng thế nào
tới trực giao hóa Gram- Schmidt của cơ sở.
Mệnh đề 1.25. Cho x1 , x2 , . . . , xn là một cơ sở của Rn , và x∗1 , x∗2 , . . . , x∗n
là trực giao hóa Gram-Schmidt của nó. Lấy j trong khoảng 1 ≤ j ≤ n − 1
ˆ1, x
ˆ2, . . . , x
ˆ n là một cơ sở mới thu được sau khi hoán đổi xj và
và lấy x
xj+1
ˆ j = xj+1 ,

x

ˆ j+1 = xj ,
x

ˆ i = xi
x

(i = j, j + 1).

ˆ ∗2 , . . . , x
ˆ ∗n là trực giao hóa Gram-Schmidt của cơ sở mới. Khi
Ký hiệu xˆ ∗1 , x
ˆ ∗i = xi với i = j, j + 1 nhưng
đó x
ˆ ∗j
x

=

x∗j+1 +µj+1,j

x∗j ,

ˆ ∗j+1
x

=

2


x∗j+1
2
ˆ ∗j
x

x∗j −µj+1,j

x∗j

2

2
x∗j

x2j+1 .

Chứng minh. Do xˆ i = xi với i = j, j + 1 nên xˆ ∗i = x∗i với i < j và theo
Định lý 1.20(c) ta cũng có xˆ ∗i = x∗i , với i > j + 1. Với xˆ ∗j , ta có
j−1

ˆ ∗j
x

ˆj −
=x

ˆj · x
ˆ ∗i
x

ˆ ∗i = xj+1 −
·x
ˆ ∗i · x
ˆ ∗i
x

i=1
j−1

j−1

i=1
j−1

µj+1,i x∗i = xj+1 −

= xj+1 −
i=1

xj+1 · x∗i
· x∗i
x∗i · x∗i
µj+1,i x∗i +µj+1,j x∗j

i=1
x∗j+1

= x∗j+1 +µj+1,j x∗j
22