zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» An ninh - Bảo mật

Tìm hiểu và nghiên cứu các đảm bảo xác thực thay cho đảm bảo mật phần 3

Chia sẻ: AFASFAF FSAFASF | Ngày: | Loại File: PDF | Số trang:5

Báo xấu

66
lượt xem 6
download

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

Giả sử tồn tại một 0A(n,k,λ) .Khi đó k≥ n+1 Chứng minh: Cho A là một 0A(n,k,l) trên tập kí hiệu X={0,1...n-1}.Giả sử π là một phép hoán vị của X và ta hoán vị các kí hiệu trong một cột bất kì của A theo phép giao hoán π.Kết quả là ta lại có một 0A(n,k,l).

Chủ đề:

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

Lưu

Nội dung Text: Tìm hiểu và nghiên cứu các đảm bảo xác thực thay cho đảm bảo mật phần 3

Vietebooks Nguyễn Hoàng Cương §Þnh lÝ 10.6. Gi¶ sö tån t¹i mét 0A(n,k,λ) .Khi ®ã k≥ n+1 Chøng minh: Cho A lµ mét 0A(n,k,l) trªn tËp kÝ hiÖu X={0,1...n-1}.Gi¶ sö π lµ mét phÐp ho¸n vÞ cña X vµ ta ho¸n vÞ c¸c kÝ hiÖu trong mét cét bÊt k× cña A theo phÐp giao ho¸n π.KÕt qu¶ lµ ta l¹i cã mét 0A(n,k,l).Bëi vËy b»ng c¸ch ¸p dông liªn tiÕp c¸c phÐp vÞ kiÓu nµy ,cã thÓ xem (mµ kh«ng lµm mÊt tÝnh tæng qu¸t) r»ng hµng ®Çu tiªn cu¶ A lµ (00...0). TiÕp theo ta sÏ chØ ra r»ng mçi kÝ hiÖu chØ xuÊt hiÖn ®ïng n lÇn trong mçi cét cña A.H·y chän hai cét (ch¼ng h¹n c vµ c’)vµ cho X lµ mét kÝ hiÖu bÊt k× .Khi ®ã víi mçi kÝ hiÖu x’ tån t¹i mét hµng duy nhÊt cña A trong ®ã x ë cét c vµ x’ ë cét c’.Cho x’ thay ®æi trªn X ta thÊy r»ng x xuÊt hiÖn ®óng n lÇn trong cét c. V× hµng thø nhÊt lµ (00...0) nªn ta ®· vÐt c¹n c¸c kh¶ n¨ng xuÊt hiÖn cña c¸c cÆp ®−îc s¾p (0.0).Bëi vËy kh«ng cã mét hµng nµo kh¸c cã nhiÒu h¬n mét kÝ hiÖu o.B©y giê ta sÏ ®Õm sè c¸c hµng chøa Ýt nhÊt mét kÝ hiÖu 0.Tæng sè lµ 1+k(n-1).Tuy nhiªn tæng nµy kh«ng thÓ lín h¬n tæng sè c¸c hµng trong A (b»ng n2).Bëi vËy 1+k(n-1)≤n2 hay k≤n+1 nh− mong muèn . B©y giê ta sÏ ®−a ra mét cÊu tróc cho m¶ng trùc giao cã λ=1 ,trong ®ã k=n .Trong thùc tÕ ®©y chÝnh lµ cÊu tróc ®· dïng ®Ó thu ®−îc m¶ng trùc giao nªu ë h×nh 10.5. §Þnh lÝ 10.7 Gi¶ sö p lµ mét sè nguyªn tè.Khi ®ã tån t¹i mét m¶ng trùc giao 0A(p.p.1). Chøng minh: M¶ng nµy sÏ lµ mét cÊp p2×p,trong ®ã c¸c hµng ®−îc lËp chØ sè trong ZPxZP vµ c¸c cét ®−îc lËp chØ sè trong ZP .PhÇn tö ë hµng (i,j) vµ cét x ®−îc tÝnh b»ng i.x+j mod p. Gi¶ sö chän hai cét x vµ y,x≠y,vµ hai kÝ hiÖu a,b.Ta cÇn t×m mét hµng duy nhÊt (i,j) sao cho a n»m trong cét x vµ y n»m trong cét y cña hµng (i,j).V× thÕ cÇn gi¶i hai ph−¬ng tr×nh: a=i.x+j b=i.y+j Trang 11
Vietebooks Nguyễn Hoàng Cương theo c¸c Èn i vµ j (trong ®ã tÊt c¶ c¸c phÐp tÝnh sè häc ®−îc thùc hiÖn trong tr−êng Z).Nh−ng hÖ nµy cã nghiÖm duy nhÊt: i=(a-b)(x-y)4mod p j=a-y.x mod p Bëi vËy ta cã mét m¶ng trùc giao. NhËn xÐt r»ng mét 0A(n,n,1) bÊt k× cã thÓ më réng thªm mét cét ®Ó t¹o thµnh 0A(n,n+1,1)(xem c¸c bµi tËp ).V× thÕ dïng ®Þnh lÝ 10.7 cã thÓ nhËn ®−îc v« h¹n c¸c 0A ®¹t ®−îc giíi h¹n cña ®Þnh lÝ 10.6 víi dÊu b»ng. §Þnh lÝ 10.6 cho biÕt r»ng λ>1 nÕu k>n+1.Ta sÏ chøng minh mét kÕt qu¶ tæng qu¸t h¬n khi ®Æt giíi h¹n d−íi cña λ nh− mét hµm cña n vµ k.Tuy nhiªn,tr−íc tiªn cÇn ®−a ra mét bÊt ®¼ng thøc quan träng sÏ dïng trong chøng minh. Bæ ®Ò 10.8. Gi¶ sö b1....bm lµ c¸c sè thùc.Khi ®ã: n n m∑ b12 ≥ (∑ b1 ) 2 m =1 m =1 Chøng minh ¸p dông bÊt ®¼ng thøc Jensen(§Þnh lÝ 2.5) víi f(x)=-x2 vµ a1=1/m.1≤i≤m.Hµm f lµ liªn tôc lµ vµ lâm.V× thÕ ta nhËn ®−îc : 2 b12 ⎛ m b1 ⎞ m ∑ m ≤ ⎜∑ m ⎟ ⎝ i =1 ⎠ i =1 Tõ ®©y dÔ dµng rót ra kÕt qu¶ mong muèn. §Þnh lÝ 10.9. Gi¶ sö tån t¹i mét 0A(n,k,λ).Khi ®ã k (n − 1) + 1 λ≥ n2 Chøng minh Cho A lµ mét 0A(n,k,λ) trªn tËp kÝ hiÖu X={0,1.....n-1},trong ®ã hµng ®Çu tiªn cña A lµ (0,0....0)(gi¶ thiÕt nµy kh«ng lµm mÊt tÝnh tæng qu¸t nh− ®· thÊy trong ®Þnh lÝ 10.6). Trang 12
Vietebooks Nguyễn Hoàng Cương KÝ hiÖu c¸c tËp hµng cña Alµ R vµ r1 lµ hµng ®Çu tiªn,cho R1=R\{r1}.Víi mét hµng bÊt r cña A,kÝ hiÖu xr chØ sè lÇn xuÊt hiÖn cña 0 trong hµng r.Cã thÓ dÔ dµng t×nh ®−îc tæng sè lÇn xuaat hiÖn cña 0 trong R1.V× mçi kÝ hiÖu ph¶i xuÊt hiÖn ®óng λn lÇn trong mçi cét cña Anªn ta cã: ∑ x r = k (λ .n − 1) r∈R1 B©y giê sè lÇn xuÊt hiÖn cÆp ®−îc s¾p (0,0) ë c¸c hµng trong R1 lµ: ∑ x r ( x r − 1) = ∑r∈R x r2 − ∑r∈R x r r∈R1 2 1 =∑ x − k (λ.n − 1) 2 r∈R2 r ¸p dông bæ ®Ò (10.8) ta cã: (k (λ.n − 1)) 2 ∑ x r2 ≥ λ.n 2 − 1 r∈R1 vµ bëi vËy : (k (λ.n − 1)) ∑ − k (λ .n − 1) x r ( x r − 1) ≥ λ..n 2 − 1 r∈R1 MÆt kh¸c,trong mét cÆp cét cho tr−íc bÊt k×,cÆp ®−îc s¾p (0,0) xuÊt hiÖn trong ®óng λ hµng .V× cã k(k-1)cÆp c¸c cét ®−îc s¾p nªn dÉn ®Õn sè lÇn xuÊt hiÖn cña cÆp ®−îc s¾p (0,0) trong c¸c hµng cña R ®óng b»ng (λ-1)k(k-1).Bëi vËy ta cã: (k (λ .n − 1)) 2 (λ-1)k(k-1)≥ − k (λ.n − 1) λ.n 2 − 1 vµ do ®ã : ((λ-1)k(k-1)+k(λn-1)(λn2-1)≥(k(λn-1))2 Khai triÓn ta cã: λ2kn2-λk.n2-λ2n2+λ2n3-λk+k+λ-λn≥λ2kn2-2λkn+k hay: -λ2n2+λ2n3≥λkn2+λk-λ+λn-2λkn hoÆc λ2(n3-n2)≥λ(k(n-1)2+n-1) Cuèi cïng,chia hai vÕ cho λ(n-1) ta cã : λn2≥k(n-1)+1 §©y chÝnh lµ giíi h¹n cÇn t×m. KÕt qu¶ sau thiÕt lËp sù tån t¹i cña mét líp v« h¹n c¸c m¶ng trùc giao ®¹t ®−îc giíi h¹n nªu trªn víi ®Êu ‘’=’’. §Þnh lÝ 10.10. Gi¶ sö p lµ mét sè nguyªn tè vµ d≥2 lµ mét sè nguyªn.Khi ®ã tån t¹i mét m¶ng trùc giao 0A(p.(pd-1)/(p-1).pd-2 Trang 13
Vietebooks Nguyễn Hoàng Cương Chøng minh: KÝ hiÖu (ZP)d lµ kh«ng gian vÐc t¬ chøa tÊt c¶ bé d trªn ZP.Ta sÏ x©y dùng A (lµ mét 0A(p,(pd-1)/(p-1),pd-2) trong ®ã c¸c hµng vµ c¸c cét ®−îc lËp chØ sè theo c¸c vÐc t¬ trong (ZP)d.C¸c phÇn tö cña A sÏ lµ c¸c phÇn tö cña ZP.TËp hîp c¸c hµng ®−îc x¸c ®Þnh lµ R=(Zp)d):tËp c¸c cét lµ : C = {(c1...cd)∈(Zp)d: ∃j,0≤j≤d-1 ,c1=...=cj=0,cj+1=1} R chøa tÊt c¶ c¸c vÐc t¬ trong (ZP)d,bëi vËy ⏐R⏐=pd.C chøa tÊt c¶ c¸c vÐc t¬ kh¸c kh«ng cã to¹ ®é kh¸c 0 ®Çu tiªn b»ng 1.NhËn thÊy r»ng: pc −1 ⏐C⏐= p −1 vµ kh«ng cã hai vÐc t¬ nµo trong C lµ c¸c béi v« h−íng cña nhau. B©y giê v−ãi mçi vÐc t¬ r’ ∈R vµ mçi c’∈C ta ®Þnh nghÜa: A(r’.c’)=r’.c’ Trong ®ã “.”kÝ hiÖu tÝch trong hai vÐc t¬ (®−îc rót gän theo mod p). Ta sÏ chøng minh A lµ m¶ng trùc giao mong muèn.Cho b’,c’∈C lµ hai cét kh¸c nhau vµ cho x,y∈ZP.Ta sÏ tÝnh sè hµng r’ ®Ó A(r’,b’)=x vµ A(r’,b’)=y.KÝ hiÖu r’=(r1,r2....rd).b’=(b1,b2....bd) vµ c’=(c1,c2....cd).Hai ph−¬ng tr×nh r’.b’=x vµ r’.c’=y cã thÓ ®−îc viÕt thµnh hai ph−¬ng tr×nh tuyÕn tÝnh trong ZP b1.r1+...+bd.rd=x c1.r1+...+cd.rd=y. §©y lµ hai ph−¬ng tr×nh tuyÕn tÝnh víi d Èn r1...rd.V× c¸c béi b’vµ c’ kh«ng ph¶i lµ c¸c béi v« h−íng cña nhau nªn hai ph−¬ng tr×nh trªn lµ ®éc lËp tuyÕn tÝnh.Bëi vËy hÖ nµy cã kh«ng gian nghiÖm (d-2) chiÒu.NghÜa lµ sè c¸c nghiÖm (sè c¸c hµng trong ®ã x n»m ë cét b’ vµ y ë cét c’)b»ng pd-2 theo mong muèn. Ta sÏ lµm mét vÝ dô nhá minh ho¹ c¸ch x©y dùng nµy: VÝ dô 10.3 Gi¶ sö lÊy p=2,d=3,khi ®ã ta sÏ x©y dùng mét 0A(2,7,2).Ta cã : R={000,001,010,011,100,101,110,111} vµ C={001,010,011,100,101,110,111} Ta nhËn ®−îc kÕt qu¶ lµ m¶ng trùc giao nh− trªn h×nh 10.6 Trang 14
Vietebooks Nguyễn Hoàng Cương ⎡0 0⎤ 0 0 0 0 0 ⎢1 1⎥ 0 1 0 1 0 ⎢ ⎥ ⎢0 1⎥ 1 1 0 0 1 ⎢ ⎥ 1 1 0 0 1 1 0⎥ H×nh 10.6.Mét 0A(2,7,2). ⎢ ⎢0 1⎥ 0 0 1 1 1 ⎢ ⎥ ⎢1 0⎥ 0 1 1 0 1 ⎢0 0⎥ 1 1 1 1 0 ⎢ ⎥ ⎢1 1⎥ ⎣ ⎦ 1 0 1 0 0 10.3.3§Æc tr−ng cña m∙ x¸c thùc . Cho tíi giê ta ®· nghiªn cøu c¸c m· x¸c thùc nhËn ®−îc tõ c¸c m¶ng trùc giao.Ta còng ®· xem xÐt c¸c ®iÒu kiÖn tån t¹i cÇn thiÕt vÒ viÖc x©y dùng c¸c m¶ng trùc giao .VÊn ®Ò ë ®©y lµ liÖu cã c¸c ph−¬ng ph¸p kh¸c tèt h¬n c¸c m¶ng trùc giao kh«ng?Tuy nhiªn hai ®Þnh lÝ ®Æc tr−ng sÏ cho biÕt r»ng nÕu chØ giíi h¹n mèi quan t©m tíi c¸c m· x¸c thùc cã x¸c suÊt lõa bÞp nhá tíi møc co thÓ th× vÊn ®Ò trªn kh«ng cÇn ph¶i ®Æt ra n÷a. Tr−íc tiªn ta sÏ chøng minh mét ®Þnh lÝ ®¶o mét phÇn cña ®Þnh lÝ 10.5. §Þnh lÝ 10.11. Gi¶ sö (S,A,K,E)lµ mét m· x¸c thùc trong ®ã ⏐R⏐=n vµ Pd0=Pd1=1/n.Khi ®ã ⏐K⏐≥n2.H¬n n÷a ⏐K⏐=n2 khi vµ chØ khi cã mét m¶ng trùc giao 0A(n.k.l) trong ®ã ⏐S⏐=k vµ pK(K)=1/n2 víi mäi kho¸ K ∈K . Chøng minh: Cè ®Þnh hai tr¹ng th¸i nguån tuú ý s vµ s’ ,s=s’ vµ xÐt ph−¬ng tr×nh (10.6).Víi mçi cÆp ®−îc s¾p (a,a’) cña c¸c nh·n x¸c thùc ta x¸c ®Þnh : Ka,a’={K∈K :eK(s)=a,eK(s’)=a’}. Khi ®ã ⏐K⏐>0 víi mäi cÆp (a,a’).Còng thÊy r»ng c¸c tËp Ka,a’ nµy rêi nhau (cã n2 tËp).Bëi vËy K≥n2. B©y giê gi¶ sö r»ng ⏐K⏐=n2 .Khi ®ã trÞ ⏐Ka,a’⏐=1,víi mäi cÆp (a,a’) vµ tõ ph−¬ng tr×nh (10.6) ,cho ta thÊy r»ng pK(K)=1/n2 víi mäi kho¸ K ∈K . VÊn ®Ò cßn l¹i lµ ph¶i chøng tá ma trËn x¸c thùc sÏ t¹o nªn ma trËn trùc giao 0A(n,k,l) .XÐt c¸c cét lÊy chØ sè theo c¸c tr¹ng th¸i nguån s vµ s’.V× ⏐Ka,a’⏐=1 víi mäi (a,a’) nªn mçi cÆp ®−îc s¾p xuÊt hiÖn dóng mét lÇn trong hai cét nµy.V× s,s’ lµ tuú ý nªn mçi cÆp ®−îc s¾p xuÊt hiÖn ®óng mét lÇn trong hai cét bÊt k×. Trang 15

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.