wu :: forums « wu :: forums - cormen book problem » Welcome, Guest. Please Login or Register. Nov 28th, 2024, 4:21pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    medium (Moderators: Eigenray, Icarus, william wu, towr, SMQ, Grimbal, ThudnBlunder)    cormen book problem « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: cormen book problem  (Read 2037 times) Dheeraj Kumar jain Newbie     Gender: Posts: 4 cormen book problem   « on: Aug 16th, 2008, 9:47pm » Quote Modify 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). « Last Edit: Aug 16th, 2008, 10:50pm by william wu » IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: cormen book problem   « Reply #1 on: Aug 17th, 2008, 1:38am » Quote Modify You mean they send A(x) and B(x) mod q, right? IP Logged Dheeraj Kumar jain Newbie     Gender: Posts: 4 Re: cormen book problem   « Reply #2 on: Aug 17th, 2008, 2:17am » Quote Modify ya they both know q and x and finally, Alice sends A(x) to Bob  and Bob Sends B(x) to Alice. IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: cormen book problem   « Reply #3 on: Aug 17th, 2008, 3:19am » Quote Modify I mean, the question should be asking about the probability that A(x) 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. IP Logged Dheeraj Kumar jain Newbie     Gender: Posts: 4 Re: cormen book problem   « Reply #4 on: Aug 17th, 2008, 6:56am » Quote Modify 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+a lgo+cormen&pg=PP1&ots=BwOuJG0fIb&sig=uruseMt6Noak_d6sevgS80vEES0&hl=en&sa=X&oi=book_result&resnum=1&ct=result#PPA915,M1 IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: cormen book problem   « Reply #5 on: Aug 17th, 2008, 8:34am » Quote Modify Right, A(x) and B(x) are evaluated mod q.  Hint: how many roots can a polynomial have over any field? IP Logged Dheeraj Kumar jain Newbie     Gender: Posts: 4 Re: cormen book problem   « Reply #6 on: Aug 17th, 2008, 10:03am » Quote Modify ya that must be the hint...bt not getting how to apply that here   IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board