wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> cormen book problem
        
(Message started by: Dheeraj Kumar jain on Aug 16^th, 2008, 9:47pm)

Title: cormen book problem
Post by Dheeraj Kumar jain on Aug 16^th, 2008, 9:47pm

Alice has a copy of a long n-bit file A = (an-1, an-2, . . . , a0) and Bob similarly has an n-bit
file B = (bn-1, bn-2, . . . , b0). Alice and Bob wish to know if their files are identical. To avoid
transmitting all of A or B, they use the following fast probabilistic check. Together, they select
a prime q > 1000n and randomly select an integer x from {0, 1, . . . , q - 1}. Then, Alice
evaluates
A(x)=(a0*x^0+a1*x^1...+ai*x^i......an*x^n)
and Bob similarly evaluates B(x). Prove that if A is not equal to B, then there is at most one chance in 1000 that
A(x) = B(x), whereas if the two files are the same, A(x) is necessarily the same as B(x).

Title: Re: cormen book problem
Post by Eigenray on Aug 17^th, 2008, 1:38am

You mean they send A(x) and B(x) mod q, right?

Title: Re: cormen book problem
Post by Dheeraj Kumar jain on Aug 17^th, 2008, 2:17am

ya they both know q and x and finally, Alice sends A(x) to Bob and Bob Sends B(x) to Alice.

Title: Re: cormen book problem
Post by Eigenray on Aug 17^th, 2008, 3:19am

I mean, the question should be asking about the probability that A(x) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif B(x) mod q, since if x>1, A(x) = B(x) implies A = B, not to mention the fact that the integer A(x) would take more than n bits to send.

Title: Re: cormen book problem
Post by Dheeraj Kumar jain on Aug 17^th, 2008, 6:56am

You can see Q at following link. Page no : 915, Q no 32.2-4.
http://books.google.co.in/books?id=NLngYyWFl_YC&dq=introduction+to+algo+cormen&pg=PP1&ots=BwOuJG0fIb&sig=uruseMt6Noak_d6sevgS80vEES0&hl=en&sa=X&oi=book_result&resnum=1&ct=result#PPA915,M1

Title: Re: cormen book problem
Post by Eigenray on Aug 17^th, 2008, 8:34am

Right, A(x) and B(x) are evaluated mod q. Hint: [hide]how many roots can a polynomial have over any field[/hide]?

Title: Re: cormen book problem
Post by Dheeraj Kumar jain on Aug 17^th, 2008, 10:03am

ya that must be the hint...bt not getting how to apply that here :(