Algebraic Techniques in Frievald's Algorithm: Matrix Product Verification

Randomized Algorithms CS648 Lecture 5 Algebraic Techniques Frievald s Algorithm Fingerprinting Techniques 1

FRIEVALDS TECHNIQUE APPLICATION MATRIX PRODUCT VERIFICATION 2

FrievaldsAlgorithm (Rusins Frievald, 1977) Problem: Given three ?-by-? matrices ?,?, and ?, determine if ? ? ?. 1 2 ? 1 2 ? ? ? ? Best deterministic algorithm: ? ? ?; Verify if ? = ? ? Time complexity: ?(? ), current value of < 2.37 3

FrievaldsAlgorithm (Rusins Frievald, 1977) 1 0 1 1 0 ? ? ? ? 1 0 1 1 0 ? ? ? 4

FrievaldsAlgorithm (Rusins Frievald, 1977) RandomProductVerify(?,?,?) Let ? be a ?-by-1 matrix (vector) whose elements are selected randomly uniformly and independently from {0,1}. ? ? ? ; ? ? ? ; ? ? ? If(? = ?) output AB=C elseoutput AB C Time complexity: ?(?2) 5

FrievaldsAlgorithm (Analyzing error probability) Question: If ? ? ?, what is the probability that the algorithm outputs AB=C ? Let ? = ? ? ? Observation: If ? ? ?, then surely ? is not a null matrix. Error Probability of the algorithm = P( ? ? ? = ? ? ) ? ? ? = ? ? ? ? ? ? ? = ? (? ? ?) ?= ? ? ? = ? ? ? = ? null vector 6

FrievaldsAlgorithm (Analyzing error probability) ?(? ? = ?) depends upon ?. So what to do ? Our goal is to get an upper bound on this probability. So we start with the least information about ?, which is: There is at least one non-zero element in ?. ? 1 2 ? 1 2 ? Let this element be ??,?. ? P(? ? = ?) = P( ??? ? = 0) ? ? P(?? ? = 0) So we need to focus on the product of ?th row and vector ?. 7

FrievaldsAlgorithm (Analyzing error probability) ? 1 2 ? 1 2 P(?? ? = 0) = P(??1 ?1+ + ??? ?? = 0) ? The underlying sample space has 2? elementary events. Convince yourself that it is indeed difficult to calculate this probability from standard tools which you know. ? ? ? Here we shall introduce a yet another simple but very powerful probability tool 8

Probability tool: Partition of sample space A set of events ?1, ,??defined over a probability space (?,P) is said to induce a partition of ? if ?=1 ?? = ? ?? ??= for all? ? ? ?3 ?2 ?4 ?5 ? ?1 ?6 Theorem: (Partition theorem) Given an event ?, we can express P(?) in terms of a given partition as: P(?) = ?P(? ??) = ?P(?| |??) P(??)using conditional probability 9

Question: When to use the Partition theorem ? Let be ? an event defined over a probability space (?,P). Suppose it turns out that it is not easy to calculate or get a good bound on P(?) directly using the standard tools. In such situation, one may explore the following possibility: Try to design a partition {?1, , ??} of the sample space such that P(?|??) is easy to calculate. This may be used to calculate P(?). IMPORTANT: Most of the times, P(?|??) turns out to be independent of ?. In this case, P(?) can be bounded directly as follows. If P(?|??) ? for every possible value of ?, then P(?) = ?P(? | |??) P(??) ?? P(??) = ? ?P(??) = ? 10

FrievaldsAlgorithm (Analyzing error probability) ? P( ??1 ?1+ + ??? ?? = 0 ) = ?? Suggestion: Think of some suitable partition of ? that will enable you to use the partition theorem effectively to calculate P(?). We shall use the partition defined by the values taken by all the random variables excluding ??. Think over this partition before proceeding further. 11

FrievaldsAlgorithm (Analyzing error probability) ? P( ??1 ?1+ + ??? ?? = 0 ) = ?? Question: What is the probability of ?conditioned on any arbitrary but fixed values taken by all??,? ? ? Answer: Consider any ? 1 values ?1, , ?? 1, ??+1, ,?? 0,1 . We are interested in the probability of event ? conditioned on ?1= ?1, ,?? 1= ?? 1,??+1= ??+1, ,??= ?? . This probability can be expressed as : P( | ?1= ?1, ,?? 1= ?? 1,??+1= ??+1, ,??= ??) 0 = P(??,1 ?1+ + ??,? 1 ?? 1+ ??,? ??+ ??,?+1 ??+1+ ??? ?? = 0) = P(??,? ??= (??,1 ?1+ + ??,? 1 ?? 1+ + ??,?+1 ??+1+ ??? ??)) = P(??= (??,1 ?1+ + ??,? 1 ?? 1+ + ??,?+1 ??+1+ ??? ??)/??,?) Could be 0, 1 or some other number 12

FrievaldsAlgorithm (Analyzing error probability) Theorem: The probability that algorithm RandomProductVerify(?,?,?) makes an error is at most . Note: There is nothing magical about . If each element of the random vector is selected randomly uniformly and independently from a set of ? values, the corresponding probability of error will be ? ? . Question: How to reduce the error probability to ( )? ? Answer: repeat the algorithm ? times. (think over this answer carefully before proceeding further) 13

FrievaldsAlgorithm (reducing the error probability) RandomProductVerify(?,?,?) Repeat ? times { Let ? be a ?-by-1 matrix (vector) whose elements are selected randomly uniformly and independently from {0,1}. ? ? ? ; ? ? ? ; ? ? ? If(? ?) { output AB C ; break} } output AB = C Time complexity: ?(??2) Error probability: ( )? 14

FrievaldsAlgorithm (final result) Theorem: Given three ?-by-? matrices ?,?, and ?, there is a Randomized Monte Carlo algorithm which determines ? ? ?. The running time is ?(?2log ?), and the error probability is less than ? 2. 15

FINGERPRINTING APPLICATION CRYPTOGRAPHY 16

PRIME NUMBERS (SOME BASIC FACTS) 17

How many primes less than ? ? ? Primes less than ? 100 25 1000 168 10000 1229 100000 9592 1000000 78498 ? ? log ? 18

How many primes less than ? ? ? Theorem: The number of primes less than ? is log ?. [An elementary proof: Paul Erd s, 1949 ] Notation: ? ? :the number of primes less than ?. 19

Prime factors of a number ?? Question: How many prime factors are for a positive integer ? ? Answer: less than log?. Proof: just use unique prime factorization theorem (every integer can be uniquely expressed as product of powers of prime numbers. For example: 3500=22 53 7) The fact that every prime factor must be 2 20

File A File B Aim: To determine if File A identical to File B by communicating fewest bits ? 21

Question: What is a File ? Answer: A bit string. 22

Visualize a file as a binary number File A = ?0 ?1 ?2 ?? 1 File B = ?0 ?1 ?2 ?? 1 ? 12? ?? ? 12? ?? ?A= ?=0 ?B= ?=0 (trivial) Observation: File A = File Bif and only if ?A= ?? Question: How large a number can ?A (or ?B) be ? Answer: less than 2?. 23

RandomEqualityChecking-Protocol(?,?) Processing at the sender computer : 1. Let ? be a prime number selected randomly uniformly from [2,?] 2. ? ?A mod ?; 3. sender sends (?,?) to receiver . Processing at the receiver computer: 1. (?,?) is received from sender. 2. ? ?B mod ?; 3. If(? = ?) send A=B to the sender else send A B to the sender Number of Bits transmitted: ? ??? ? 24

RandomEqualityChecking-Protocol (bounding the error probability) Question:If ?A ??, what is the probability that the protocol concludes A=B ? Let ? = |?A ??| Observation: If ?A ??, then surely ? > ?. The protocol makes an error iff ?A ??? ? = ?B ??? ? ?A ??? ? ?B ??? ? = ? (?A ??) ??? ?= ? ? divides ? ? isone of the prime factors of? Error probability = ?? How many prime factors can ? have ? at most ? since ? is less than 2?. How many choices are there for ? ? ?(? ) since? is a random prime number from [?,?] ? ?(?) 25

RandomEqualityChecking-Protocol (bounding the error probability) ? Lemma: The probability RandomEqualityChecking-Protocol makes an error is ?(?). Question: How large should ? be in order to achieve error probability < 1 ? ? Answer: Pick ? > 4 ?2log ?. ? ?(?) log ? . 4 ?2log ? 2 log ?+2+log log ? > > ?2for ? > 4 Bits transmitted: ? ??? ? = O(??? ?) 26

Please go through the slides of this lecture carefully and patiently. You are welcome to discuss any doubt in the next class (Saturday, 17th August) 27