Giáo trình Số học thuật toán - Chương 5: Trường và đa thức

ó thể xuất phát từ đa thức bất khả quy tuỳ ý. Các tr−ờng nhận đ−ợc có số phần tử 
nh− nhau , và đẳng cấu với nhau. 
Ta minh hoạ những điều nói trên qua ví dụ cụ thể. 
Ví dụ. Xây dựng tr−ờng F16 từ tr−ờng F2 bởi đa thức 
P(x)=x4+x3+x2+x+1. 
Đa thức đang xét là một đa thức bất khả quy trên tr−ờng F2. Thật vậy, nếu nó có −ớc 
khác hằng số thì phải có −ớc là đa thức bậc 1 hoặc bậc 2. Nếu −ớc là đa thức bậc 1, 
P(x) có nghiệm trong F2: điều này không xảy ra vì P(0)=P(1)=1. Có bốn đa thức bậc 
2 trên F2 đó là các đa thức x
2, x2+1, x2+x, x2+x+1. Thử trực tiếp cho thấy rằng 
không có cặp đa thức nào có tích bằng P(x). 
Các phần tử của F16 là các đa thức bậc bé hơn hoặc bằng 3, với hệ số 0 hoặc 1: 
-Bậc 0: 0,1. 
-Bậc 1: x, x+1. 
-Bậc 2: x2, x2+1, x2+x, x2+x+1. 
-Bậc 3: x3, x3+1, x3+x, x3+x2, x3+x+1, x3+x2+x+1, x3+x
2+x, x3+x2+x+1. 
 88
Quy tắc cộng và nhân là quy tắc cộng và nhân thông th−ờng của các đa thức, với chú 
ý 1+1=0 và x4=-(x3+x2+x+1). 
Trong nhiều ứng dụng, chẳng hạn trong lí thuyết thông tin, ng−ời ta th−ờng viết các 
phần tử của tr−ờng Fq theo các hệ số của chúng. Nh− trong ví dụ trên đây, các phần 
tử của tr−ờng sẽ là: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 
1010, 1100, 1001, 1101, 1110, 1111, cùng với một bảng để cho quy tắc cộng và 
nhân của chúng. Chú ý rằng, các quy tắc này khác với các quy tắc số học đồng d− 
modulo q. 
Khi biết một phần tử sinh của tr−ờng Fq, ta có thể tìm các phần tử khác bằng cách 
nâng lên luỹ thừa. Sau đây, ta sẽ tìm hiểu một thuật toán thời gian đa thức để làm 
việc đó. Thuật toán này sẽ đ−ợc áp dụng trong những ch−ơng sau. 
Tr−ớc khi đi vào mô tả thuật toán, để dễ hình dung, ta xét ví dụ sau đây. Giả sử ta 
cần tính (1994)23(mod 4611). Nếu dùng cách thông th−ờng (tính lần l−ợt các luỹ thừa 
của 1994), ta phải làm 22 phép nhân và 22 phép chia. Để giảm bớt số phép tính phải 
làm, ta dùng ph−ơng pháp bình ph−ơng liên tiếp nh− sau. Ta có: 
(1994)23=(1994)16+4+2+1 
Nh− vậy, ta chỉ cần tính modulo của các luỹ thừa 1,2,4,8,16 của 1994. Nói cách 
khác, ta chỉ cần làm phép bình ph−ơng liên tiếp 4 lần, sau đó nhân các kết quả ở 
những luỹ thừa nào t−ơng ứng với số 1 trong biểu diễn số 23 d−ới dạng cơ số 2. Ta 
có 23=(10111)2, nên ta nhân kết quả của những luỹ thừa 16,4,2,1. 
Cách làm nh− trên áp dụng đ−ợc cho mọi nhóm nhân. Giả sử g∈G là phần tử của 
nhóm nhân G nào đó, ta cần tính gn, với n là số tự nhiên. Ta viết n d−ới dạng cơ số 2: 
n= ε∑ i2i, trong đó ε = ± 1. Khi đó ta tính 
gn= ( )gi
iε =
∏
1
. 
Thuật toán. 
S1. (Xuất phát) đặt y←1. Nếu n=0, thuật toán kết thúc. 
Nếu ng−ợc lại, đặt N←n, z←g. 
S2. (Nhân). Nếu N lẻ, đặt y←z.y. 
S3. (Chia đôi N). Đặt N←[N/2]. Nếu N=0, in ra y và kết 
thúc thuật toán. Ng−ợc lại, đặt z←z.z và quay về S2. 
Có thể chứng minh tính đúng đắn của thuật toán với nhận xét rằng, từ b−ớc thứ hai 
trở đi, ta luôn luôn có gn=y.zN. 
 Ta sẽ đánh giá độ phức tạp của thuật toán nói trên. 
Số phép nhân phải làm bằng số chữ số của n, cộng thêm số chữ số 1 trong cách viết 
nhị phân của n, và trừ đi 1. Nh− vậy, số phép nhân không v−ợt quá 2[log n]+1, tức là 
O(log n). Nếu ta tính trong lớp đồng d− modulo m nào đó, mỗi phép nhân đòi hỏi 
O(log2 m) phép tính bit, và toàn bộ số phép tính bit cần thiết sẽ là O(log nlog2 m). 
 89
Nh− ta đã thấy ở trên, để thực hiện các phép tính trên tr−ờng Fq, ta phải làm các phép 
tính đối với các đa thức. Sau đây là vài thuật toán để thực hiện các phép tính đó. 
Thuật toán chia 
 Xét các đa thức với hệ số trong tr−ờng K tuỳ ý. Với mỗi đa thức P, kí hiệu qua l(P) 
hệ số của luỹ thừa cao nhất. Ta có thuật toán để, với đa thức đã cho A, B, B≠ 0, tìm 
các đa thức Q, R sao cho A=BQ+R, và deg R<deg B: 
C1. (Xuất phát). Đặt R←A, Q←0. 
C2. (Kết thúc?). Nếu deg R<deg B, kết thúc thuật toán. 
C3.(Tìm hệ số). Đặt S← l R
l B
( )
( )
xdeg R-deg B. Sau đó, đặt Q←Q+S, 
R←R-S.B, và chuyển sang b−ớc C2. 
Ta cần l−u ý ngay một điều. Về mặt lí thuyết, sau b−ớc S3, bậc của R phải giảm (vì 
hệ số của xdeg R sẽ bằng 0 do định nghĩa của S). Tuy nhiên, khi làm việc trên máy, 
thực tế là ta chỉ có các số gần đúng, nên có thể xảy ra tr−ờng hợp hệ số của xdeg R tuy 
rất nhỏ, nh−ng khác không, nghĩa là bậc không giảm, và do đó không bảo đảm là 
thuật toán kết thúc! Vì thế, khi viết ch−ơng trình, nhất thiết phải để hệ số đó bằng 0 
sau phép tính R←R-S.B. 
Để tìm −ớc chung lớn nhất của các đa thức, ta có thuật toán Euclid sau đây. 
Thuật toán 
 Cho các đa thức A,B, tìm ƯCLN của A,B. 
EP1. (Kết thúc?) Nếu B=0, in ra A và kết thúc thuật 
toán. 
EP2. (B−ớc Euclid). Giả sử A=BQ+R, với deg R<deg B (tính 
bằng thuật toán C trình bày ở trên). Đặt A←B, B←R, và 
quay về b−ớc EP1. 
Định lí 5.4. Có thể nhân hoặc chia hai phần tử của tr−ờng Fq với O(log3 q) phép tính 
bit. Nếu k là số nguyên d−ơng thì một phần tử của Fq có thể nâng lên luỹ thừa k với 
O(log klog3 q) phép tính bit. 
Chứng minh. Giả sử Fq đ−ợc xây dựng bằng cách nâng tr−ờng Fp bởi đa thức bất khả 
quy P(x) bậc r. Khi đó, các phần tử của tr−ờng Fq chính là các đa thức với hệ số 
trong tr−ờng Fp modulo đa thức P(x). Để nhân hai phần tử của tr−ờng Fq, ta phải 
nhân hai đa thức nh− vậy. Để làm việc đó, ta phải thực hiện O(r2) phép nhân modulo 
p (vì các đa thức có bậc nhỏ hơn r), cùng với một số phép tính cộng. Các phép này 
đòi hỏi thời gian ít hơn. Sau khi có kết quả của phép nhân, ta lại phải tính “modulo 
đa thức P(x)”, nghĩa là làm phép chia cho đa thức P(x) để biết đ−ợc phần d−. Phép 
chia đa thức này đòi hỏi O(r) phép chia các số nguyên modulo p và O(r2) phép nhân 
các số nguyên modulo p Nh− ta đã biết, mỗi phép nhân số nguyên modulo p có thể 
thực hiện bằng O(log2 p) phép tính bit , còn mỗi phép chia modulo p có thể làm 
(chẳng hạn, dùng thuật toán Euclid) với O(log3 p) phép tính bit. Nh− vậy, toàn bộ số 
 90
phép tính bit đ−ợc thực hiện khi nhân hai phần tử của tr−ờng Fq là: 
O(r2log2 p+rlog3 p)=O((rlogp)3)=O(log3 q). Khẳng định của định lí đ−ợc chứng 
minh đối với phép nhân. 
Xét phép chia các phần tử của Fq. Để chứng minh rằng có thể hiện phép chia sau 
O(log3 q) phép tính bit, ta chỉ cần chứng tỏ rằng, nghịch đảo của một phần tử tìm 
đ−ợc bởi O(log3 q) phép tính bit, rồi áp dụng kết quả đã chứng minh đối với phép 
nhân. 
Giả sử ta cần tìm nghịch đảo của phần tử Q∈Fq (là một đa thức bậc nhỏ hơn r, hệ số 
trong Fp). Dùng thuật chia Euclid cho các đa thức trên tr−ờng Fq, ta cần biểu diễn 1 
nh− là tổ hợp tuyến tính của đa thức P(x) và Q(x). Điều này làm đ−ợc bởi O(r) phép 
chia các đa thức bậc nhỏ hơn r. Mỗi phép chia nh− vậy cần 
O(r2log2 p+rlog3 p)=O(r2log3 p) phép tính bit. Nh− vậy, ta cần tất cả là 
O(r3log3 p)=O(log3 q) phép tính bit, điều phải chứng minh. 
Còn phải xét phép tính nâng lên luỹ thừa bậc k. Ta có thể dùng ph−ơng pháp bình 
ph−ơng liên tiếp, và nh− vậy, số phép nhân và bình ph−ơng cần thực hiện là O(log k). 
Số phép tính bit cần thiết trong tr−ờng hợp này là O(log klog3 q). Định lí đ−ợc chứng 
minh. 
Đ4. Sự t−ơng tự giữa số nguyên và đa thức. 
Sự phát triển của số học, đặc biệt là trong những thập kỉ gần đây, chịu ảnh h−ởng rất 
lớn của sự t−ơng tự giữa số nguyên và đa thức. Nói cách khác, khi có giả thuyết nào 
đó ch−a chứng minh đ−ợc đối với các số nguyên, ng−ời ta cố gắng chứng minh sự 
kiện t−ơng tự cho các đa thức. Điều đó th−ờng dễ làm hơn, có lẽ nguyên nhân chủ 
yếu là vì, đối với các đa thức, ta có phép tính đạo hàm, trong khi một khái niệm 
t−ơng tự ch−a có đối với các số nguyên. 
Trong tiết này, chúng tôi cố gắng thông qua một vài ví dụ đơn giản, minh họa vai trò 
quan trọng của sự t−ơng tự nói trên trong các nghiên cứu về số học. 
Tr−ớc hết, chúng ta thấy rõ, giữa tập hợp các số nguyên và tập hợp các đa thức có 
những tính chất rất giống nhau sau đây: 
1) Các qui tắc cộng, trừ, nhân, chia hoàn toàn nh− nhau cho cả hai tập hợp. 
2) Nếu đối với các số nguyên, ta có các số nguyên tố, thì với các đa thức, ta có các 
đa thức bất khả quy. 
3) Đối với hai số nguyên, cũng nh− đối với hai đa thức, có thể định nghĩa −ớc chung 
lớn nhất. Hơn nữa, trong cả hai tr−ờng hợp, −ớc chung lớn nhất này tìm đ−ợc bằng 
thuật toán Euclid. 
4) Mỗi số nguyên có phân tích thành các thừa số nguyên tố, mỗi đa thức có phân tích 
thành các đa thức bất khả quy. 
5) Các số hữu tỷ t−ơng ứng với các hàm hữu tỷ. 
 91
Chúng tôi dành cho độc giả việc kéo dài bảng danh sách này. ở đây, chúng tôi sẽ đi 
vào một vài t−ơng tự khó nhìn thấy hơn. 
Ta để ý đến sự t−ơng tự giữa phân tích ra thừa số nguyên tố và phân tích bất khả quy. 
Nếu giả thiết rằng tr−ờng k là đóng đại số, thì mỗi đa thức Q(x) ∈ k[x] có thể phân 
tích đ−ợc d−ới dạng sau: 
Q(x)= P a1 1 P P
a
n
an
2
2 ... , 
trong đó Pi(x)=(x-α i), α i ∈k. 
Nh− vậy, có thể thấy rằng, trong sự t−ơng tự giữa phân tích bất khả quy và phân tích 
ra thừa số nguyên tố các nghiệm của đa thức t−ơng ứng với các −ớc nguyên tố của số 
nguyên. Do đó, số các nghiệm phân biệt của một đa thức có vai trò t−ơng tự nh− số 
các −ớc nguyên tố của một số nguyên. Từ nhận xét đó, ta đi đến định nghĩa sau đây. 
Định nghĩa 5.5. Cho a là một số nguyên. Ta định nghĩa căn của a, kí hiệu qua 
N0(a), là tích các −ớc nguyên tố của a: 
N0(a)= p
p a|
∏ . 
Ta sẽ thấy rằng, sự t−ơng tự trên đây cùng với các tính chất của đa thức gợi mở một 
con đ−ờng nhiều hy vọng để đi đến chứng minh định lí Fermat. 
Năm 1983, R. C. Mason chứng minh định lí rất đẹp sau đây về các đa thức. 
Định lí 5.6. Giả sử a(t), b(t), c(t) là các đa thức với hệ số phức, nguyên tố cùng nhau 
từng cặp và thoả mãn hệ thức 
a(t)+ b(t)= c(t) 
Khi đó, nếu kí hiệu qua n0(f) số nghiệm phân biệt của một đa thức f, thì ta có 
max{ deg a, deg b, deg c}≤n0(abc)-1. 
Tr−ớc khi đi vào chứng minh định lí, ta chứng minh hệ quả sau đây của định lí 
Mason. 
Hệ quả 5.7. Không tồn tại các đa thức a, b, c, khác hằng số, nguyên tố cùng nhau, 
thoả mãn ph−ơng trình 
an + bn = cn 
với n≥3. 
Chứng minh. Gỉa sử các đa thức a, b, c thoả mãn ph−ơng trình nói trê