ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC
-------------------------------
DƢƠNG THỊ LAN HƢƠNG
VỀ MỘT SỐ THUẬT TOÁN PHÂN TÍCH
ĐA THỨC MỘT BIẾN THÀNH NHÂN TỬ
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2016
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC
-------------------------------
DƢƠNG THỊ LAN HƢƠNG
VỀ MỘT SỐ THUẬT TOÁN PHÂN TÍCH
ĐA THỨC MỘT BIẾN THÀNH NHÂN TỬ
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Phƣơng pháp Toán sơ cấp
Mã số: 60 46 01 13
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. Đoàn Trung Cƣờng
THÁI NGUYÊN - 2016
i
Mục lục
Danh sách ký hiệu iii
Mở đầu 1
Chương 1. Kiến thức chuẩn bị 4
1.1 Phân tích bất khả quy của đa thức . . . . . . . . . . . . . . . . . 4
1.2 Thuật toán chia đa thức . . . . . . . . . . . . . . . . . . . . . . . 7
Chương 2. Thu gọn mod pvà đa thức bất khả quy 11
2.1 Thu gọn mod pvà đa thức bất khả quy . . . . . . . . . . . . . . . 11
2.2 Tiêu chuẩn bất khả quy Eisenstein . . . . . . . . . . . . . . . . . 16
2.3 Trường hợp đa thức thu gọn P(X)không có nghiệm trong Fp. . . 24
2.4 Bàitậpđềnghị ........................... 26
Chương 3. Một số thuật toán phân tích đa thức thành nhân tử 28
3.1 Phân tích đa thức thành nhân tử . . . . . . . . . . . . . . . . . . . 28
3.2 Thuật toán Yun phân tích không bình phương . . . . . . . . . . . 32
3.2.1 Phân tích không bình phương . . . . . . . . . . . . . . . 32
3.2.2 ThuậttoánYun....................... 35
3.3 Phân tích nhân tử của đa thức trên trường hữu hạn Fp....... 38
3.3.1 Thuật toán tổng quát . . . . . . . . . . . . . . . . . . . . 38
3.3.2 Phân tích tách bậc . . . . . . . . . . . . . . . . . . . . . 40
3.3.3 Phân tích đồng bậc . . . . . . . . . . . . . . . . . . . . . 42
3.4 Phân tích bất khả quy trên Z[X]................... 44
ii
3.4.1 Chặn cho hệ số của các ước trong vành đa thức nguyên . . 44
3.4.2 Phân tích bất khả quy mod pe............... 48
3.4.3 Thuật toán Zassenhaus . . . . . . . . . . . . . . . . . . . 51
Kết luận 54
Tài liệu tham khảo 55
iii
Danh sách ký hiệu
Zvành các số nguyên
Qtrường các số hữu tỷ
Fptrường có pphần tử
K[X]vành đa thức với hệ số trên trường K
P(X)đa thức một biến X
degP(X)bậc của đa thức P(X)
mod pmodulo p
a6 | b a không là ước của b
gcd(P(X),Q(X)) ước chung lớn nhất của hai đa thức P(X)và Q(X)