Chuyên đề thuật toán số học

Chuyên đề THU TOÁN CẬ Chuyên đềTHU TOÁN CẬ I. Gi thi chungớ thu toán (Algorithmic number theory) là ngành toán đang phát tri nh, nghiên ạc trên ph ng di thu toán. Ta chú ng là trong nh ng ngành toán ươ ữh nh còn thu toán là khái ni ra và phát tri trong th XX. ốh thu toán xây ng trên nh ng thành lý thuy thu toán. ượ trong nh ng bài toán ti ng nh đã oc gi quy trong th XX là bài toán th 10 ức Hilbertủ Có thu toán ng quát cho phép ta tr ph ng trình Diophantine ươcho tr có nghi hay không ?ướ ’. Ph ng trình Diophantine là ph ng trình có ng f(x, y, z, ươ ươ ạ= trong đó f(x, y, z, …) là đa th các bi x, y, z, có các nguyên, và các bi ch ỉnh giá tr nguyên. Bài toán này đã Michiakêvích gi quy tr và câu tr là ph ượ ủđ nh, là không có thu toán nh y. Bài toán th 10 Hilbert gi quy là thành ượ ột quan tr ng cũng nh thu toán. thu toán không ch phát tri trên nh ng thành p, mà nó còn ậd ng nh ng thành hi i, hi i, Hình Cũng nh các ưngành toán thu toán khác, trong thu toán cũng có nh ng bài toán NP, là không ứcó thu gi trong th gian đa th c, tiêu bi là bài toán phân tích ra các th nguyên ,ậ ốthu toán ki tra nguyên Trong bài vi này, ta ch nh ng nh thu toán, và trên ơs toán p. ấII. Các phép tính nguyênớ Trong máy tính, các bi di nh phân, vi mô ng nh ượ ướ ịphân làm cho các phép tính tr nên gi nhi u. cho ng quát, ta gi hai toán ng có đúng bit (trong tr ng các bít có nghĩa ườ ốnh thì ta thêm vào cho ). 1. Phép ng và phép tr phép ng và phép nhân các bít, ta có th th hi gi ng nh phép ng tr trên ệth phân Th hi ng (hay tr ph sang trái (v bít ng mũ nh tr mũ ướ ốl sau). 1. Phép nhân phép nhân, ta có thu toán nhân Nga mô nh sau ượ ưFunction Mult(a, Integer): Integer; Var 1Giáo viên: Võ Tá HoàngChuyên đề THU TOÁN CẬ Integer; Begin := 0; repeat if Odd(b) then := a; := shl 1; := shr 1; until 0; Mult := c; End; xét cho kĩ thì th ra thu toán nhân Nga có cùng ng thu toán nhân hai ng ằph ng pháp mà bình th ng ta dùng tính tay, ch có đi khác là thao tác trên nh phân. ươ ườ Thu toán nhân Nga ch bít, trong tr ng ng quát ph th hi N/2 phép ườ ầc ng, do đó ph tính toán là Nộ 2. Sau đây, ta gi thi thu toán nhân khác, tuy ph nh ng có ph nh ỏh n. Gi ta ph th hi phép nhân hai có 2N bit và B. Phân tích a1*2 a2 b1*2 b2. AB a1*b1 2N (a1b2 a2b1)*2 a2b2. Ta chú ng phép nhân lu th cũng nh phép ng có th gian N. Nh xét (a1+a2)(b1 b2) a1b1 a2b2 a1b2 a2b1. Do đó bi (a1+a2)(b1 b2), a1b1, a2b2 thì có th tính a1b2 a2b1. ượ Qui nhân hai 2N bit nhân bit và phép tính có th gian N. ớN F(n) là th gian nhi nh th hi phép nhân hai có 2ế bit, ta có F(n) 3F(n-1) k2 (*) trong đó là ng th hi chi phí các phép tính ng và ch bit ịtrong qui. Chia hai (*) cho 2ỗ ướ ta ượ2Giáo viên: Võ Tá HoàngChuyên đề THU TOÁN CẬ Do đó, F(n) O( n) O( hay nói cách khác th gian th hi ệphép nhân hai bít có ph O(ố ). 3. Phép chia Trong ph này, ta trình bày thu toán chia hai nh phân có bít (A1A2A3…AN)ầ ị2 (B1B2…BN)2 cho qu th ng Q, R. ươ +B 1:Q ướ 0, 0, +B 2: i+1. ướ thúc thu toán, ng ượ 3. ướ +B 3: ướ (R shl 1) or (A[i]). 4, ng 5. ướ ượ ướ +B 4: ướ B, C[i] 1. Th hi 2. ướ +B 5: C[i] 0. Th hi 2. ướ ướHay ta có th mô ng ch ng trình ươProcedure Divide(A, LongInt; var Q, LongInt); Var Integer; Begin := 0; := 0; For := to do Begin If (A and (1 shl (N-i)) 0) then := (R shl 1)+1 else := shl 1; if >= then Begin := or (1 shl (N-i)); := B; 3Giáo viên: Võ Tá HoàngChuyên đề THU TOÁN CẬ End; End; End; Đánh giá ph pộ Thu toán chia có ph (Nậ 2). III. Thu toán Euclidậ 1. Thu toán Euclidậ Thu toán Euclid dùng tìm chung nh hai nguyên ng m, n. ướ ươThu toán ti hành nh sau :ậ 0: m, n. ướ 1:ướ ta thay ng ph phép chia cho b, ng thay ng ph ượ ưc phép chia cho a. 2: ho ng 0, thì qu là b, ng th hi 1. ướ ượ ướHay thu toán mô ng hàm trong ngôn ng Pascal nh sau ượ ưFunction Euclid(m, Integer) Integer; Var a, Integer; Begin := m; := n; repeat if then := mod else := mod a; until (a 0) or (b 0); Euclid := b; End; Ta cũng có cách vi khác nh sau Function Euclid1(m, Integer) Integer; 4Giáo viên: Võ Tá HoàngChuyên đề THU TOÁN CẬ Var a, b, Integer; Begin := m; := n; repeat := mod b; := b; := r; until 0; Euclid := a; End; Trong ta đã bi ng hai nguyên ng m, kì và là chung chúng thì ươ ướ ủluôn hai nguyên u, sao cho u*m v*n d. thu toán Euclid ta cũng có th ch ra ỉđ th (u, v) nh ượ Ta chú ng vòng repeat, và (x, y) x, ướ tho ảmãn x*m y*n (= b). Ban có ng ng là (1, 0), ng ng nầ ươ ươ là (0, 1) vì 1*m 0*n 0*m 1*n Trong vòng p, ta có phép gán := mod b, phép gán này ng ng := q*b trong đó là ươ ươth ng phép chia cho (q := div b). Khi đó (xươ ặa ya ng ng bi ng ng ươ ươ xa := xa q*xb ya := ya q*yb Nh y, và luôn có th bi di ng x*m y*n và qu chung ng ướ ướ ẽcó x, ng ng là xặ ươ ứa xb ya yb Nh y, thu toán tìm u, trên thu toán ậEuclid vi nh sau ượ ưProcedure Euclid2(m, Integer; var u, Integer); Var a, b, q, Integer; 5Giáo viên: Võ Tá HoàngChuyên đề THU TOÁN CẬ xa, ya, xb, yb, xt, yt Integer; Begin := m; := n; xa := 1; ya := 0; xb := 0; yb := 1; repeat := div b; := mod b; := b; := r; xt := xa; yt := ya; xa := xb; ya := yb; xb := xt q*xb; yb := yt q*yb; until 0; := xa; := ya; End; Đánh giá ph thu toán Euclidộ ta (aế ọi bi là a, vòng th i, đánh ốtheo chi ng thúc là (aề ượ ế1 b1 ), tr đó làướ (a2 b2 ), (a3 b3 (as bs )). Ta có th ch ng ứminh ng qui max{aằ ạk bk Fk trong đó Fk là th trong dãy Fibonaci. Ta có công th sau ứ6Giáo viên: Võ Tá HoàngChuyên đề THU TOÁN CẬ Fn Fn tăng theo hàm mũ, thu toán Euclid có ph lôgarit max(m, n). ủTa chú ng cách đánh giá này qua th gian th hi phép chia (mod) (trong máy tính đây là ệm nh CPU), tuy nhiên thu toán chia th hi hai bít nói chung kho ng Nộ 2. Do đó xét chi ti t, thu toán Euclid có ph O((log(max{m, n})ế 3). 2. Thu toán Euclid nh phânậ Sau đây, ta trình bày ng Quay 1. ướ 3ướ Ch ng nào khác thu toán Euclid có ph nh n. Ta có nh xét sau ậc chung nh hai a, không ph thu vào các phép bi sau ướ Chia (ho b) (ho b) ch n. Thay ng b. Thu toán có th mô nh sau 0ướ m, n, dem 0. 1ướ và ch thì ng ướ ượ 3. ướ 2ướ dem dem 1, chia và cho 2,ả còn ch thì chia cho 2, th hi ng ươ ựv b. 4ướ 6, ng ướ ượ 5.; ướ 5ướ := b, ng ượ := a. Th hi 3. ướ 6ướ := dem ch sanh trái bit ng dem Thu toán thúc và là chung ướl nh tìm. ầTa có th môt ng ch ng trình Pascal nh sau ươ ưFunction BinaryEuclid(m, Integer) Integer; Var a, b, dem Integer; Begin := m; := n; 7Giáo viên: Võ Tá HoàngChuyên đề THU TOÁN CẬ dem := 0; while (not Odd(a)) and (not Odd(b)) do begin Inc(dem); := shr 1; := shr 1; end; repeat while not Odd(a) do := shr 1; while not Odd(b) do := shr 1; if then Break; if then := else := a; until b; BinaryEuclid := shl dem; End; Vì các mô ng nh phân nên rõ ràng các phép chia có th th hi gi ướ ướ ảb ng phép ch ph i. m, có th mô ng bít thì phép ch có chi phí ng N, phép tr ừcũng có chi phí ng (xem ph II). khác, sau phép tr là ít nh phép ch bít và ta ịd th có không quá 2N ch bit. Do đó ph thu toán Nễ hay log(max{m, n}) 2. Ta cũng chú ng phép mod là nh th ng nên các m, không quá ớ(trong ph vi 2ạ 31) thì thu toánậ Euclid ch nhanh thu toán mô đây. Còn ởkhi ta ph làm vi các thì thu toán Euclid nh phân thích n. Thu toán này ậkhông ch có ph nh mà có th khác là ta ch ph th hi phép ch bít và ịphép tr là nh ng phép tính gi n, trong khi thu toán Euclidừ ph th hi phép chia vi ếkhá ph p. ạIV. Gi ph ng trình nghi nguyên tuy tínhả ươ 1. Ph ng trình ng ax ươ b(mod c) (*) iớ a, b, là các nguyên ng. ươ8Giáo viên: Võ Tá HoàngChuyên đề THU TOÁN CẬ là chung nh và c. qu cho ta ph ng trình có nghi khi và ướ ươ ệch khi chia và (*) có nghi thì có vô nghi ng xỉ ạ0 Z, và x0 là nghi (*). Nh y, ta có th dàng ki tra ph ng trình có nhi hay ươ ệkhông. còn là tìm nghi xấ ệ0 tho mãn ph ng trình. Ta chú ng thu toán Euclid có ươ ậth chí ra hai u, sao cho *a d, là u*a (mod c) xế0 (b d) (chú ph ng trình có nghi ươ chia cho d) thì a*xế0 (mod c), là xứ0 tho mãn (*). ảCh ng trình Pascal gi ph ng trình (*) nh sau ươ ươ ưProcedure Solve1(a, b, Integer); Var d, e, b1, u, Integer; Begin Euclid2(a, c, u, v); := u*a v*c; if mod then Writeln(‘No solution ’) else begin := div d; b1 := div d; Writeln(‘Equation has infinite solution’); Write(‘All solutions have form ); Writeln(‘ ’, u*b1 ,‘ k*‘, e); end; End; 2. Ph ng trình Diophantine tuy tính ng a*x b*y cươ (**) a, b, Ta có th th ph ng trình Diophantine này có th gi ph ng trình ng tuy ươ ươ ếtính. 9Giáo viên: Võ Tá HoàngChuyên đề THU TOÁN CẬ (**) Vi gi ph ng trình ng tuy tính đã trình bày 1. ươ ựơ Chú UCLN(a, b) a1 b1 (**) có nghi khi và ch khiệ (mod d). (**) có nghi thì có vô nghi m, công th nghi (x, y) (x0 y0 (-b1 a1 ). iớ (x0 y0 là nghi nào đó (**). 3. nh lý ng Trung Hoaị nh lýị Cho nguyên ng aố ươ1 a2 a3 am đôi nguyên cùng nhau, và nguyên bộ ố1 b2 b3 bm tho mãn bi ai i= 1, 2, …, m. aặ1 *a2 *…*am. Khi đó và duy nh nguyên tho mãn và bi (mod ai 1, 2, …, m. nh lý ng Trung Hoa trình bày và ch ng minh trong các giáo trình c. ượ ọSau đây ta tìm hi thu toán ch ra th nh y. Ta chú ng nghi ng ng ràng bu ng các aằ ươ ố1 b1 a2 b2 ak bk có ẽd ng xạk Mk Trong đó Mk a1 a2 …* ak và xk là nghi tho mãn nh lý ng Trung Hoaệ ưt ng ng aươ ớ1 b1 a2 b2 ak bk th khi đó xễ ấk+1 là nghi không âm nh nh tho mãn bk+1 (mod ak+1 xk (mod Mk ). qu cu cùng, th mãn bài toán là xế ỏm Nh y, ta vi gi ph ng trình m-1 gi hai ph ng trình. ươ ươ10Giáo viên: Võ Tá Hoàng