ĐẠI SỐ
TUYẾN TÍNH
VÀ
CẤU TRÚC ĐẠI SỐ
Mục lục
Chương 1 .................................................................................................................. 1
Chương 2 ................................................................................................................. 70
Chương 3 ................................................................................................................ 108
Chương 4 ................................................................................................................ 127
Chương 5 ................................................................................................................ 164
Chương 6 ................................................................................................................ 183
Chương 7 ................................................................................................................ 208
Chương 8 ................................................................................................................ 221
Bài tập chương 1 ................................................................................................... 241
Bài tập chương 2 ................................................................................................... 280
Bài tập chương 3 ................................................................................................... 306
Bài tập chương 4 ................................................................................................... 323
Bài tập chương 5 ................................................................................................... 350
Bài tập chương 6 ................................................................................................... 357
Bài tập chương 7 ................................................................................................... 373
Bài tập chương 8 ................................................................................................... 379
CHƯƠNG 1.
CÁC PHƯƠNG TRÌNH TUYẾN
TÍNH TRONG ĐẠI SỐ TUYẾN TÍNH
VÍ DỤ MỞ ĐẦU
Những mô hình tuyến tính trong kinh tế và kỹ thuật
Vào cuối mùa hè năm 1949. Giáo sư Harvard Wassily Leontief đã cẩn thận đưa chiếc thẻ
bấm lỗ cuối cùng của mình vào máy tính Mark II của trường đại học. Các thẻ này chứa
thông tin về nền kinh tế Mỹ và đại diện cho một bản tóm tắt của hơn 250.000 mẩu thông
tin được tạo ra bởi Cục Thống kê Lao động Hoa Kỳ sau hai năm làm việc chuyên sâu.
Leontief đã chia kinh tế Mỹ thành 500 “ngành”, như ngành than, ngành công nghiệp ô tô,
truyền thông, …. Đối với từng lĩnh vực, ông đã viết một phương trình tuyến tính mô tả
cách thức ngành phân phối sản lượng của mình cho các lĩnh vực khác của nền kinh tế. Bởi
vì Mark II, một trong những máy tính lớn nhất lúc bấy giờ, không thể xử lý hệ gồm 500
phương trình với 500 ẩn số, nên Leontief đã rút gọn bài toán thành một hệ gồm 42 phương
trình 42 ẩn số.
Lập trình cho máy tính Mark II với 42 phương trình của Leontief đã đòi hỏi một vài tháng
nỗ lực, và ông ấy lo lắng liệu máy tính sẽ mất bao lâu để giải bài toán. Mark II mất 56 giờ
để giải ra nghiệm. Chúng ta sẽ thảo luận về bản chất của nghiệm này trong các phần 1.6 và
2.6.
Leontief, người được trao giải Nobel về Khoa học Kinh tế năm 1973, đã mở cánh cửa đến
một kỷ nguyên mới của mô hình toán học về kinh tế học. Những nỗ lực của ông tại
Harvard năm 1949 đánh dấu một trong những lợi ích quan trọng đầu tiên của máy tính để
phân tích những mô hình toán học với quy mô lớn. Kể từ đó, các nhà nghiên cứu ở nhiều
lĩnh vực khác đã sử dụng máy tính để phân tích các mô hình toán học. Do số lượng lớn dữ
liệu liên quan với nhau, nên các mô hình thường là tuyến tính; nghĩa là chúng được mô tả
bằng hệ phương trình tuyến tính.
Tầm quan trọng của đại số tuyến tính đối với các ứng dụng đã tăng tỷ lệ thuận với sự gia
tăng sức mạnh tính toán, mỗi thế hệ phần cứng và phần mềm mới tạo ra nhu cầu về khả
năng lớn hơn. Khoa học máy tính do đó được liên kết phức tạp với đại số tuyến tính thông
qua sự phát triển bùng nổ của việc xử lý và tính toán quy mô lớn.
Các nhà khoa học và kỹ sư hiện đang làm việc với các bài toán phức tạp hơn nhiều so với
vài thập kỷ trước. Ngày nay, đại số tuyến tính có nhiều giá trị tiềm năng cho sinh viên
trong nhiều lĩnh vực khoa học và kinh doanh hơn bất kỳ môn toán học đại học nào khác!
1
Các kiến thức trong sách này cung cấp nền tảng cho công việc tiếp theo trong nhiều lĩnh
vực thú vị. Dưới đây là một vài khả năng; những cái khác sẽ được mô tả sau.
Thăm dò dầu. Khi một con tàu tìm kiếm các mỏ dầu ngoài khơi, thì các máy tính của nó giải
hàng ngàn hệ phương trình tuyến tính riêng biệt mỗi ngày. Dữ liệu địa chấn cho các
phương trình thu được từ sóng xung kích dưới nước được tạo ra bởi các vụ nổ từ súng
hơi. Những con sóng tung ra khỏi đá ngầm và được đo bằng geophones gắn liền với cáp
dài phía sau tàu.
Lập trình tuyến tính. Nhiều quyết định quan trọng ngày nay được thực hiện trên cơ sở các
mô hình tuyến tính sử dụng hàng
...
--------------------------------------
...trình
máy tính khác).
4. Có thể sử dụng khóa k 11, 13 như là một khóa trong hệ mã affine không?
5. Trong một hệ mã affine với một khóa chưa biết, Eve đoán rằng chữ cái F đã được mã hóa
thành N và chữ cái K đã được mã hóa thành O. Hãy giúp Eve tìm được chìa khóa mã này.
6. Một văn bản rõ (tiếng Anh) đã được mã hóa nhờ hệ mã aífine. Văn bản đã được mã hóa
nhận được là:
Hãy tìm văn bản gốc. Những ước lượng sau đây về tần suất của 26 chữ cái trong văn bản
tiếng Anh có thể giúp ích cho bạn. Bạn cũng được khuyến khích sử dụng bất kỳ sự trợ
giúp máy tính nào mà bạn cần.
7. (a) Ma trận nào sau đây là khả nghịch trong 26 , hãy tìm nghịch đảo của nó trong trường
hợp khả nghịch:
1 12 1 6
,
.
12 1 6 1
(b) Cho M là ma trận khả nghịch tìm được trong câu (a). Hãy sử dụng nó như là một khóa
trong hệ mật mã Hill để mã hóa YEAR và giải mã ROLK.
382
8.
11 12
, hãy tìm tất cả các cặp chữ cái XY mà không
12 11
Trong hệ mật mã Hill với khóa K
thay đổi sau khi được mã hóa hai lần, nghĩa là nếu chúng ta mã hóa XY được cặp ZT và
nó lại được mã hóa thành XY.
9. Bạn bắt được xâu ký tự đã được mã hóa là
NWOLBOTEPEHKICNSHR.
Bạn biết rằng nó được mã hóa bởi mật mã Hill với một ma trận 22 và biết 4 ký tự đầu
tiên của mẩu tin này là từ "DEAR". Hãy tìm khóa bí mật này và giải mã đoạn văn bản
trên.
10. Khóa của một hệ mã Hill trên 26 là mà trận
1 2 3 4 5
9 11 18 12 4
1 2 8 23 3 .
7 14 21 5 1
5 20 6 5 0
Hãy sử dụng một phần mềm tính toán để giải mã đoạn tin
WGVUUTGEPVRIMFTXMXMHCYTNGIMJJE
EZKEWHLQQISDJYJCTYEUBYKFBWPBBE
11. Hãy chứng minh rằng một ma trận vuông cấp n trên 26 là khả nghịch nếu và chỉ nếu
định thức của nó là một phần tử khả nghịc của 26 .
BÀI TẬP 8.6
1. Với các số nguyên tố được cho ở Ví dụ trên hãy cho biết số nào trong số hai số e1 2145
và e2 3861 có thể được dùng làm khóa công khai và tính khóa riêng cho nó.
2. Alice và Bob thống nhất dùng hệ mã RSA để liên lạc bí mật. Mỗi tin nhắn bao gồm một
ký tự đơn mà được mã hóa là
A 11, B 12,..., Z 36.
Khóa công khai của Bob là n , e 143 , 113 và Alice gửi cho anh ấy mẩu tin là 97. Ký tự
nào mà Alice gửi cho Bob trong tin nhắn này?
3. Cơ số của khóa công khai của Alice là e 41 và modulo là n 13337 . Có bao nhiêu phép
nhân mod n mà Bob cần để mã hóa tin nhắn của anh ấy là m 2619 ? (Không mã hóa
mà chỉ tính.)
4. Hãy tạo một hệ mã RSA cho riêng mình. Hãy tập trung vào giải thích cách có thể gửi
được tin cho bạn và cách mà bạn có thể giải mã chúng nhờ sử dụng khóa riêng của mình.
5. Alice và Bob có các khóa công khai RSA tương ứng là 20687 , 17179 và 20687 , 4913 .
Bob gửi một tin nhắn cho Alice, Eve đã tìm thấy một tin nhắn mã hóa là 353. Hãy giúp
Eve giải mã được tin nhắn này, với nghi ngờ rằng modulo 20687 là tích của hai số nguyên
383
tố có ba chữ số. Hãy thử làm điều này với những tính toán thông thường trước, sau đó
kiểm tra bằng một phần mềm máy tính.
6. Alice và Bob mã hóa tin nhắn của họ nhờ sử dụng phương pháp RSA. Khóa công khai của
Bob là n , e 24613 , 1003 .
a. Alice muốn gửi cho Bob tin nhắn m 183. Cô ấy sẽ phải gửi văn bản mã hóa nào?
b. Bob biết rằng n 24300 nhưng quên mất khóa riêng d của mình. Hãy giúp Bob
tính d.
c. Bob nhận được tin nhắn mã hóa 16935 từ Casey gửi cho anh ấy. Hãy chỉ cho anh ta
cách tìm được văn bản gốc.
7. Trong RSA Bob đã sử dụng một tích hai số nguyên tố lớn n và một cơ số đơn công khaie.
Để tăng tính bảo mật, anh ấy chọn hai cơ số công khai e1 và e2 mà cùng nguyên tố cùng
nhau với n . Anh ta yêu cầu Alice mã hóa tin nhắn của cô ấy hai lần: một lần sử dụng
cơ số thứ nhất, và sau đó sử dụng cơ số kia. Nghĩa là. Alice phải tính c1 m 1 mod n và
e
sau đó tính c2 c1 2 mod n và gửi c2 cho Bob. Anh ta cũng phải chuẩn bị hai cơ số để
e
giải mã tin nhắn của Alice. Liệu sự mã hóa hai lần này có tăng hơn nhiều tính bảo mật so
với việc mã hóa một lần?
8. Eve chặn được tin nhắn này từ Bob gửi cho Alice:
5272281348, 21089283929, 3117723025, 26844144908, 22890519533,
26945939925, 27395704341, 2253724391, 1481681985, 2163791130,
13583590307, 5838404872, 12165330281, 28372578777, 7536755222.
Trong miền công khai Eve biết được tin nhắn này đã được gửi bằng cách sử dụng sự mã
hóa theo modulo n pq 30796045883. Cô ta cũng nhận thấy rằng khóa công khai của
Alice là e 48611. Hãy giải mã tin nhắn này biết nó đã được mã hóa nhờ kiểu ghi mã
A 11, B 12,..., Z 36.
9. Eve đã chặn được tin nhắn sau từ Bob gửi cho Alice:
[ 427849968240759007228494978639775081809,
498308250136673589542748543030806629941,
925288105342943743271024837479707225255,
95024328800414254907217356783906225740 ]
Cô ta biết Bob đã sử dụng hệ mã RSA với modulo
n 956331992007843552652604425031376690367
và cơ số công khai của Alice là e 12398737. Cô ta cũng biết rằng để chuyển từ để chuyển
in nhắn của họ sang số, Bob và Alice luôn sử dụng kiểu ghi mã: cách trống = 00, A = 11, B
= 12,…, Z = 36. Hãy giúp Eve phá mã và giải mã tin nhắn.
384
