Số học thuật toán P1

Chia sẻ: Trần Bá Trung4 | Ngày: | Loại File: PDF | Số trang:40

Thêm vào BST

Báo xấu

337
lượt xem 165
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Số học thuật toán P1 là tài liệu tham khảo, rất hay để các bạn đam mê toán tham khảo, tài liệu bao gồm các kiến thức chuyên sâu về toán. Chúc các bạn học tốt.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Số học thuật toán P1

Lêi nãi ®Çu Trong nh÷ng n¨m gÇn ®©y, sù ph¸t triÓn cña Tin häc ®· lµm thay ®æi nhiÒu ngµnh truyÒn thèng cña LÝ thuyÕt sè (trong cuèn s¸ch nµy, chóng ta th−êng dïng tõ “Sè häc”). NÕu nh− tr−íc thËp kû 70, sè häc vÉn ®−îc xem lµ mét trong nh÷ng ngµnh lÝ thuyÕt xa rêi thùc tiÔn nhÊt, th× ngµy nay, nhiÒu thµnh tùu míi nhÊt cña sè häc cã øng dông trùc tiÕp vµo c¸c vÊn ®Ò cña ®êi sèng, nh− th«ng tin, mËt m·, kÜ thuËt m¸y tÝnh. Mét ph−¬ng h−íng míi cña sè häc ra ®êi vµ ph¸t triÓn m¹nh mÏ: sè häc thuËt to¸n. Cã thÓ nãi, ®ã lµ chiÕc cÇu nèi gi÷a sè häc víi tin häc. Víi viÖc sö dông réng r·i m¸y tÝnh trong nghiªn cøu sè häc, nhiÒu ng−êi cho r»ng, sè häc ngµy nay ®· thµnh mét khoa häc thùc nghiÖm! §iÒu ®ã thÓ hiÖn kh¸ râ trong nh÷ng “thuËt to¸n x¸c suÊt” ®−îc ®Ò cËp ®Õn trong cuèn s¸ch nµy. Môc ®Ých cña cuèn s¸ch nhá nµy lµ cung cÊp cho ng−êi ®äc mét sè kiÕn thøc s¬ bé om m vÒ sè häc thuËt to¸n. Cuèn s¸ch kh«ng ®ßi hái ë ng−êi ®äc mét kiÕn thøc chuÈn bÞ nµo vÒ lý thuyÕt sè. V× thÕ còng cã thÓ gäi nã lµ “NhËp m«n thuËt to¸n vµo sè häc”. §iÒu ®ã cã nghÜa lµ, trong nhiÒu con ®−êng kh¸c nhau ®Ó ®i vµo sè häc, ta chän con o ®−êng thuËt to¸n: c¸c ®Þnh lÝ, kh¸i niÖm cña sè häc ®−îc tr×nh bµy cïng víi c¸c thuËt to¸n x©y dùng chóng. Trong nhiÒu tr−êng hîp, c¸c thuËt to¸n cã kÌm theo ®¸nh gi¸ s¬ bé vÒ ®é phøc t¹p. .C .C Cuèn s¸ch nh»m mét sè ®èi t−îng kh¸ réng r·i: nh÷ng sinh viªn, nghiªn cøu sinh vÒ sè häc vµ tin häc, nh÷ng ng−êi quan t©m ®Õn lÝ thuyÕt vµ øng dông cña sè häc hiÖn ®¹i. NhiÒu phÇn cña cuèn s¸ch cã thÓ cã Ých cho häc sinh c¸c líp chuyªn to¸n vµ h chuyªn tin häc. th Ch−¬ng ®Çu tiªn cña cuèn s¸ch ®−îc dµnh ®Ó giíi thiÖu vµi ®Þnh nghÜa c¬ b¶n nhÊt at cña lÝ thuyÕt thuËt to¸n. Ba ch−¬ng tiÕp theo tr×nh bµy nh÷ng vÊn ®Ò c¬ së cña sè a häc. Ch−¬ng 5, ngoµi viÖc chuÈn bÞ kiÕn thøc cho nh÷ng phÇn tiÕp theo, cã b×nh luËn Ýt nhiÒu vÒ vai trß cña sù t−¬ng tù gi÷a sè vµ ®a thøc trong sù ph¸t triÓn cña sè häc nM hiÖn ®¹i. M §Ó ng−êi ®äc cã thÓ h×nh dung phÇn nµo c¸c øng dông cña sè häc thuËt to¸n, cuèn s¸ch dµnh ch−¬ng 6 ®Ó nãi vÒ lÝ thuyÕt mËt m·. Mét vµi øng dông gÇn ®©y cña lÝ thuyÕt ®−êng cong elliptic vµo mËt m· ®−îc tr×nh bµy trong ch−¬ng 7. Còng cã thÓ n xem Ch−¬ng 7 lµ mét nhËp m«n ng¾n vµ s¬ cÊp vµo lÝ thuyÕt ®−êng cong elliptic, mét trong nh÷ng lÝ thuyÕt phong phó nhÊt cña H×nh häc ®¹i sè sè häc. V V Cuèi mçi ch−¬ng ®Òu cã mét sè bµi tËp dµnh cho ®éc gi¶ muèn ®äc cuèn s¸ch “mét c¸ch tÝch cùc”. Mét sè bµi tËp mang tÝnh chÊt luyÖn tËp vµ tÝnh to¸n thùc hµnh, mét sè kh¸c lµ më réng lÝ thuyÕt. Trõ ch−¬ng cuèi vÒ ®−êng cong elliptic, c¸c ch−¬ng cßn l¹i ®Òu cã kÌm theo h−íng dÉn thùc hµnh tÝnh to¸n b»ng ch−¬ng tr×nh MAPLE. PhÇn h−íng dÉn thùc hµnh nµy do T¹ ThÞ Hoµi An biªn so¹n. Cuèi cuèn s¸ch cã phÇn tù kiÓm tra kiÕn thøc dµnh cho nh÷ng ®éc gi¶ häc gi¸o tr×nh nµy víi sù trî gióp cña m¸y tÝnh. Do nhiÒu nguyªn nh©n kh¸c nhau, cuèn s¸ch ch¾c ch¾n cßn rÊt nhiÒu thiÕu sãt. T¸c gi¶ hy väng nhËn ®−îc nh÷ng lêi phª b×nh cña b¹n ®äc. Hµ néi, 1998 Hµ Huy Kho¸i i
Ch−¬ng 1. thuËt to¸n §1. §Þnh nghÜa. Cã thÓ ®Þnh nghÜa thuËt to¸n theo nhiÒu c¸ch kh¸c nhau. ë ®©y chóng t«i kh«ng cã ý ®Þnh tr×nh bµy chÆt chÏ vÒ thuËt to¸n nh− trong mét gi¸o tr×nh logic, mµ sÏ hiÓu kh¸i niÖm thuËt to¸n theo mét c¸ch th«ng th−êng nhÊt. om m ThuËt to¸n lµ mét qui t¾c ®Ó, víi nh÷ng d÷ liÖu ban ®Çu ®· cho, t×m ®−îc lêi gi¶i sau mét kho¶ng thêi gian h÷u h¹n. §Ó minh ho¹ c¸ch ghi mét thuËt to¸n, còng nh− t×m hiÓu c¸c yªu cÇu ®Ò ra cho thuËt o to¸n, ta xÐt trªn c¸c vÝ dô cô thÓ sau ®©y. Cho n sè X[1], X[2],..., X[n], ta cÇn t×m m vµ j sao cho m=X[j] = max X[k], vµ j lµ .C .C 1≤ k ≤ n lín nhÊt cã thÓ. §iÒu ®ã cã nghÜa lµ cÇn t×m cùc ®¹i cña c¸c sè ®· cho, vµ chØ sè lín nhÊt trong c¸c sè ®¹t cùc ®¹i. h Víi môc tiªu t×m sè cùc ®¹i víi chØ sè lín nhÊt, ta xuÊt ph¸t tõ gi¸ trÞ X[n]. B−íc thø th nhÊt, v× míi chØ cã mét sè, ta cã thÓ t¹m thêi xem m=X[n] vµ j=n. TiÕp theo , ta so s¸nh X[n] víi X[n-1]. Trong tr−êng hîp n-1=0, tøc n=1, thuËt to¸n kÕt thóc. at a NÕu X[n-1] ≤ X[n] , ta chuyÓn sang so s¸nh X[n] víi X[n-2] .Trong tr−êng hîp ng−îc l¹i, X[n-1] chÝnh lµ sè cùc ®¹i trong hai sè ®· xÐt, vµ ta ph¶i thay ®æi m vµ j: ®Æt m= nM M X[n-1], j=n-1. Víi c¸ch lµm nh− trªn, ë mçi b−íc, ta lu«n nhËn ®−îc sè cùc ®¹i trong nh÷ng sè ®· xÐt. B−íc tiÕp theo lµ so s¸nh nã víi nh÷ng sè ®øng tr−íc, hoÆc kÕt thóc thuËt to¸n trong tr−êng hîp kh«ng cßn sè nµo ®øng tr−íc nã. ThuËt to¸n m« t¶ trªn ®©y ®−îc ghi l¹i nh− sau: n ThuËt to¸n t×m cùc ®¹i. V V M1. [B−íc xuÊt ph¸t ] §Æt j←n, k←n-1, m← X[n]. M2. [§· kiÓm tra xong?] NÕu k=0, thuËt to¸n kÕt thóc. M3. [So s¸nh] NÕu X[k]≤m,chuyÓn sang M5. M4. [Thay ®æi m] §Æt j ← k, m ← X[k]. (T¹m thêi m ®ang lµ cùc ®¹i) M5. [Gi¶m k] §Æt k ← k-1, quay vÒ M2. DÊu “←“ dïng ®Ó chØ mét phÐp to¸n quan träng lµ phÐp thay chç (replacement). 1
Trªn ®©y ta ghi mét thuËt to¸n b»ng ng«n ng÷ th«ng th−êng. Trong tr−êng hîp thuËt to¸n ®−îc viÕt b»ng ng«n ng÷ cña m¸y tÝnh, ta cã mét ch−¬ng tr×nh. Trong thuËt to¸n cã nh÷ng sè liÖu ban ®Çu, ®−îc cho tr−íc khi thuËt to¸n b¾t ®Çu lµm viÖc: c¸c ®Çu vµo (input). Trong thuËt to¸n M, ®Çu vµo lµ c¸c sè X[1], X[2],..., X[n]. Mét thuËt to¸n cã thÓ cã mét hoÆc nhiÒu ®Çu ra (ouput). Trong thuËt to¸n M, c¸c ®Çu ra lµ m vµ j. Cã thÓ thÊy r»ng thuËt to¸n võa m« t¶ tho¶ m·n c¸c yªu cÇu cña mét thuËt to¸n nãi chung, ®ã lµ: 1. TÝnh h÷u h¹n.ThuËt to¸n cÇn ph¶i kÕt thóc sau mét sè h÷u h¹n b−íc. Khi thuËt to¸n ngõng lµm viÖc, ta ph¶i thu ®−îc c©u tr¶ lêi cho vÊn ®Ò ®Æt ra. ThuËt to¸n M râ om rµng tho¶ m·n ®iÒu kiÖn nµy, v× ë mçi b−íc, ta lu«n chuyÓn tõ viÖc xÐt mét sè sang m sè ®øng tr−íc nã, vµ sè c¸c sè lµ h÷u h¹n. 2. TÝnh x¸c ®Þnh. ë mçi b−íc, thuËt to¸n cÇn ph¶i x¸c ®Þnh, nghÜa lµ chØ râ viÖc cÇn o lµm. NÕu ®èi víi ng−êi ®äc, thuËt to¸n M ch−a tho¶ m·n ®iÒu kiÖn nµy th× ®ã lµ lçi cña ng−êi viÕt! .C .C Ngoµi nh÷ng yÕu tè kÓ trªn, ta cßn ph¶i xÐt ®Õn tÝnh hiÖu qu¶ cña thuËt to¸n. Cã rÊt nhiÒu thuËt to¸n, vÒ mÆt lÝ thuyÕt lµ kÕt thóc sau h÷u h¹n b−íc, tuy nhiªn thêi gian “h÷u h¹n” ®ã v−ît qu¸ kh¶ n¨ng lµm viÖc cña chóng ta. Nh÷ng thuËt to¸n ®ã sÏ kh«ng ®−îc xÐt ®Õn ë ®©y, v× chóng ta chØ quan t©m nh÷ng thuËt to¸n cã thÓ sö dông thh thËt sù trªn m¸y tÝnh. Còng do môc tiªu nãi trªn, ta cßn ph¶i chó ý ®Õn ®é phøc t¹p cña c¸c thuËt to¸n. §é at phøc t¹p cña mét thuËt to¸n cã thÓ ®o b»ng kh«ng gian, tøc lµ dung l−îng bé nhí cña a m¸y tÝnh cÇn thiÕt ®Ó thùc hiÖn thuËt to¸n, vµ b»ng thêi gian, tøc lµ thêi gian m¸y tÝnh lµm viÖc. Trong cuèn s¸ch nµy, khi nãi ®Õn ®é phøc t¹p cña thuËt to¸n, ta lu«n nM M hiÓu lµ ®é phøc t¹p thêi gian. §2. §é phøc t¹p thuËt to¸n. n DÜ nhiªn, thêi gian lµm viÖc cña m¸y tÝnh khi ch¹y mét thuËt to¸n nµo ®ã kh«ng chØ phô thuéc vµo thuËt to¸n, mµ cßn phô thuéc vµo m¸y tÝnh ®−îc sö dông. V× thÕ, ®Ó V cã mét tiªu chuÈn chung, ta sÏ ®o ®é phøc t¹p cña mét thuËt to¸n b»ng sè c¸c phÐp V tÝnh ph¶i lµm khi thùc hiÖn thuËt to¸n. Khi tiÕn hµnh cïng mét thuËt to¸n, sè c¸c phÐp tÝnh ph¶i thùc hiÖn cßn phô thuéc vµo cì cña bµi to¸n, tøc lµ ®é lín cña ®Çu vµo. V× thÕ, ®é phøc t¹p cña thuËt to¸n sÏ lµ mét hµm sè cña ®é lín cña ®Çu vµo. Trong nh÷ng øng dông thùc tiÔn, chóng ta kh«ng cÇn biÕt chÝnh x¸c hµm nµy, mµ chØ cÇn biÕt “ cì” cña chóng, tøc lµ cÇn cã mét −íc l−îng ®ñ tèt cña chóng. Khi lµm viÖc, m¸y tÝnh th−êng ghi c¸c ch÷ sè b»ng nh÷ng bãng ®Ìn “s¸ng, t¾t”: bãng ®Ìn s¸ng chØ sè 1, bãng ®Ìn t¾t chØ sè 0. V× thÕ thuËn tiÖn nhÊt lµ dïng hÖ ®Õm c¬ sè 2, trong ®ã ®Ó biÓu diÔn mét sè, ta chØ cÇn dïng hai kÝ hiÖu 0 vµ 1. Mét kÝ hiÖu 0 hoÆc 1 ®−îc gäi lµ mét bit (viÕt t¾t cña ch÷ “binary digit”). Mét sè nguyªn n biÓu diÔn bëi k ch÷ sè 1 vµ 0 d−îc gäi lµ mét sè k-bit. Trong ch−¬ng tiÕp theo, ta sÏ thÊy r»ng, sè tù nhiªn n sÏ lµ mét sè k-bit víi k=[log2n] ( dÊu[ ] kÝ hiÖu phÇn nguyªn cña mét sè). 2
§é phøc t¹p cña mét thuËt to¸n ®−îc ®o b»ng sè c¸c phÐp tÝnh bit. PhÐp tÝnh bit lµ mét phÐp tÝnh logic hay sè häc thùc hiÖn trªn c¸c sè 1-bit 0 vµ 1. §Ó −íc l−îng ®é phøc t¹p cña thuËt to¸n, ta dïng kh¸i niÖm bËc O-lín. §Þnh nghÜa 1.1: Gi¶ sö f(n) vµ g(n) lµ hai hµm x¸c ®Þnh trªn tËp hîp c¸c sè nguyªn d−¬ng. Ta nãi f(n) cã bËc O-lín cña g(n), vµ viÕt f(n)=O(g(n)) hoÆc f=O(g), nÕu tån t¹i mét sè C >0 sao cho víi n ®ñ lín, c¸c hµm f(n) vµ g(n) ®Òu d−¬ng, ®ång thêi f(n) < Cg(n). VÝ dô. 1) Gi¶ sö f(n) lµ ®a thøc; f(n)=adnd + ad-1nd-1 + ...+a1n+a0, trong ®ã ad > 0. DÔ chøng minh r»ng f(n)=O(nd). om m 2) NÕu f1(n)=O(g(n)), f2(n)=O(g(n)) th× f1+f2=O(g). 3) NÕu f1=O(g1), f2=O(g2), th× f1.f2=O(g1.g2). o 4) NÕu tån t¹i giíi h¹n h÷u h¹n f ( n) lim th× f=O(g). .C .C n→∞ g ( n) 5)Víi mäi sè ε >0, log n=O(n ε ). thh §Þnh nghÜa 1.2. Mét thuËt to¸n ®−îc gäi lµ cã ®é phøc t¹p ®a thøc, hoÆc cã thêi at gian ®a thøc, nÕu sè c¸c phÐp tÝnh cÇn thiÕt khi thùc hiÖn thuËt to¸n kh«ng v−ît qu¸ a O (logd n), trong ®ã n lµ ®é lín cña ®Çu vµo, vµ d lµ sè nguyªn d−¬ng nµo ®ã. Nãi c¸ch kh¸c, nÕu ®Çu vµo lµ c¸c sè k-bit th× thêi gian thùc hiÖn thuËt to¸n lµ O(kd), nM M tøc lµ t−¬ng ®−¬ng víi mét ®a thøc cña k. C¸c thuËt to¸n víi thêi gian O(n α ), α >0, ®−îc gäi lµ c¸c thuËt to¸n víi ®é phøc t¹p mò, hoÆc thêi gian mò. n Chó ý r»ng, nÕu mét thuËt to¸n nµo ®ã cã ®é phøc t¹p O(g), th× còng cã thÓ nãi nã ®é phøc t¹p O(h) víi mäi hµm h > g. Tuy nhiªn, ta lu«n lu«n cè g¾ng t×m −íc l−îng tèt V V nhÊt cã thÓ ®−îc ®Ó tr¸nh hiÓu sai vÒ ®é phøc t¹p thùc sù cña thuËt to¸n. Còng cã nh÷ng thuËt to¸n cã ®é phøc t¹p trung gian gi÷a ®a thøc vµ mò. Ta th−êng gäi ®ã lµ thuËt to¸n d−íi mò. Ch¼ng h¹n, thuËt to¸n nhanh nhÊt ®−îc biÕt hiÖn nay ®Ó ph©n tÝch mét sè nguyªn n ra thõa sè lµ thuËt to¸n cã ®é phøc t¹p exp( log n log log n ). Khi gi¶i mét bµi to¸n, kh«ng nh÷ng ta chØ cè g¾ng t×m ra mét thuËt to¸n nµo ®ã, mµ cßn muèn t×m ra thuËt to¸n “ tèt nhÊt”. §¸nh gi¸ ®é phøc t¹p lµ mét trong nh÷ng c¸ch ®Ó ph©n tÝch, so s¸nh vµ t×m ra thuËt to¸n tèi −u. Tuy nhiªn, ®é phøc t¹p kh«ng ph¶i lµ tiªu chuÈn duy nhÊt ®Ó ®¸nh gi¸ thuËt to¸n. Cã nh÷ng thuËt to¸n, vÒ lÝ thuyÕt th× cã ®é phøc t¹p cao h¬n mét thuËt to¸n kh¸c, nh−ng khi sö dông l¹i cã kÕt qu¶ 3
(gÇn ®óng) nhanh h¬n nhiÒu. §iÒu nµy cßn tuú thuéc nh÷ng bµi to¸n cô thÓ, nh÷ng môc tiªu cô thÓ, vµ c¶ kinh nghiÖm cña ng−êi sö dông. Chóng ta cÇn l−u ý thªm mét ®iÓm sau ®©y. MÆc dï ®Þnh nghÜa thuËt to¸n mµ chóng ta ®−a ra ch−a ph¶i lµ chÆt chÏ, nã vÉn qu¸ “cøng nh¾c “ trong nh÷ng øng dông thùc tÕ! Bëi vËy, chóng ta cßn cÇn ®Õn c¸c thuËt to¸n “x¸c suÊt “, tøc lµ c¸c thuËt to¸n phô thuéc vµo mét hay nhiÒu tham sè ngÉu nhiªn. Nh÷ng “thuËt to¸n” nµy, vÒ nguyªn t¾c kh«ng ®−îc gäi lµ thuËt to¸n, v× chóng cã thÓ, víi x¸c suÊt rÊt bÐ, kh«ng bao giê kÕt thóc. Tuy nhiªn, thùc nghiÖm chØ ra r»ng, c¸c thuËt to¸n x¸c suÊt th−êng h÷u hiÖu h¬n c¸c thuËt to¸n kh«ng x¸c suÊt. ThËm chÝ, trong rÊt nhiÒu tr−êng hîp, chØ cã c¸c thuËt to¸n nh− thÕ lµ sö dông ®−îc. Khi lµm viÖc víi c¸c thuËt to¸n x¸c suÊt, ta th−êng hay ph¶i sö dông c¸c sè “ngÉu nhiªn”. Kh¸i niÖm chän sè ngÉu nhiªn còng cÇn ®−îc chÝnh x¸c ho¸. Th−êng th× ng−êi ta sö dông mét “m¸y” s¶n xuÊt sè gi¶ ngÉu nhiªn nµo ®ã. Tuy nhiªn, trong om m cuèn s¸ch nµy, chóng t«i kh«ng ®Ò cËp ®Õn vÊn ®Ò nãi trªn, mµ mçi lÇn nãi ®Õn viÖc chän sè ngÉu nhiªn, ta sÏ hiÓu lµ ®iÒu ®ã thùc hiÖn ®−îc trªn m¸y. Còng cÇn l−u ý ngay r»ng, ®èi víi c¸c thuËt to¸n x¸c suÊt, kh«ng thÓ nãi ®Õn thêi o gian tuyÖt ®èi, mµ chØ cã thÓ nãi ®Õn thêi gian hy väng (expected ). .C §Ó h×nh dung ®−îc phÇn nµo “®é phøc t¹p” cña c¸c thuËt to¸n khi lµm viÖc víi .C nh÷ng sè lín, ta xem b¶ng d−íi ®©y cho kho¶ng thêi gian cÇn thiÕt ®Ó ph©n tÝch mét sè nguyªn n ra thõa sè b»ng thuËt to¸n nhanh nhÊt ®−îc biÕt hiÖn nay (ta xem m¸y tÝnh sö dông vµo viÖc nµy cã tèc ®é 1 triÖu phÐp tÝnh trong 1 gi©y) thh at Sè ch÷ sè thËp ph©n Sè phÐp tÝnh bit Thêi gian a 50 1,4.1010 3,9 giê 75 9,0.1012 104 ngµy nM M 100 2,3.1015 74 n¨m 200 1,2.1023 3,8.109 n¨m n 300 1,5.1029 4,9.1015 n¨m 500 1,3.1039 4,2.1025 n¨m V V Tõ b¶ng trªn ®©y, ta thÊy r»ng, ngay víi mét thuËt to¸n d−íi mò, thêi gian lµm viÖc víi c¸c sè nguyªn lín lµ qu¸ l©u. V× thÕ nãi chung ng−êi ta lu«n cè g¾ng t×m nh÷ng thuËt to¸n ®a thøc. LÝ thuyÕt vÒ ®é phøc t¹p thuËt to¸n lµ mét lÝ thuyÕt rÊt phong phó. Trong cuèn s¸ch nµy, chóng t«i kh«ng lÊy môc tiªu tr×nh bµy lÝ thuyÕt ®ã lµm träng t©m. §éc gi¶ quan t©m ®Õn lÝ thuyÕt thuËt to¸n cã thÓ t×m ®äc c¸c s¸ch trong phÇn Tµi liÖu tham kh¶o. 4
Ch−¬ng 2. Sè nguyªn §1. BiÓu diÔn sè nguyªn vµ c¸c phÐp tÝnh sè häc 1.1 HÖ c¬ sè. MÆc dï hÇu hÇu hÕt ®éc gi¶ ®· quen thuéc víi c¸ch biÓu diÔn sè nguyªn trong c¬ sè tuú ý, chóng t«i nh¾c l¹i s¬ qua vÊn ®Ò ®ã ë phÇn nµy, ®Ó thuËn tiÖn cho viÖc tr×nh om m bµy c¸c thuËt to¸n vÒ sè nguyªn. §Þnh lÝ 2.1. Gi¶ sö b lµ mét sè nguyªn lín h¬n 1. Khi ®ã mäi sè nguyªn n cã thÓ viÕt duy nhÊt d−íi d¹ng o n=akbk + ak-1bk-1 +...+ a1b1 +a0, .C trong ®ã aj lµ sè nguyªn, 0 ≤ aj ≤ k-1, víi j=0,1,...,k vµ hÖ sè ®Çu tiªn ak ≠ 0. .C Chøng minh. Ta chØ cÇn thùc hiÖn liªn tiÕp phÐp chia n cho b: n=bq0 +a0, 0 ≤ a0 ≤ b-1. thh NÕu q0 >b, ta tiÕp tôc chia q0 cho b ®Ó ®−îc at q0=bq1 +a1, 0 ≤ a1 ≤ b-1. a TiÕp tôc qu¸ tr×nh ®ã, ta cã: nM M q1=bq2 +a2, 0 ≤ a2 ≤ b-1 q2=bq3 +a3, 0 ≤ a3 ≤ b-1 ... ... ... n qk-1=b.0 +ak, 0 ≤ ak ≤ b-1. V V Qu¸ tr×nh kÕt thóc v× ta lu«n cã: n>q0>q1>... ≥ 0. Chóng t«i dµnh cho ®éc gi¶ viÖc chøng minh n cã d¹ng nh− trong ph¸t biÓu cña ®Þnh lÝ, vµ biÓu diÔn ®ã lµ duy nhÊt. Sè b nãi trong ®Þnh lÝ ®−îc gäi lµ c¬ sè cña biÓu diÔn. C¸c hÖ biÓu diÔn c¬ sè 10 vµ 2 t−¬ng øng ®−îc gäi lµ hÖ thËp ph©n vµ nhÞ ph©n. C¸c hÖ sè aj ®−îc gäi lµ c¸c ch÷ sè. VÒ sau ta dïng bit ®Ó chØ ch÷ sè nhÞ ph©n. NÕu sè nguyªn n biÓu diÔn trong c¬ sè b cã k ch÷ sè, th× tõ chøng minh trªn, ta cã : bk-1 ≤ n ≤ bk. Nh− vËy sè ch÷ sè cña n ®−îc tÝnh theo c«ng thøc: 5
k=[logb n]+1=[log n / log b]+1, trong ®ã, kÝ hiÖu log dïng ®Ó chØ logarit c¬ sè e. Trong c¬ sè tuú ý, ta cã: k=O(logn). §Ó ph©n biÖt c¸c biÓu diÔn cña sè nguyªn trong nh÷ng hÖ c¬ sè kh¸c nhau, ta th−êng dïng c¸ch viÕt (akak-1...a1a0)b ®Ó chØ sè n= akbk + ak-1bk-1 +...+ a1b1 +a0, VÝ dô. 1). §èi víi sè 1994 trong hÖ thËp ph©n, ta cã (1994)10=(11111001010)2. 2). Trong m¸y tÝnh, bªn c¹nh hÖ c¬ sè 2, ng−êi ta còng th−êng dïng hÖ c¬ sè 8 hoÆc 16. LÝ do chñ yÕu lµ v× viÖc chuyÓn mét sè viÕt ë c¬ sè nµy sang c¬ sè kia trong 3 c¬ sè ®ã ®−îc thùc hiÖn mét c¸ch dÔ dµng. VÝ dô, muèn chuyÓn mét sè cho trong c¬ sè 2 sang c¬ sè 8, ta chØ viÖc nhãm tõ ph¶i sang tr¸i tõng khèi 3 ch÷ sè, råi chuyÓn sè ®−îc viÕt trong khèi ®ã sang d¹ng thËp ph©n. Ch¼ng h¹n, sè (1110010100110)2 ®−îc t¸ch thµnh c¸c nhãm 1,110,010,100,110. Tõ ®ã ta ®−îc: om m (1110010100110)2=(16246)8. Ta cã thÓ lµm t−¬ng tù ®Ó chuyÓn sè ®· cho thµnh sè viÕt trong c¬ sè 16, chØ cÇn nhãm thµnh tõng bé 4 ch÷ sè. Chó ý r»ng, trong tr−êng hîp nµy, cÇn thªm vµo c¸c kÝ o hiÖu míi ®Ó chØ c¸c “ch÷ sè “ tõ 10 ®Õn 15. .C Ta nh¾c l¹i r»ng m¸y tÝnh sö dông c¸ch viÕt nhÞ ph©n, hoÆc lµ c¸c “bit”. M¸y tÝnh .C nµo còng cã giíi h¹n vÒ ®é lín cña c¸c sè cã thÓ ®−a vµo tÝnh to¸n. Giíi h¹n ®ã ®−îc gäi lµ cì tõ cña m¸y, kÝ hiÖu qua w. Cì tõ th−êng lµ mét luü thõa cña 2, ch¼ng h¹n 235. thh §Ó thùc hiÖn c¸c phÐp tÝnh sè häc víi nh÷ng sè nguyªn lín h¬n cì tõ, ta lµm nh− sau. Muèn ®−a mét sè n > w vµo m¸y, ta viÕt n d−íi d¹ng c¬ sè w, vµ khi ®ã n ®−îc at biÓu diÔn b»ng nh÷ng sè kh«ng v−ît qu¸ cì tõ. VÝ dô, nÕu cì tõ cña m¸y lµ 235, th× a ®Ó ®−a vµo mét sè cã ®é lín cì 2350-1, ta chØ cÇn dïng 10 sè nhá nhá h¬n cì tõ cña m¸y, b»ng c¸ch biÓu diÔn n trong c¬ sè 235. Nh− ®· nãi trong vÝ dô ë 1, viÖc chuyÓn mét sè tõ c¬ sè 2 sang c¬ sè 235 ®−îc thùc hiÖn dÔ dµng b»ng c¸ch nhãm tõng khèi nM M 35 ch÷ sè. Tõ qui t¾c cña c¸c phÐp tÝnh sè häc, ta thÊy r»ng: n 1) §Ó céng hoÆc trõ hai sè nguyªn k bit, ta cÇn O(k) phÐp tÝnh bit. 2) §Ó nh©n hoÆc chia hai sè k bit theo qui t¾c th«ng th−êng, ta cÇn O(k2) phÐp tÝnh V V bit. Trong nh÷ng thËp kØ gÇn ®©y, ng−êi ta t×m ra nh÷ng thuËt to¸n nh©n víi ®é phøc t¹p bÐ h¬n nhiÒu so víi c¸ch nh©n th«ng th−ßng. §iÒu thó vÞ lµ, nÕu tho¹t nh×n th× c¸c thuËt to¸n ®ã “phøc t¹p” h¬n quy t¾c nh©n th«ng th−êng. Tuy nhiªn, khi lµm viÖc víi nh÷ng sè rÊt lín, c¸c thuËt to¸n nµy cho phÐp thùc hiÖn viÖc nh©n hai sè víi mét thêi gian bÐ h¬n h¼n so víi quy t¾c th«ng th−êng. 1.2 ThuËt to¸n nh©n nhanh hai sè. Ta sö dông tÝnh chÊt hÕt søc ®¬n gi¶n cña phÐp nh©n: nÕu a=a1+a2, b=b1+b2, th× ab=a1b1+a2b2+a2b1+a1b2. §iÒu ®¸ng chó ý ë ®©y lµ, thay cho viÖc nh©n hai sè nguyªn n bit, ta thùc hiÖn viÖc nh©n c¸c sè cã ch÷ sè nhá h¬n, cïng víi mét sè phÐp 6
céng (®ßi hái sè phÐp tÝnh bit Ýt h¬n lµ phÐp nh©n). Thùc ra ®iÒu nµy kh«ng cã g× míi: ngay trong quan niÖm ban ®Çu, phÐp nh©n a víi b ®· lµ phÐp céng b lÇn sè a!. Tuy nhiªn ®Ó cã mét thuËt to¸n nh©n nhanh, ta kh«ng thÓ céng b lÇn sè a, mµ ph¶i t×m ®−îc mét c¸ch tèi −u nµo ®ã ®Ó t¸ch b vµ a thµnh nh÷ng phÇn nhá h¬n. Nh÷ng thuËt to¸n tr×nh bµy d−íi ®©y cho chóng ta mét sè c¸ch ®Ó lµm viÖc ph©n chia nh− vËy. Gi¶ sö muèn nh©n hai sè nguyªn 2n bit, a=(a2n-1a2n-2...a1a0)2, b=(b2n-1b2n-2...b1b0)2. Ta viÕt a=2nA1+A0, b=2nB1+B0, trong ®ã om m A1=(a2n-1a2n-2...an)2, A0=(an-1an-2...a1a0)2, B1=(b2n-1b2n-2...bn)2, B0=(bn-1bn-2...b1b0)2. o Khi ®ã ta cã: ab=(22n+2n)A1B1+2n(A1 - A0)+(2n+1)A0B0. (1.1) .C .C Nh− vËy, viÖc nh©n hai sè a,b 2n bit ®−îc ®−a vÒ viÖc nh©n c¸c sè n bit, cïng víi c¸c phÐp céng, trõ vµ dÞch chuyÓn (nh©n mét sè víi mét luü thõa bËc n cña 2 ®−îc thùc hiÖn b»ng c¸ch dÞch sè ®ã sang tr¸i n vÞ trÝ). thh §Þnh lÝ 2.2. ThuËt to¸n 2.1 cã ®é phøc t¹p lµ O(nlog23). at Chøng minh. Gäi M(n) lµ sè c¸c phÐp tÝnh bit tèi ®a cÇn thiÕt khi thùc hiÖn nh©n hai sè nguyªn n bit b»ng thuËt to¸n 2.1. Tõ c«ng thøc (1.1) ta cã: a M(2n) ≤ 3M(n)+Cn, nM M trong ®ã C lµ mét h»ng sè kh«ng phô thuéc n. §Æt c=max(C,M(2)). B»ng quy n¹p, dÔ chøng minh ®−îc r»ng n M(2k) ≤ c(3k-2k). Tõ ®ã ta cã V V M(n)=M(2log2n) ≤ M(2[log2n]+1) ≤ c(3[log2n]+1-2[log2n]+1) ≤ 3c.3[log2n] ≤ 3c.3log2n=3cnlog23. §Þnh lÝ ®· ®−îc chøng minh. Víi thuËt to¸n 2.1, ta thÊy r»ng, ngay chØ víi c¸ch ph©n chia ®¬n gi¶n sè nguyªn thµnh hai phÇn víi sè ch÷ sè b»ng nhau, ta ®· nhËn ®−îc mét thuËt to¸n gi¶m ®¸ng kÓ thêi gian thùc hiÖn phÐp nh©n. DÜ nhiªn, c¸ch ph©n chia nh− vËy cßn xa víi c¸ch ph©n chia tèi −u. Ta sÏ chøng tá r»ng c¸ch ph©n chia nh− trªn cã thÓ tæng qu¸t ho¸ ®Ó nhËn ®−îc nh÷ng thuËt to¸n nh©n víi ®é phøc t¹p nhá h¬n nhiÒu. 7
Còng nh− tr−íc ®©y, ta sÏ kÝ hiÖu qua M(n) sè c¸c phÐp tÝnh bit cÇn thiÕt ®Ó thùc hiÖn phÐp nh©n hai sè nguyªn n bit. Tr−íc tiªn, ta chøng minh c«ng thøc sau: víi mäi sè tù nhiªn n, tån t¹i thuËt to¸n sao cho: M((r+1)n) ≤ (2r+1)M(n)+Cn, (1.2) víi C lµ mét h»ng sè nµo ®ã. Nh− vËy, §Þnh lÝ 2.2 lµ tr−êng hîp riªng víi r=1. Gi¶ sö cÇn nh©n hai sè (r+1)n bit: a=(a(r+1)n-1...a1a0)2, b=(b(r+1)n-1...b1b0)2. Ta t¸ch mçi sè a,b thµnh r+1 sè h¹ng: a=Ar2rn+...+A12n+A0 om m b=Br2rn+...+B12n+B0, trong ®ã Aj,Bj lµ c¸c sè n bit. o Ta nhËn xÐt r»ng, viÖc biÓu diÔn mét sè nguyªn d−íi d¹ng c¬ sè nµo ®ã còng gÇn .C gièng nh− viÕt sè ®ã d−íi d¹ng ®a thøc, trong ®ã c¸c ch÷ sè chÝnh lµ c¸c hÖ sè cña .C ®a thøc. V× vËy viÖc nh©n hai sè cã thÓ thùc hiÖn t−¬ng tù nh− viÖc nh©n ®a thøc. Ta xÐt c¸c ®a thøc sau: A(x)=Arxr+...+A1x+A0, thh B(x)=Brxr+...+B1x+B0, at W(x)=A(x)B(x)=W2rx2r+...+W1x+W0. a Tõ ®Þnh nghÜa c¸c ®a thøc trªn ta ®ù¬c: a=A(2n),b=B(2n), ab= W(2n). Nh− vËy, ta dÔ nM dµng tÝnh ®−îc tÝch ab nÕu biÕt ®−îc c¸c hÖ sè cña ®a thøc W(x). M C«ng thøc (1.2) sÏ ®−îc chøng minh nÕu ta t×m ®−îc mét thuËt to¸n tÝnh c¸c hÖ sè cña W(x) mµ chØ sö dông 2r+1 phÐp nh©n c¸c sè n bit vµ mét sè phÐp tÝnh kh¸c víi ®é phøc t¹p O(n). §iÒu ®ã cã thÓ lµm b»ng c¸ch tÝnh gi¸ trÞ cña ®a thøc W(x) t¹i n 2r+1 ®iÓm sau ®©y: V W(0)=A(0)B(0), W(1)=A(1)B(1),..., W(2r)=A(2r)B(2r). V Chó ý r»ng, c¸c sè Aj,Bj kh«ng nhÊt thiÕt lµ c¸c sè n bit, nh−ng víi r cè ®Þnh, chóng cã sè ch÷ sè nhiÒu nhÊt lµ r+t, víi mét t cè ®Þnh nµo ®ã. DÔ thÊy r»ng, cã thÓ nh©n hai sè (r+t)-bit víi kh«ng qu¸ M(n)+c1n phÐp tÝnh bit, trong ®ã c1 lµ h»ng sè (chØ cÇn t¸ch sè (n+t)-bit thµnh hai phÇn n-bit vµ t-bit, vµ nhËn xÐt r»ng, khi t cè ®Þnh, viÖc nh©n sè t-bit víi sè n-bit ®ßi hái kh«ng qu¸ cn phÐp tÝnh bit). Khi ®· cã c¸c gi¸ trÞ W(j),(j=0,1,...2r), ta t×m ®−îc ®a thøc W(x) theo c«ng thøc Lagrange: 2r x(x - 1)...(x - j + 1)(x - j - 1)...(x - 2r) W(x)= ∑ ( −1) j W(j) . j=0 j!(2r - j)! 8
Nh− vËy, c¸c hÖ sè cña W(x) sÏ lµ tæ hîp tuyÕn tÝnh (víi hÖ sè kh«ng phô thuéc n) cña c¸c gi¸ trÞ W(j), vµ do ®ã, tÝnh ®ùoc b»ng O(n) phÐp tÝnh bit. Ta ®· chøng minh ®−îc c«ng thøc sau: M((r+1)n) ≤ (2r+1)M(n)+Cn. LËp luËn t−¬ng tù nh− trong chøng minh ®Þnh lÝ 2.1 ta cã: M(n) ≤ C3nlogr+1(2r+1)0 bÐ tuú ý, khi c¸c thõa sè cã sè ch÷ sè rÊt lín, ta cã thÓ chän r ®ñ lín sao cho logr+12< ε . Ta cã ®Þnh lÝ sau: §Þnh lÝ 2.3. Víi mäi ε >0, tån t¹i thuËt to¸n nh©n sao cho sè phÐp tÝnh bit M(n) cÇn thiÕt ®Ó nh©n hai sè n bit tho¶ m·n bÊt ®¼ng thøc om M(n)
ThËt vËy, v× n lµ mét hîp sè nªn ta cã thÓ viÕt n=ab, trong ®ã a vµ b lµ c¸c sè nguyªn víi 1
n=p1 p2 ...ps=q1q2...qr, trong ®ã pi, qj lµ c¸c sè nguyªn tè. Gi¶n −íc nh÷ng sè nguyªn tè b»ng nhau cã mÆt trong hai vÕ, ta ®−îc ®¼ng thøc pi1pi2...piu=qj1qj2...qjv,, trong ®ã kh«ng cã sè nguyªn tè nµo cã mÆt c¶ hai vÕ. Nh− vËy, vÕ tr¸i chia hÕt cho qj1, vµ do ®ã ph¶i tån t¹i mét thõa sè cña tÝch chia hÕt cho qj1: ®iÒu ®ã v« lý, v× ®©y lµ tÝch c¸c sè nguyªn tè kh¸c víi qj1. Ph©n tÝch nh− trªn cña c¸c sè nguyªn ®−îc gäi lµ ph©n tÝch ra thõa sè nguyªn tè. Khi n lµ mét sè rÊt lín, viÖc kiÓm tra xem n lµ sè nguyªn tè hay hîp sè, vµ nÕu lµ hîp sè th× t×m ph©n tÝch cña nã ra thõa sè nguyªn tè, lµ mét bµi to¸n hÕt søc khã kh¨n. Trong nh÷ng phÇn tiÕp theo cña cuèn s¸ch, ta sÏ t×m hiÓu nhiÒu thuËt to¸n ®Ó lµm om viÖc ®ã, còng nh− c¸c øng dông cña nã trong thùc tiÔn. m §3. ThuËt to¸n Euclid. o .C .C Mét trong nh÷ng thuËt to¸n c¬ b¶n vµ l©u ®êi nhÊt cña to¸n häc lµ thuËt to¸n Euclid. ThuËt to¸n ®ã cho phÐp x¸c ®Þnh −íc chung lín nhÊt cña hai sè nguyªn cho tr−íc. Khi tr×nh bµy thuËt to¸n Euclid, ta nh¾c l¹i s¬ qua kh¸i niÖm ®ång d−. Nh÷ng tÝnh thh chÊt cÇn dïng cña ®ång d− vµ c¸c tÝnh chÊt c¬ b¶n cña −íc chung lín nhÊt ®−îc cho trong c¸c bµi tËp cña ch−¬ng nµy. at Gi¶ sö m lµ mét sè nguyªn d−¬ng. Ta nãi hai sè nguyªn a vµ b lµ ®ång d− víi nhau a modulo m nÕu m chia hÕt hiÖu a-b ( ta dïng c¸ch viÕt m | (a-b)). §Ó chØ quan hÖ ®ång d−, ta dïng ký hiÖu a ≡ b (mod m). nM M Nh− vËy, a ≡ b (mod m) khi vµ chØ khi tån t¹i sè nguyªn k sao cho a=b+km. Quan hÖ ®ång d− lµ mét trong nh÷ng quan hÖ c¬ b¶n cña sè häc, vµ ta sÏ gÆp th−êng n xuyªn trong nh÷ng phÇn tiÕp theo cña cuèn s¸ch. Trong thuËt to¸n Euclid, ta chØ dïng quan hÖ ®ã ®Ó diÔn ®¹t ng¾n gän vÒ phÇn d− cña phÐp chia. V ThuËt to¸n sau ®©y cho phÐp tÝnh −íc chung lín nhÊt (¦CLN) d cña hai sè nguyªn V kh«ng ©m a vµ b (ký hiÖu lµ d=(a,b)). ThuËt to¸n Euclid E1. [KÕt thóc?] NÕu b=0, in ra a vµ kÕt thóc thuËt to¸n. E2. [Chia Euclid] §Æt r ← a mod b, a ← b, b ← r vµ quay vÒ b−íc 1. VÝ dô: tÝnh d=(24,63) b»ng thuËt to¸n Euclid. Ta cã: d=(24,63) = (15,24)=(9,15)=(6,9)=(3,6)=(0,3)=3. 11
§Þnh lý sau ®©y võa cho ta mét chøng minh tÝnh ®óng ®¾n cña thuËt to¸n Euclid, võa cho mét −íc l−îng vÒ ®é phøc t¹p cña nã. §Þnh lÝ LamÐ. Sè phÐp chia cÇn thiÕt ®Ó t×m ¦CLN cña hai sè nguyªn d−¬ng b»ng thuËt to¸n Euclid kh«ng v−ît qu¸ 5 lÇn sè ch÷ sè thËp ph©n cña sè bÐ trong hai sè ®· cho. Chøng minh. Gi¶ sö a>b lµ hai sè nguyªn d−¬ng cho tr−íc. B»ng thuËt to¸n Euclid, ta cã: a=r0, b=r1 vµ: r0=r1q1+r2, 0 ≤ r2
ThËt vËy, sè phÐp chia ph¶i lµm lµ O(log2a), vµ mçi phÐp chia cÇn O((log2a)2) phÐp tÝnh bit. ThuËt to¸n Euclid, mÆc dï ®· ra ®êi hµng ngh×n n¨m, vÉn lµ thuËt to¸n tèt nhÊt ®Ó t×m ¦CLN cña hai sè nguyªn cho tr−íc! Cho ®Õn n¨m 1967, J.Stein x©y dùng ®−îc mét thuËt to¸n kh¸ thuËn tiÖn ®Ó t×m ¦CLN trong tr−êng hîp c¸c sè ®· cho ®−îc viÕt d−íi d¹ng nhÞ ph©n. ¦u ®iÓm chñ yÕu cña thuËt to¸n nµy lµ ta kh«ng cÇn lµm c¸c phÐp tÝnh chia (thùc ra ta cã lµm phÐp chia sè ch½n cho 2, nh−ng trong c¬ sè 2 th× ®ã lµ phÐp dÞch chuyÓn sè ®· cho sang ph¶i mét vÞ trÝ). ThuËt to¸n dùa trªn nh÷ng nhËn xÐt ®¬n gi¶n sau (xem phÇn bµi tËp cuèi ch−¬ng): 1) NÕu a,b lµ c¸c sè ch½n, th× (a,b)=2(a/2,b/2). 2) NÕu a ch½n, b lÎ, th× (a,b)=(a/2,b). 3) NÕu a,b ®Òu lÎ th× a-b ch½n vµ |a-b|0, ®Æt a ← t; nÕu n ng−îc l¹i, ®Æt b ← -t. Nh− vËy, sè lín nhÊt trong hai sè ®· ®−îc thay bëi |t|. V V E’6. (Trõ) §Æt t ← a-b. NÕu t ≠ 0, quay l¹i E’3. NÕu ng−îc l¹i thuËt to¸n kÕt thóc vµ in ra a.2k. Ngoµi thuËt to¸n Euclid nãi trªn, trong nhiÒu tr−êng hîp, ta cÇn ®Õn thuËt to¸n Euclid më réng. ThuËt to¸n nµy kh«ng nh÷ng cho ta thuËt to¸n t×m ¦CLN cña hai sè a, b, mµ cßn cho ta biÓu diÔn d=(a,b) d−íi d¹ng tæ hîp tuyÕn tÝnh cña a, b: d=ma+nb, trong ®ã m, n lµ c¸c sè nguyªn. Tr−íc hÕt, ta chøng minh bæ ®Ò sau: Bæ ®Ò 2.7: ¦CLN cña c¸c sè nguyªn a vµ b lµ sè d d−¬ng nhá nhÊt biÓu diÔn ®−îc d−íi d¹ng tæ hîp tuyÕn tÝnh cña a vµ b. 13
ThËt vËy, gi¶ sö d lµ sè nguyªn d−¬ng nhá nhÊt biÓu diÔn ®−îc d−íi d¹ng d=ma+nb. Ta chøng tá d lµ −íc chung cña a vµ b. XÐt phÐp chia a=dq+r, trong ®ã 0 ≤ r
... ... ... xr ≡ ar(mod mr). Cã nghiÖm duy nhÊt modulo M=m1m2...mr. Chøng minh. Tr−íc hÕt ta x©y dùng mét nghiÖm cña hÖ. Gi¶ sö Mk=M/mk= m1m2...mk-1mk+1...mr. Ta biÕt r»ng (Mk,mk)=1 v× (mj,mk)=1 víi mäi j ≠ k. Nh− vËy, theo bµi tËp 2.18 ta cã thÓ t×m mét nghÞch ®¶o yk cña Mk modulo mk, tøc lµ Mkyk ≡ 1 (mod mk). §Æt x=a1M1y1+ a2M2y2 +...+ arMryr . Ta thÊy r»ng x ≡ ak(mod mk) víi mäi k v× mk |Mj víi j ≠ k nªn Mj ≡ 0 (mod mk) khi j ≠ k. om m Nh− vËy, x chÝnh lµ mét nghiÖm cña hÖ ®ang xÐt. Ta chøng tá r»ng nghiÖm võa x©y dùng lµ duy nhÊt modulo M. Gi¶ sö x0, x1 lµ hai o nghiÖm cña hÖ. Khi ®ã, víi mçi k, x0 ≡ x1 ≡ ak (mod mk), cho nªn mk | (x0-x1). Theo bµi tËp 2.17, M | (x0-x1). §Þnh lÝ ®−îc chøng minh. .C .C §Þnh lÝ Trung Quèc vÒ phÇn d− liªn quan bµi to¸n næi tiÕng “Hµn TÝn ®iÓm binh”. T−¬ng truyÒn r»ng, ®Ó kiÓm tra qu©n sè, Hµn TÝn th−êng ra lÖnh cho qu©n sÜ xÕp thµnh hµng 3, hµng 5, hµng 7 vµ th«ng b¸o cho «ng c¸c sè d−. Khi biÕt c¸c sè d− vµ ®· cã s½n th«ng tin gÇn ®óng vÒ sè qu©n cña m×nh, Hµn TÝn dïng ®Þnh lÝ trªn ®©y ®Ó thh suy ra sè qu©n chÝnh x¸c. at §Þnh lÝ Trung Quèc vÒ phÇn d− ®−îc sö dông trong m¸y tÝnh ®Ó lµm viÖc víi nh÷ng sè lín. §Ó ®−a mét sè nguyªn lín tuú ý vµo m¸y tÝnh vµ lµm c¸c phÐp tÝnh sè häc víi a chóng, ta cÇn cã nh÷ng kÜ thuËt ®Æc biÖt. Theo ®Þnh lÝ Trung quèc vÒ phÇn d−, khi cho tr−íc c¸c modun nguyªn tè cïng nhau m1,m2,...,mr, mét sè d−¬ng n
B©y giêi ta dïng ®Þnh lÝ Trung Quèc vÒ phÇn d− ®Ó t×m x+y modulo M=99.98.97.95=89403930. Ta cã: M1=M/99=903070, M2=M/98=912288, M3=M/97=921690, M4=M/95=941094. Ta cÇn t×m ng−îc cña Mi(mod yi) víi i=1,2,3,4, tøc lµ gi¶i hÖ ph−¬ng tr×nh ®ång d− sau ®©y (B»ng thuËt chia Euclid): 903070y1 ≡ 91y1 ≡ 1(mod 99) 912285y2 ≡ 3y2 ≡ 1(mod 98) 921690y3 ≡ 93y3 ≡ 1(mod 97) Ta t×m ®−îc: y1 ≡ 37(mod 99), y2 ≡ 38(mod 98), y3 ≡ 24(mod 97), y4 ≡ 4(mod 95). Nh− vËy, x+y=65.903070.37+2.912285.33+51.921690.24+10.941094.4=3397886480 om m ≡ 537140(mod 89403930) V× 0
Trong c¸c m¸y tÝnh hiÖn ®¹i, viÖc thùc hiÖn nhiÒu phÐp tÝnh ®−îc tiÕn hµnh ®ång thêi. V× thÕ viÖc sö dông ®Þnh lÝ Trung Quèc vÒ phÇn d− nh− trªn l¹i cµng tiÖn lîi: thay cho viÖc lµm c¸c phÐp tÝnh víi c¸c sè nguyªn lín, ta lµm nhiÒu phÐp tÝnh ®ång thêi víi nh÷ng sè nguyªn bÐ h¬n. §iÒu ®ã gi¶m ®¸ng kÓ thêi gian tÝnh to¸n. om m o .C .C thh at a nM M n V V 17
ThuËt to¸n gi¶i ph−¬ng tr×nh ®ång d− b»ng ®Þnh lÝ Trung Quèc Tõ chøng minh ®Þnh lÝ Trung Quèc vÒ phÇn d−, ta cã thuËt to¸n sau ®©y ®Ó gi¶i hÖ ph−¬ng tr×nh ®ång d− x ≡ xi (mod mi), trong ®ã mi, 1 ≤ i ≤ k lµ c¸c sè nguyªn tè víi nhau tõng cÆp, xi lµ c¸c sè nguyªn cho tr−íc. Trong thuËt to¸n tr×nh bµy sau ®©y, chóng ta ®· t×m ra c¸ch ®Ó tr¸nh ph¶i lµm viÖc víi c¸c sè lín nh− Mi vµ aiMi. ThuËt to¸n. 1. (XuÊt ph¸t). §Æt j ← 2, C1 ← 1. H¬n n÷a ta s¾p xÕp l¹i c¸c sè mi theo thø tù t¨ng dÇn. 2. (TÝnh to¸n s¬ bé). §Æt p ← m1m2...mj-1(mod mj). TÝnh (u,v,d) sao cho up+vmj=d=UCLN(p,mj) b»ng thuËt to¸n Euclid më réng. om m Ed. NÕu d>0, in ra th«ng b¸o: c¸c mi kh«ng nguyªn tè cïng nhau tõng cÆp. NÕu ng−îc l¹i, ®Æt Cj ← u, j ← j+1 vµ chuyÓn sang b−íc 3 nÕu j ≤ k. o 3. (TÝnh c¸c h»ng sè phô). §Æt y1 ← x1 mod m1, vµ mçi j=2,...,k tÝnh: .C .C yj ← (xj-(y1+m1(y2+m2(y3+...+mj-2yj-1)...))Cjmod mj. 4. (KÕt thóc). In ra x ← y1+m1(y2+m2(y3+...+mk-1yk)...), vµ kÕt thóc thuËt to¸n. thh at §5. Mét sè ®ång d− ®Æc biÖt. a nM M §Þnh lÝ Wilson. p lµ sè nguyªn tè khi vµ chØ khi (p-1)! ≡ -1 (mod p). Chøng minh. Tr−íc tiªn, gi¶ sö p lµ sè nguyªn tè. Khi p=2, ta cã (p-1)! ≡ 1 ≡ -1(mod 2). B©y giê gi¶ sö p lµ sè nguyªn tè lín h¬n 2. Theo bµi tËp 2.18, n víi mçi sè nguyªn a víi 1 ≤ a ≤ p-1, tån t¹i nghÞch ®¶o a , 1 ≤ a ≤ p-1, víi V a a ≡ 1(mod p). Theo bµi tËp 2.13, trong sè c¸c sè nguyªn d−¬ng nhá h¬n p, chØ cã 1 V vµ p-1 lµ nghÞch ®¶o víi chÝnh nã. Nh− vËy ta cã thÓ nhãm c¸c sè nguyªn tõ 2 ®Õn p-2 thµnh (p-3)/2 cÆp sè nguyªn, tÝch cña mçi cÆp ®ång d− víi 1 modulo p. Nh− vËy ta cã: 2.3.....(p-3)(p-2) ≡ 1 (mod p) Nh©n hai vÕ víi 1 vµ p-1 ta ®−îc: (p-1)! ≡ 1.2.3...(p-2)(p-1) ≡ 1(p-1) ≡ -1(mod p) Ng−îc l¹i gi¶ sö p tho¶ m·n ®ång d− ph¸t biÓu trong ®Þnh lÝ vµ a lµ mét −íc sè cña p, a
§Þnh lÝ Wilson cã thÓ ®−îc dïng ®Ó kiÓm tra mét sè cã ph¶i lµ sè nguyªn tè hay kh«ng. Tuy nhiªn , dÔ thÊy r»ng, thuËt to¸n dùa theo ®Þnh lÝ Wilson khã cã thÓ sö dông víi nh÷ng sè nguyªn lín, bëi v× sè c¸c phÐp tÝnh bit ®ßi hái qu¸ cao. §Ó ®¬n gi¶n, ta gäi c«ng viÖc xem xÐt mét sè ®· cho cã ph¶i lµ sè nguyªn tè hay kh«ng lµ kiÓm tra nguyªn tè. §Þnh lÝ sau ®©y cã nhiÒu øng dông trong kiÓm tra nguyªn tè. §Þnh lÝ Fermat bÐ. NÕu p lµ sè nguyªn tè vµ a lµ sè kh«ng chia hÕt cho p th× ap-1 ≡ 1(mod p). Chøng minh. XÐt p-1 sè nguyªn a, 2a,..., (p-1)a. C¸c sè ®ã ®Òu kh«ng chia hÕt cho p vµ kh«ng cã hai sè nµo ®ång d− modulo p. Nh− vËy, c¸c thÆng d− d−¬ng bÐ nhÊt cña chóng ph¶i lµ 1, 2,... p-1, xÕp theo thø tù nµo ®ã. Tõ ®ã ta cã: a.2a.....(p-1) ≡ 1...(p-1) ≡ (p-1)!(mod p) om m tøc lµ ap-1(p-1)! ≡ 1(mod p) o V× ((p-1)!,p)=1 nªn ta cã ap-1 ≡ 1(mod p). .C .C HÖ qu¶ 2.11. NÕu p lµ sè nguyªn tè vµ a lµ sè nguyªn d−¬ng th× ap ≡ a(mod p). HÖ qu¶ 2.12. NÕu p lµ sè nguyªn tè vµ a lµ sè nguyªn kh«ng chia hÕt cho p th× ap-2 lµ nghÞch ®¶o cña a modulo p. thh HÖ qu¶ 2.13. NÕu a vµ b lµ c¸c sè nguyªn d−¬ng, p nguyªn tè, p|a th× c¸c nghiÖm cña ®ång d− thøc tuyÕn tÝnh ax ≡ b(mod p) lµ c¸c sè nguyªn x sao cho at x ≡ ap-2b(mod p). a nM M §6. Sè gi¶ nguyªn tè. n Theo ®Þnh lÝ Fermat, nÕu n lµ sè nguyªn tè vµ b lµ sè nguyªn tuú ý, th× bn ≡ b(mod n). Do ®ã nÕu tån t¹i sè b sao cho bn ≡ b(mod n) th× n ph¶i lµ hîp sè. Trong nhiÒu øng / V dông , chóng ta l¹i cÇn ®Õn c¸c thuËt to¸n ®Ó chØ ra mét sè n lµ sè nguyªn tè. Trong V tr−êng hîp nµy, ta kh«ng thÓ dïng ®Þnh lÝ Fermat bÐ, v× ®Þnh lÝ ng−îc cña nã kh«ng ®óng. Tuy nhiªn, nÕu mét sè nguyªn tho¶ m·n c¸c gi¶ thiÕt cña ®Þnh lÝ Fermat bÐ th× “cã nhiÒu kh¶ n¨ng” nã lµ mét sè nguyªn tè! Ta cã ®Þnh nghÜa sau ®©y. §Þnh nghÜa 2.14. Gi¶ sö b lµ mét sè nguyªn d−¬ng. NÕu n lµ hîp sè nguyªn d−¬ng vµ bn ≡ b(mod n) th× n ®−îc gäi lµ sè gi¶ nguyªn tè c¬ së b. Trong tr−êng hîp (n,b)=1, ta th−êng dïng ®Þnh nghÜa t−¬ng ®−¬ng: bn-1 ≡ b(mod n). VÝ dô. Sè nguyªn 561=3.11.17 lµ sè gi¶ nguyªn tè c¬ së 2. ThËt vËy, ¸p dông ®Þnh lÝ Fermat bÐ, ta cã 2560=(22)280 ≡ 1(mod 3), 2560=(210)56 ≡ 1(mod 11), 2 =(2 ) ≡ 1(mod 17). Tõ ®ã suy ra (bµi tËp 2.12) 2560 ≡ 1(mod 561). 560 16 35 19