`
`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.
`
`
`
`