Chuyên đề
THU T TOÁN S H CẬ Ố Ọ
Tác gi : Tr n quang Kh i ả ầ ả
I. Gi i thi u chungớ ệ
S h c thu t toán (Algorithmic number theory) là m t ngành toán h c đang phát tri n m nh, nghiênố ọ ậ ộ ọ ể ạ
c u s h c trên ph ng di n thu t toán. Ta c n chú ý r ng S h c là m t trong nh ng ngành toánứ ố ọ ươ ệ ậ ầ ằ ố ọ ộ ữ
h c c nh t còn thu t toán l i là m t khái ni m m i m ra đ i và phát tri n t trong th k XX. Sọ ổ ấ ậ ạ ộ ệ ớ ẻ ờ ể ừ ế ỉ ố
h c thu t toán đ c xây d ng trên c s nh ng thành t u c a c lý thuy t s h c l n thu t toán. ọ ậ ượ ự ơ ở ữ ự ủ ả ế ố ọ ẫ ậ
M t trong nh ng bài toán n i ti ng nh t đã đ oc gi i quy t trong th k XX là bài toán th 10ộ ữ ổ ế ấ ự ả ế ế ỉ ứ
c a Hilbertủ ‘Có t n t i m t thu t toán t ng quát cho phép ta tr l i m t ph ng trình Diophantineồ ạ ộ ậ ổ ả ờ ộ ươ
cho tr c có nghi m hay không ?ướ ệ ’. Ph ng trình Diophantine là ph ng trình có d ng f(x, y, z, … )ươ ươ ạ
= 0 trong đó f(x, y, z, …) là đa th c c a các bi n x, y, z, … có các h s nguyên, và các bi n chứ ủ ế ệ ố ế ỉ
nh n giá tr nguyên. Bài toán này đã đ c Michiakêvích gi i quy t tr n v n và câu tr l i là phậ ị ượ ả ế ọ ẹ ả ờ ủ
đ nh, t c là không có thu t toán nh v y. Bài toán th 10 c a Hilbert đ c gi i quy t là m t thànhị ứ ậ ư ậ ứ ủ ượ ả ế ộ
t u quan tr ng c a s h c cũng nh thu t toán. ự ọ ủ ố ọ ư ậ
S h c thu t toán không ch phát tri n trên nh ng thành t u c a S h c s c p, mà nó còn t nố ọ ậ ỉ ể ữ ự ủ ố ọ ơ ấ ậ
d ng nh ng thành t u c a S h c hi n đ i, Đ i s hi n đ i, Hình h c đ i s … Cũng nh cácụ ữ ự ủ ố ọ ệ ạ ạ ố ệ ạ ọ ạ ố ư
ngành toán h c - thu t toán khác, trong S h c thu t toán cũng có nh ng bài toán NP, t c là khôngọ ậ ố ọ ậ ữ ứ
có thu t gi i trong th i gian đa th c, tiêu bi u là bài toán phân tích m t s ra các th a s nguyên t ,ậ ả ờ ứ ể ộ ố ừ ố ố
thu t toán ki m tra nguyên t , … ậ ể ố
Trong bài vi t này, ta ch đ c p t i nh ng v n đ c b n nh t c a S h c thu t toán, và trên cế ỉ ề ậ ớ ữ ấ ề ơ ả ấ ủ ố ọ ậ ơ
s c a toán h c s c p. ở ủ ọ ơ ấ
II. Các phép tính v i s nguyênớ ố
Trong máy tính, các s đ u đ c bi u di n h nh phân, h n n a vi c mô t d i d ng nhố ề ượ ể ễ ở ệ ị ơ ữ ệ ả ướ ạ ị
phân làm cho các phép tính tr nên đ n gi n h n r t nhi u. ở ơ ả ơ ấ ề
Đ cho t ng quát, ta gi s hai toán h ng đ u có đúng N bit (trong tr ng h p s các bít có nghĩaể ổ ả ử ạ ề ườ ợ ố
nh h n N thì ta thêm 0 vào đ u cho đ ). ỏ ơ ầ ủ
1. Phép c ng và phép tr ộ ừ
Đ i v i phép c ng và phép nhân các s N bít, ta có th th c hi n gi ng nh phép c ng tr trên hố ớ ộ ố ể ự ệ ố ư ộ ừ ệ
th p phân : Th c hi n c ng (hay tr ) t ph i sang trái (v i bít ng v i s mũ nh tr c r i s mũậ ự ệ ộ ừ ừ ả ớ ứ ớ ố ỏ ướ ồ ố
l n sau). ớ
1. Phép nhân
Đ i v i phép nhân, ta có thu t toán nhân Nga đ c mô t nh sau : ố ớ ậ ượ ả ư
Function Mult(a, b : Integer): Integer;
Var
c : Integer;
Begin
c := 0;
repeat
if Odd(b) then c := c + a;
a := a shl 1;
b := b shr 1;
until b = 0;
Mult := c;
End;
N u xét cho kĩ thì th c ra thu t toán nhân Nga có cùng m t d ng v i thu t toán nhân hai s b ngế ự ậ ộ ạ ớ ậ ố ằ
ph ng pháp mà bình th ng ta v n dùng đ tính tay, ch có đi u khác là thao tác trên h nh phân. ươ ườ ẫ ể ỉ ề ệ ị
Thu t toán nhân Nga g m N l n d ch bít, trong tr ng h p t ng quát ph i th c hi n N/2 l n phépậ ồ ầ ị ườ ợ ổ ả ự ệ ầ
c ng, do đó đ ph c t p tính toán là Nộ ộ ứ ạ 2.
Sau đây, ta s gi i thi u m t thu t toán nhân khác, tuy ph c t p h n nh ng có đ ph c t p nhẽ ớ ệ ộ ậ ứ ạ ơ ư ộ ứ ạ ỏ
h n. ơ
Gi s ta ph i th c hi n phép nhân v i hai s có 2N bit A và B. Phân tích : ả ử ả ự ệ ớ ố
A = a1*2N + a2
B = b1*2N + b2.
AB = a1*b1 * 22N + (a1b2 + a2b1)*2N + a2b2.
Ta chú ý r ng phép nhân v i m t lu th a c a 2 cũng nh phép c ng có th i gian t l v i N. ằ ớ ộ ỹ ừ ủ ư ộ ờ ỉ ệ ớ
Nh n xét : (a1+a2)(b1 + b2) - a1b1 - a2b2 = a1b2 + a2b1. ậ
Do đó n u bi t (a1+a2)(b1 + b2), a1b1, a2b2 thì có th tính đ c a1b2 + a2b1. ế ế ể ượ
→ Qui v nhân hai s 2N bit v 2 l n nhân N bit và m t s phép tính có th i gian t l v i N. ề ố ề ầ ộ ố ờ ỉ ệ ớ
N u g i F(n) là th i gian nhi u nh t đ th c hi n phép nhân hai s có 2ế ọ ờ ề ấ ể ự ệ ố n bit, ta có
F(n) = 3F(n-1) + k2n (*) trong đó k là m t h ng s th hi n chi phí các phép tính c ng và d ch bitộ ằ ố ể ệ ộ ị
trong m i b c g i đ qui. Chia c hai v c a (*) cho 2ỗ ướ ọ ệ ả ế ủ n ta đ c ượ
. Do đó, F(n) = O(3n) = O( ) hay nói cách khác th i gian th c hi nờ ự ệ
phép nhân hai s N bít có đ ph c t p c O(ố ộ ứ ạ ỡ ).
3. Phép chia
Trong ph n này, ta s trình bày thu t toán chia hai s nh phân có N bít A = (A1A2A3…AN)ầ ẽ ậ ố ị 2, B =
(B1B2…BN)2 cho k t qu th ng Q, d R. ế ả ươ ư
+B c 1:Q ướ ← 0, R ← 0, i ← 0
+B c 2: i = i+1. N u i > N ướ ế → k t thúc thu t toán, ng c l i ế ậ ượ ạ → B c 3. ướ
+B c 3: R ướ ← (R shl 1) or (A[i]). N u R ế≥ B → B c 4, ng c l i B c 5. ướ ượ ạ ướ
+B c 4: R ướ ← R - B, C[i] = 1. Th c hi n B c 2. ự ệ ướ
+B c 5: C[i] = 0. Th c hi n B c 2. ướ ự ệ ướ
Hay ta có th mô t b ng ch ng trình : ể ả ằ ươ
Procedure Divide(A, B : LongInt; var Q, R : LongInt);
Var
i : Integer;
Begin
Q := 0;
R := 0;
For i := 1 to N do
Begin
If (A and (1 shl (N-i)) <> 0) then R := (R shl 1)+1
else R := R shl 1;
if R >= B then
Begin
Q := Q or (1 shl (N-i));
R := R - B;
End;
End;
End;
Đánh giá đ ph c t pộ ứ ạ : Thu t toán chia có đ ph c t p (Nậ ộ ứ ạ 2).
III. Thu t toán Euclidậ
1. Thu t toán Euclidậ
Thu t toán Euclid dùng đ tìm c chung l n nh t c a hai s nguyên d ng m, n. ậ ể ướ ớ ấ ủ ố ươ
Thu t toán ti n hành nh sau :ậ ế ư
B c 0: Đ t a = m, b = n. ướ ặ
B c 1:ướ N u a > b ta thay a b ng ph n d c a phép chia a cho b, ng c l i thay b b ng ph n dế ằ ầ ư ủ ượ ạ ằ ầ ư
c a phép chia b cho a. ủ
B c 2: N u a ho c b b ng 0, thì k t qu là a + b, ng c l i th c hi n b c 1. ướ ế ặ ằ ế ả ượ ạ ự ệ ướ
Hay thu t toán đ c mô t b ng m t hàm trong ngôn ng Pascal nh sau : ậ ượ ả ằ ộ ữ ư
Function Euclid(m, n : Integer) : Integer;
Var
a, b : Integer;
Begin
a := m; b := n;
repeat
if a > b then a := a mod b
else b := b mod a;
until (a = 0) or (b = 0);
Euclid := a + b;
End;
Ta cũng có cách vi t khác nh sau : ế ư
Function Euclid1(m, n : Integer) : Integer;
Var
a, b, r : Integer;
Begin
a := m; b := n;
repeat
r := a mod b;
a := b;
b := r;
until b = 0;
Euclid := a;
End;
Trong s h c ta đã bi t r ng v i hai s nguyên d ng m, n b t kì và d là c chung c a chúng thìố ọ ế ằ ớ ố ươ ấ ướ ủ
luôn t n t i hai s nguyên u, v sao cho u*m + v*n = d. T thu t toán Euclid ta cũng có th ch raồ ạ ố ừ ậ ể ỉ
đ c c th m t c p (u, v) nh v y : ượ ụ ế ộ ặ ư ậ
Ta chú ý r ng t i m i b c c a vòng l p repeat, a và b đ u t n t i c p (x, y) v i x, y ằ ạ ỗ ướ ủ ặ ề ồ ạ ặ ớ ∈ Z thoả
mãn x*m + y*n = a (= b). Ban đ u a = m có m t c p t ng ng là (1, 0), c p t ng ng v i b = nầ ộ ặ ươ ứ ặ ươ ứ ớ
là (0, 1) vì :
1*m + 0*n = m = a
0*m + 1*n = n = b
Trong vòng l p, ta có phép gán a := a mod b, phép gán này t ng đ ng a := a - q*b trong đó q làặ ươ ươ
th ng c a phép chia a cho b (q := a div b). Khi đó c p (xươ ủ ặ a, ya) t ng ng v i a bi n đ i t ng ng ươ ứ ớ ế ổ ươ ứ
xa := xa - q*xb
ya := ya - q*yb
Nh v y, a và b luôn có th bi u di n d i d ng x*m + y*n và k t qu c chung b ng a + b sư ậ ể ể ễ ướ ạ ế ả ướ ằ ẽ
có c p x, y t ng ng là xặ ươ ứ a + xb , ya + yb. Nh v y, thu t toán tìm c p u, v trên c s thu t toánư ậ ậ ặ ơ ở ậ
Euclid s đ c vi t nh sau : ẽ ượ ế ư
Procedure Euclid2(m, n : Integer; var u, v : Integer);
Var
a, b, q, r : Integer;