`
`FI’NGERPRINTING BY RANDOM POLYNOMIALS
`
`by
`
`Michael O. Rabin
`
`TR-15481
`
`EMCVMW 1015
`EMCVMW 1 0 1 5
`
`
`
`FINGERPRINTING BY RANDOM POLYNGMIALS
`
`my
`
`.
`
`Michael O. Rabin
`
`Department of Mathematics
`The Hebrew University of Jerusalem
`
`and
`
`Department of Computer Science
`Harvard University
`
`
`52mg
`
`
`
`Randomly chosen irreducible polynomials
`
`p(t) e Zz[t]
`
`are used to
`
`”fingerprint” bit-strings. This method is applied to produce a very
`
`simple real—time string matching algorithm and a procedure for securing
`
`files against unauthorized changes.
`
`The method is provably efficient
`
`and highly reliable for everl input.
`
`This research was supported in part by NSF Grant MCS-BO-l27l6 at the
`"I
`University of Ca
`iiprnia at Berkeley.
`
`
`
`1
`1
`
`Fingerprinting by Random Polynomials
`
`by
`
`Michael 0. Rabin
`
`l.
`
`gitflductiol
`
`Prime numbers are used in several contexts to yield efficient random‘
`
`ized algorithms for various problems [ 1,4].
`
`In these applications a
`
`randomly chosen prime
`
`p
`
`is used to "fingerprint” a long character—string
`
`by computing the residue of that string, viewed as a large integer,
`
`modulo p.
`
`This method requires performing fixedwpoint arithmetic on k—bit
`
`integers, where
`
`k = Hog2 pl,
`
`or at least addition/subtrac-ion on such
`
`integers [ 4].
`We propose using a randomly chosen irreducible (prime) polynomial
`
`p(t) e Zz[t] of an appropriate small degree
`
`k
`
`instead of the prime
`
`integer
`
`p.
`
`It turns out that it is very easy to effect a random choice
`
`of an irreducible polynomial.
`
`The implementation of mod p(t)
`
`arithmetic
`
`requires just length k shift registers and the exclusive-or operation 0
`
`:5
`
`k—bit vectors. These operations are fast,
`
`involve simple circuits, and in
`
`VLSI require little chip area.
`
`lhe applications given here are:
`
`a real—time string matching
`
`algorithm; detection of unauthorized changes in a file.
`
`The method ob—
`
`viously extends into other areas.
`
`Polynomial modular computations are used in algebraic error correction
`
`codes.
`
`In these applications one carefully constructs a specific poly—
`
`nomial which is designed to facilitate coding and decoding. Under aSSump—
`
`tion of a
`
`I
`random distribution of all possible error patterns,
`
`the code
`
`/‘:
`
`E?
`
`*1
`
`*
`
`5
`
`
`
`
`
`will detect/correct most occurrences of up to.
`
`R errors for some fixed
`
`2.
`
`1n the style of [5 1, we turn the tables around and instead of applying a
`
`fixed algorithm to (hopefully) randomly distributed inputs, we construct
`
`a randomizing algorithm which is efficient on every input.
`
`By randomizing
`
`the choice of the irreducible polynomial p(t),
`
`we obtain a provably
`
`highly dependable and efficient algorithm for §y§3y_instance of the
`
`string matching problem to be solved;
`
`we successfully protect every file
`
`against any deliberate modification,_etc.
`
`The mathematically provable
`
`efficacy of our method is of particular significance for this last
`
`application.
`
`a.
`
`
`Countinq_and Choosing Irreducible Polynomials
`
`Even though any degree
`
`k
`
`can be used,
`
`implementation is most con—
`
`venient when
`
`k
`
`is prime.
`
`Thus in practice we can use
`
`k = l7, l9,...,3l,
`
`6l, etc.
`
`Lemma l. Let
`k
`be prime.
`The number of irreducible polynomials
`9(x;
`= xk + ah_]xk ‘ + ... + a0 5 Zz[x],
`is
`(2‘ — 2)]K.
`Erggf,
`Let GF(2k)
`= E
`be the Galois field with
`2k
`elements.
`
`.
`
`I
`
`\ u
`
`\
`
`l-1
`
`Every
`
`irreducible polynomial
`
`p(x) e Zz[x] of degree
`
`k
`
`has exactly k
`
`roots
`
`in
`
`E,
`
`and since
`
`l < k
`
`these roots are in
`
`E — Zn.
`
`henCe mlx
`
`(see [.33).
`
`Since
`
`k
`
`is prime,
`
`m = k.
`
`I.e., every
`
`._.
`
`0,; E -
`
`Z
`
`is a root of an irreducible polynomial of degree
`
`7‘?
`
`thus the set
`
`E — 29
`
`is partitioned into sets of
`
`k
`
`elements,
`
`where
`
`each set consists of all
`
`roots of an irreducible polynomial
`
`
`
`3
`
`f e Ze[x] of degree
`
`way.
`
`It follows that the number of these polynomials is
`
`k, and all such polynomials are obtained in this
`k
`(2 2)/k.
`
`3
`
`Consider a fixed prime
`
`k,
`
`say
`
`k = 3i,
`
`how do we randomly choose
`
`t31 + b1t30 + ... e ZZEt]? we shall do this
`an irreducible polynomial
`by calculating within the field E = GF(2k) of
`2k
`elements.
`II
`
`To this end we need one_irreducible polynomial
`
`f(x) = x“ + a1xL ‘ +
`
`I.’
`
`+ ... e 22[x].
`
`The elements of
`
`E will be the k-tuples
`
`v = (c],.. ..ck),
`
`c. e 22.
`
`The addition of two elements is component-wise.
`
`To find the
`
`product 7-5, where
`
`6 = (dl""’dk)’
`
`calculate (in
`
`ZZExl)
`
`the
`
`residue
`
`ems»—
`
`elx‘
`
`+ ... + ek a (Clx
`
`+ ... + ck)(d1x
`
`+ ... + dk) mod f(x);
`
`then y-S = (e1,...,ek).
`
`Details of how to computationally implement
`
`the arithmetic of a
`
`finite field can be found in [ 7], where an efficient method for finding
`
`irreducible polynomials of any degree
`
`n
`
`is also given. We a53ume that
`
`irreducible polynomials
`
`f2(x),
`
`f3(x),
`
`... f3](X),..., of small prime
`
`degrees are tabulated once and for all.
`
`We shall now effect a random choice of an irreducible polynomial
`
`P(t) e t31 + ... e Zg[t]. We use the indeterminate
`
`t
`
`to distinguish
`
`these polynomials from the fixed polynomials
`,
`..
`v
`.
`ill .
`randomly an element y: (C1,...,C3]) e Gng
`g
`
`f2(x), 93(x)‘...
`.i
`— £2. Namely.
`
`randomly
`
`. Choose
`
`generate a sequence of 3l bits and if it happens to be
`
`(0,0,...,O)
`
`or
`
`(G,0,...,O,l)
`
`discard it.
`
`The element
`
`1
`
`satisfies, by the proof of Lemma l, a unique
`
`.
`.
`.
`,
`4
`.rreduCible polynomial
`
`‘
`.
`pit,
`
`3l
`
`= t
`
`30
`
`+ blt
`
`+ ... + by»
`.Jl
`
`w
`e 22Lt
`
`‘
`
`.
`
`l0
`
`find it, compute in GF(2 ‘)
`
`(using
`
`J
`i9](x})
`
`the powers
`
`
`
`Y0 = (G,...,l),
`
`y, y2,..
`
`, Y3]. These are 32 vectors in
`
`’
`
`‘3
`
`22"1
`
`and '
`
`are therefore linearly dependent over
`
`22. Hence there exist
`
`b0, b],...,
`
`b31 e 22,
`
`not all
`
`0,
`
`so that
`
`(l)
`
`by”
`
`30
`
`0'—
`
`The system (l) of linear equations can be solved by Gaussian elimination
`
`which is particularly simple over
`J
`is 3l.
`decree of
`
`v over
`
`2
`
`2
`
`Z
`2.
`Thus
`
`bO must be
`Now
`t31 + b t30 + ;..
`1
`
`l
`+ b
`
`because the
`
`3l
`
`is the
`
`irreducible polynomial satisfied by Y-
`
`gemma 2.
`
`The above algorithm gives, for a prime degree
`
`k,
`
`a random
`
`choice with equal probabilities,of an irreducible polynomial
`
`p(t)
`
`("l
`
`4L1
`22[c3
`
`of degree
`
`k.
`
` Proof. Let p](t),...,pd(t),
`
`d = (2k-2)/k,
`
`be an enumeration of all
`
`the different irreducible polynomials of degree
`
`k.
`
`As
`
`in the proof of
`
`Lemma l, GF(2 )
`
`, 29 = 51 U 32 U ... U Sd’ where
`
`Si
`
`consists of the
`
`k
`
`roots of pg(t).
`
`The randomly chosen
`
`k
`y e GF(2 )
`
`- 22
`
`has equal
`
`n.
`probability of falling within each of the Si’ since all
`
`these sets have
`
`the same number of elements.
`
`Thus with probability l/d we chose
`
`y 6 Si’
`
`in which case p(t) = pi(t).
`
`.
`
`u.)
`
`Ari thmet 12 c.
`
`:‘icvo’ul 0 gig)
`
`Henceforth,
`
`throughout
`
`the rest of this paper, all polynomials will
`
`be in 22[t]. Let p(t) = t
`
`k
`
`+ blt
`
`k—l
`
`+ ... + bk
`
`be a polynomial, not
`
`necessarily irreducible.
`
`For an arbitrary polynomial
`
`g{t‘
`
`denote by
`
`gCt)
`
`the residue Res(g,p) of
`
`9 when divided by
`
`p.
`
`A residue
`
`mod p(t)
`
`is a polynomial
`
`c1tk'1 + ... + ck
`
`and will be represented by
`
`5‘
`
`
`
`5
`
`the bit-vector
`
`(C1,...,Ck).
`
`For the sma11
`
`k < 61 which wi11 actua11y
`
`be used, one or at most
`
`two computer words wi11 suffice to store such
`
`vectors.
`
`_
`Let g(t) — X1t
`
`n-1
`
`+ xzt
`
`n-2
`
`+ ... + Xn‘
`
`.
`.+,
`-7
`The computation of g\t)
`
`can be effected in rea1~time as the coefficient bits x],x2,..., are read
`in. Let gi1t) = xltl'] + ... + Xi’
`1 < i < n,
`so that g(t) = gn(t)
`
`and
`
`91+]
`
`= gi't + Xi+1’ 1 < 1 < n-1. Hence
`
`(2)
`
`.. =_.-
`91+]
`9i t + xi+1,
`
`1
`
`<‘g-
`1
`n 1,
`
`and we can work with residues mod p(t) throughout.
`H
`
`,
`.
`and
`
`x e 22,
`
`then
`
`Now, if
`
`r(t)
`
`c1t
`
`+ ... + ck
`
`k-1
`
`(3)
`
`rlt ~t+x = cqtkJ + ... + c t+x + c (b tk_] + ... + b.),
`L
`k
`1
`1
`k
`
`.
`Since
`
`k_
`— b1t
`
`k-1.
`v ... + bk mod p
`
`t
`
`t.
`(recal1 that
`
`bi
`
`,
`— 'bi
`
`‘
`in
`
`29).
`
`So that the corresponding vector is
`
`(4)
`
`(c2,...,ck,x) + c](b],....bk).
`
`The operation {4)
`
`is accomp1ished by a 1eft~shift of the word c1c7...cb,
`.,
`BK
`
`introduction of
`
`x
`
`on the right,
`
`fo11owed by the bit-wise exciusive-or
`
`with
`
`b1b0...hh
`
`if the overf1ow c1
`
`is
`
`1.
`
`'A11
`
`this is very fast when
`
`imp1emented by k~1enqth shift registers.
`
`The iteration (2)
`
`is now very rapid1y calcu1ated with one or two
`
`'
`operations for every incowinq bit
`
`'vl
`x1L1.
`
`
`
`4.
`
`§tring hatching
`II
`
`Let
`
`n
`
`x,...x
`
`n
`
`,
`
`T = J1...y ,
`m
`
`.
`x4,y e {0,l} be bit strings.
`i
`1.
`
`The
`
`string matching problem is to find one or all
`
`indices
`
`i
`
`such that
`
`n = yiyi+1...y
`
`i+nwl'
`
`For any such an
`
`i
`
`we say that the pattern n
`
`matches with the ith substring of length n of the tg§t_ T,
`
`or more
`
`shortly that a match occurs.
`
`In the style of [6 ] we construct a random«
`
`'ized algorithm which for gygrx_
`
`n
`
`and
`
`T
`
`and given
`
`0 <
`
`5 will solve
`
`the string matching problem with probability of error smaller than
`
`5.
`
`Let
`
`k
`
`be the smallest prime such that
`
`k > logz(nme'1).
`
`In all
`
`practical applications
`
`k = 6l
`
`or even
`
`k = 3l will be ample, so that
`
`k—hit words will fit into one or at most
`
`two computer words. Define
`
`\: .
`+
`a(t,
`X]:
`
`:
`
`-.,
`+-c.+l\
`
`q
`
`.l
`ai\t)
`
`:
`
`.tn—h
`.
`y]
`
`'
`.
`~--"y1+n“19 l < i < m—n+l.
`
`a(t) = ai(t).
`is equivalent to
`i
`index
`a match For
`Obviously.
`Choose randomly an irreducible polynomial
`p(t) = tk + b tk‘]+.. +b
`1
`'
`
`k'
`
`Denote,as in Section 2, by git)
`
`the residue modulo p(t) of the poly-
`
`nomial g(t).
`
`If alt) =
`time.
`Compute alt), tn_], a}(t). This is done in real
`31(t)
`output "match for index l.” At the ith stage we have stored
`
`ait), tn-', akit), 0(t), i.
`Each of the first four is a k—bit word and
`
`i
`
`is a pointer into the text
`
`T.
`
`Compute
`
`,,
`P
`
`1‘11
`
`Z [7”
`”
`\dj\t) :-
`
`+
`.y1'
`
`This
`
`is done as in Section 2, except that if
`
`‘«+ + '.
`n “ *"i.
`/
`..
`Y1+n '0“ pKtl
`.,
`.
`
`‘kr
`'.
`1
`
`=
`
`
`we start by doing an
`
`.
`_
`.
`-*
`.
`exclUSive-or or the words corresponding to ai(t)
`
`and
`
`*n~l
`L
`
`.
`
`If
`
`flit} = a} 1(t)
`
`then output ”hatching for i+l."
`
`The updating from ai(t)
`
`to di+l(t)
`
`requires a fixed number of operations per text symbol,
`
`i.e., is done in real
`
`time.
`
`
`
`7
`
`For any pattern n = x]...x
`Theorem 3.
`if
`T = y]...ym,
`and text
`___
`k > logz(nme'])
`then the probability that the above randomized algorithm
`
`n
`
`will produce one or more errors is smaller than
`
`5.
`
`Furthermore the
`
`algorithm will discover all actual matches.
`
`Erggf.
`
`The second assertion is obvious, since a(t) = ai(t)
`
`implies
`
`Sit) = E€(t)
`
`for every modulus p(t).
`
`Consider the product
`
`(5)
`
`no =
`
`II
`a(t)fai(t)
`
`(a(t) - aim).
`
`If for a polynomial
`
`p(t)
`
`the algorithm outputs for some
`
`i
`
`“match
`
`for index i" even though there is no match,then we must have
`
`'Eit)
`
`= a.(t)
`
`and a(t) # ai(t). Hence p(t)
`
`divides H(t), which we write asv
`
`nitllH
`
`"“
`
`t).
`
`Conversely, if for an irreducible polynomial
`r~
`or H(t). But
`
`must divide some factor a(t) - ai(t)
`
`then
`
`a{t) = Eg(t,
`
`p(t)!H(t}
`
`then p(t)
`
`while
`
`a(t) # ai{t), so that if this p(t)
`
`is used in the algorithm it
`
`produces a wrong output.
`
`Let p](t),...,p9(t)
`
`be a list of all
`
`the irregucjgfljg polynomials
`
`of degree
`
`k which divide H(t).
`
`Then their product Pit)
`
`also divides
`
`H(t). Consequently
`
`/\ O3 \../
`
`(Q K
`
`H 3 (D '(2
`
`[I
`
`‘U
`
`‘. (D (Q I {I‘ 2I:
`
`The right hand inequality holds because H(t)
`
`is a product of at most
`
`m—n
`
`factors each of degree at most
`
`n.
`
`From (6) we have
`
`2 < nm/k.
`
`Thus
`
`for every pair n,t of pattern and text, at most
`
`nm/k
`
`irreducible
`
`polynomial
`
`p(t)
`
`of degree
`
`k will produce an error when used in the
`
`algorithm.
`
`
`
`8
`
`By Lennm l, the total number of all
`
`irreducible polynomials of
`
`degree
`
`k
`
`is
`
`N > nme'1/k.
`
`h
`k
`N = (2 ~2)/k “J2“/ W
`
`we have
`k > logz{nme'])
`Since
`The probability that for a randomly chosen p(t)
`the
`
`algorithm will produce an error, equals the number
`
`t of error producing
`
`polynomials divided by the number
`
`N of all
`
`irreducible polynomials of
`
`degree
`
`k.
`
`Thus we get
`
`Pr(p(t)lAlgorithm produces error) < (nm/k)/(nme"]/k).= e.
`
`a
`
`The only part of the string matching algorithm which is not strictly
`
`k.
`real-time is the random choice of p(t) of degree
`will give high reliability,
`the choice of p(t) Will
`
`Since
`involve
`
`k = 3 log2 m
`(3 log2 mlz
`
`exclusive-or operations on k-bit vectors (for the Gaussian elimination), and
`
`is negligible as compared to the [1! = m
`
`steps of the algorithm. Alterna-
`
`tively, one can prepare in advance a list of randomly chosen polynomials
`
`from which p(t) will be selected in one step.
`
`6
`Illustrating Theorem 3,
`assume that
`n =
`lnl = lOOO,
`m = {II = l0 ,
`e = 2-30.
`Then
`k = 6l satisfies
`k > logz(nme-])
`so that by using
`
`polynomials of degree 6l,
`i.e., Sl-bit words,
`the probabilit of error
`for every particular pair of pattern/text is at most
`2-30 “/10'9.
`If we are worried about errors having probability lO'9 we could use
`
`a larger
`
`k.
`
`If, however, we do not want
`
`to move to larger wordulength
`
`then we can randomly choose two irreducible oolynomials p1(t),
`
`pzft)
`
`of degree bl and run the algorithm twice, either in parallel or by inter-
`
`leaving steps, one time with
`
`p}
`
`and another time with
`
`p2.
`
`Since the
`
`error probabilities are independent,
`
`the probability of a wrong output
`
`is 10'“.
`
`The method of computing residues modulu a polynomial can be combined
`
`with anyone of the algorithm in
`
`[ 43
`
`to produce efficient solutions to the
`
`other pattern matching problems such as two and higher—dimensional
`
`
`
`99
`See [2,5] for non-randomized string
`
`matching problems, solved there.
`
`matching algorithms.
`
`5.
`
`
`Protection gjmfjles
`
`We shall use irreducible polynomials to "fingerprint" files so that
`
`any unauthorized change will be detected with a very high probability.
`
`Furthermore, updating the fingerprint when the file is locally modified
`
`in an authorized change,
`
`is very simple.
`
`The method will use a randomly chosen irreducible polynomial
`
`p(t)
`
`of an appropriate degree
`
`k
`
`(k = 6l will be ample). This polynomial,
`
`actually k-bit word,
`
`is chosen by the guardian of the filing system‘s
`
`security and will be kept secret.
`
`A file F will be fingerprinted and
`
`the fingerprint ?(t), a polynomial of degree k-l, will be securely
`
`kept by the guardian.
`
`To check whether
`
`F was tempered wit.,
`
`the file
`
`is again fingerprinted and the current fingerprint
`
`F1
`
`is compared with
`
`the stored value F.
`
`If F] #'F then the guardian knows that the file
`
`was changed without authorization.
`
`The method for updating the fingerprint
`
`F when author‘zed changes
`
`are made is detailed later on.
`
`The same polynomial
`
`p will be employed to fingerprint all
`
`the
`
`files
`
`F1, F2,...
`
`in the system.
`
`An arrangement must be made for the
`
`guardian to securely store
`
`p,
`
`and the fingerprints
`
`‘?], ?é,.=.
`
`.
`
`The
`
`fingerprinting and updating computations must be performed securely so
`
`that none other than the guardian can access
`
`p or the
`
`?L
`
`In view of
`
`the simple computations involved in the fingerprinting and the small
`
`amOunt of information requiring secure storage, namely just one word per
`
`file, it is feasible to construct a special purpose “box” for handling
`
`the security check algorithm.
`
`The box is attached to the system and the
`
`pages of the file pass through it, but none of the secret numbers ever
`
`leaves the box.
`
`Assume that the file F
`
`has
`
`m
`
`pages
`
`P
`
`P
`0,..., m—l
`
`and that eacn
`
`page stores up to
`
`n bits,
`
`If
`
`P;
`
`=
`
`~. x.
`il 12
`
`...
`
`X-
`lH’
`
`define
`
`
`
`
`
`
`
`-12-
`
`-
`Pi(t) ’-xil.+ ... + Xint
`
`n—l
`
`,
`
`,
`_
`_
`_
`r“) _ pO‘t)
`
`+ P](t)t
`
`n
`
`+
`
`.n(r'I-l)
`V
`4. Pm_1(t)t
`
`Choose randomly an irreducible polynomial
`
`p(t) of prime degree
`H
`
`'§i(t) = res (Pi(t),p(t)), then
`Denote, as before,
`Section 2, this P{(t)
`is very rapidly calculable.
`
`k—l.
`
`deg 53
`If
`r(t) = tn
`
`k.
`
`As
`
`in
`
`then the residue F(t) = res (F(t),p(t))
`
`is given by
`
`(7)
`
`fit) =50m + P1(t)vr(t) +
`
`+3
`
`(tl-r(t)m']
`
`lhe fingerprint for the whole file F will be $(t). This residue is
`n
`r(t) = t mod p(t)
`
`also rapidly computable. Namely, calculate
`
`by any
`
`Read
`of the rapid exponentiation algorithms.
`in real-time.
`Compute F (t), E (t)-r(t),
`
`l
`1
`
`P0
`r(t)2,
`
`in and compute 56(t)
`and
`
`30(t) + $1it)-r(t),
`
`etc.
`
`The general step involves computation of
`
`(
`
`and two multiplications modulu p(t) of k—ledegree polynomials.
`
`The latter multiplications require little time compared to the computation
`of
`'§i(t).
`even if the straightforward method is used.
`Formula (7} suggests hOWIdeating of ?{t)
`is done locally. Assume
`
`that F(t). p(t)t
`
`r(t)
`
`are securely stored and that page
`
`Pi
`
`is to be
`
`modified into P'g.
`I
`
`As
`
`Pi
`k
`
`is read in.
`
`the residue 5;(t)
`I
`
`is recomputed.
`
`T
`y
`s-
`1-
`A.>O tumou-e
`
`'«'s\’
`A-
`n
`u f-
`li\L) - res tilt,
`
`,pl,
`
`'a
`~~
`'
`~
`~'
`-
`thlS again by any or toe loplu
`
`exponentiation algorithms. After P'i
`
`is produced, compute 5T;(t).
`
`The updated fingerprint is
`
`To illustrate the reliability of the security-check algorithm let us
`
`
`
`11
`
`11
`
`work out an example rather than write general
`
`formulas,
`
`
`Proposition.
`
`if a file F consists of a thousand pages each containing
`
`up to 4000 bytes (32,000 bits) and we use polynomials of'degree 61.
`
`then the probability of any unauthorized change in
`
`F
`
`to go undetected
`
`is at most 2'46,
`
`i.e., completely negligible.
`
`Proof. Assume that page
`___.._
`
`Pi was changed into page P:,
`1
`
`let Flt)
`
`denote, as before,
`
`the fingerprint (7 ) of the original file F
`
`and
`
`let Falt)
`
`denote the fingerprint of the modified file F'.
`
`The
`
`change will be detected if
`
`F f F.
`
`We have
`
`deg F(t) = deg F‘(t) = 32-105
`
`so that-
`
`deg (F - F') < 32-l06 < 225.
`
`If F(t) - F'(t) # 0
`
`then it has at most
`
`2‘5/61
`
`irreducible divisors of degree 6l.
`
`Since there are
`
`261/61
`
`irreducible polynomials of degree 6l,
`
`the probability that for a randomly
`
`chosen such p(t)
`
`we have
`
`'FT ='F is at most
`
`(245/6l)/(261/6l) = 2'46.
`
`
`Remark. We can dispense with the assumption that the file F
`
`is a
`
`sequence of numoered pages and consider
`
`F
`
`as a set
`
`Q = {P0,...,Pm_1}
`
`of pages.
`
`We shall use two irreducible polynomials,
`
`p(t)
`
`of
`
`degree
`
`k
`
`and q(t) of degree
`
`k] 2 k., Denote by
`
`n(P)
`
`the sequence
`
`of coefficient bits of
`
`res(P(t),p(t)).
`
`View n(P}
`
`as an integer,
`
`then
`
`n(P) < 2k.
`
`Define
`
`on) = pI‘IQ 9W git) = res (comm);
`
`O‘Ct) will be the fingerprint of
`
`Q‘
`
`The computation of.
`
`{J
`
`as well as
`
`the updating follow the previous pattern.
`
`The set formulation has the
`
`_,.,"_,——_,-
`
`FE
`li
`
`i
`
`
`
`
`
`further advantage that the f1ngerpr1nt of the union Q'U Q’
`
`of two
`
`disjoint f11es 13 simp1y Q](t) + Q'}(t). We omit
`
`the deta11ed deter—
`
`mination of degrees
`
`k
`
`and
`
`k1 which W111 ensure a desired probabi11ty
`
`e
`
`for a change to go undetected.
`
`BIBLIOGRAPHY
`
`Probab11ist1c machines can use 1ess running time.
`Freivo1ds, R.
`lgjggmgjlig_Procc5s1ng 77, Gi1chr15t, 8. (ed.), pp. 839-812.
`
`T1me~snace optimal string matching.
`Ga111, Z. and J. Se1feras
`
`13th Annuai
`fiCM STOC (1981), pp. 106~113.
`
`
`:gpics jg fl;.ebra, §g§_§gj§jcn. Xerox Co11ege
`Herstein, 1.1.
`Oub1ishing, Lex1n3on MA, 1375.
`
`Karp, R.M. are H .O. Rabin. Efficient randomized pattern—matching
`a1gor1thms.
`sutmitted for pub11cat1on.
`
`FaStgpatterz1maMch ng
`Knuth, D. E. , Morris, 3.8. and V.R. Pratt.
`in str1ng;
`§§AM J. an Comcutjggfi 391;_§ {1977), pp. 323- 3L‘SO
`
`In fi1ggr1hms_j:gugggg1ex1tg,
`Probab§1ist1c e1gor1thms.
`Rabin,MM0.
`2:155
`'Ed. ). Academ1c
`Recent_Resu1tsan'ew_Dirert10n:S, J.F. Tr u
`Press, New York,1976, pp. 21- 40.
`*
`
`Rab1n, M. 0 Pro’abilisiic a1ger1thms in f‘. n1te f1e1d3.
`onComggtqu) V01.
`3
`(--980), pp. 2735280.
`
`sign J.
`
`1.
`
`2.
`
`3
`
`4.
`
`5.
`
`6.
`
`7.
`
`
`
`
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
