Hướng dẫn các chứng minh mà không cần tiết lộ thông tin phần 3 ppt

Vietebooks Nguyễn Hoàng Cương

Trang 11

§Ó chøng minh r»ng hÖ thèng chøng minh lµ kh«ng tiÕt lé th«ng tin

hoµn thiÖn ta cÇn mét phÐp biÕn ®æi chung ®Ó x©y dùng mét bé m« pháng S*

tõ V* bÊt kú. Ta sÏ tiÕp tôc thùc hiÖn viÖc nµy ®èi víi hÖ thèng chøng minh

cho tÝnh ®¼ng cÊu ®å thÞ. Bé m« pháng sÏ ®ãng vai trß cña Peggy sö dông V*

nh− mét “ch−¬ng tr×nh con” cã kh¶ n¨ng khëi t¹o l¹i. Nãi mét c¸ch kh«ng

h×nh thøc S* sÏ cè g¾ng gi¶ ®Þnh mét yªu cÇu ij

mµ V*sÏ ®−a ra trong mçi

vßng j. tøc lµ S* sÏ t¹o ra mét bé ba hîp lÖ ngÉu nhiªn cã d¹ng (Hj

, Þj

, ρj

) vµ

thùc hiÖn thuËt to¸n V* ®Î thÊy ®−îc yªu cÇu cña nã dµnh cho vßng j. nÕu gi¶

®Þnh ij

gièng nh− yªu cÇu i’j

(nh− ®−îc t¹o bëi V*) th× bé ba (Hj

, Þj

, ρj

) sÏ

®−îc g¾n vµo b¶n sao gi¶ m¹o. nÕu kh«ng thÞ bé ba nµy sÏ bÞ lo¹i bá, S* sÏ

gi¶ ®Þnh mét yªu cÇu míi ij

vµ thuËt to¸n V* sÏ ®−îc khëi ®éng l¹i sau khi

thiÕt lËp l¹i tr¹ng th¸i cña nã vÒ trµng th¸i b¾t ®Çu cña vßng hiÖn thêi . thuËt

ng÷ “tr¹ng th¸i ”®−îc hiÓu lµ c¸c gi¸ trÞ cña tÊt c¶ c¸c biÕn dïng trong thuËt

to¸n.

B©y giê ta sÏ ®−a ra mét m« t¶ chi tiÕt h¬n vÒ thuËt to¸n m« pháng S*.ë

thêi ®Ióm b¸t kú cho tr−íc, trong khi thùc hiªn ch−¬ng tr×nh V* tr¹ng th¸i

hiÖn thêi cña V* sÏ ®−îc ký hiÖu lµ state (V*). Mét m« t¶ gi¶ m· cña thuËt

to¸n m« pháng ®−îc cho ë h×nh 13.7

§Çu vµo: hai ®å thÞ ®¼ng cÊu G1 vµ G2 ,mçi ®å thÞ cã tËp ®Ønh {1...n}

1. T = (G1, G2)

2. For j = 1 to n do

3. X¸c ®Þnh tµng th¸i cò b»ng tr¹ng th¸i (V*)

4. Repeat

5. Chän ngÉu ij

=1 hoÆc 2

6. Chän pj

lµ phÐp ho¸n vÞ ngÉu nhiªn cña {1...n}

7. TÝnh Hj

lµ ¶nh cña Gi

theo ρj

8. Gäi V* víi ®Çu vµo Hj

ta thu ®−îc mét yªu cÇu I’,

9. If ij

= I’j

then

ghÐp (Hj

, ij

, ρj

) vµo ®u«i cña T

Else

ThiÕt lËp l¹i V* b»ng c¸ch x¸c ®Þnh tr¹ng th¸i (V*)

= tr¹ng th¸i cò

10. Until ij

=i’j