HASH1››    Polynomial/Sequential hashing›    -----------------------------››Suppose we have a finite commutative›ring with identity, R and consider›the power series ring R'=R[[x]].›Suppose we have power series p,q with›p*q=1 in R[[x]], that is,›p*q=1 in R'.››Suppose a is in R' and is a›polynomial and deg(a)=D-1, and let›R"=R[[x]]/(x^D), (drop all terms of›degree greater than that of a) and›note that p*q=1 in R".››Consider q, q*q, q*q*q, etc. in R".›This must be finite, so there exist k›and l (k<>l) such that q^k=q^l in R",›or if k<l, multiplying by p^l, q^t=1›in R" where t=k-l.››Given a (D=deg(a)+1), consider the›sequence q*a, q*q*a, q*q*q*a, etc.›in R".››As eventually this MUST yield a›polynomial (in R") with degree=deg(a)›(if nothing else, when we reach k-l,›we will get a*q^t=a in R", and a has›the right degree!), let us pick n as›the first value (n>0) such that›(in R") q^n*a has the same degree›as a (that is, the coefficient of›x^(D-1) is non-zero) (NOTE that as we›do everything mod x^D, we will not›have degree GREATER than x^(D-1)).››Let a'=a*q^n (in R"), which has D›coefficients (as did a)... this is›one to one on polynomials of›degree D-1 (for if a'=b' where a and›b have degree D-1, and n and m are›the exponents used for a and b, we›have in R", q^n*a=q^m*b, if m=n, then›multiplying by p^n we see that a=b,›while if m<n, multiplying by p^m›gives a*q^(n-m)=b in R" and so n was›NOT the first exponent (the one we›should use), but WE SHOULD HAVE USED›AN EXPONENT NO LARGER THAN n-m and IF›n-m were the correct exponent, then›b=a'. Thus, we used the wrong›exponent.››Note that a' has D digits if a does›(so this preserves length) and we›call a' the hashed value of a.››To dehash, we simply multiply (in›R"=R[[x]]/(x^D) where›D-1=deg(a')=deg(a)) a' successively›by p until we get a value of the same›degree... that is a.››As an example, to hash at most four›digits in binary (R=Z_2, R'=Z_2[[x]],›power series in bits using mod 2›arithmetic in multiplying, adding,›power series).››We can take q=1+x and›p=1+x+x^2+x^3+x^4+x^5+..., but as we›are going to work with at most four›digits we can work in R[[x]]/(x^4)›and take p=1+x+x^2+x^3 with›R=Z_2 (mod 2) (p*q=1 mod(x^4) and we›don't need the full series for p if›we limit ourselves to four bits).››For example, the sequence (1,1)=1+x›as a polynomial (D=deg(1+x)+1=2) and›q*(1+x)=1 mod(x^2) in Z_2, wrong›degree (R"=Z_2[[x]]/(x^2)), so we›multiply again and get›q*q*(1+x)=(1+x) mod(x^2) and the›sequence (1,1) is hashed to (1,1).››To dehash it, we take›p*(1+x)=1 mod(x^2) (again wrong›degree, so we multiply by p again to›get p*p*(1+x)=1+x in R", or (1,1)›dehashes to (1,1).››For the length three sequence,›(1,0,1), a=1+x^2 with›q*a=1+x+x^2 mod(x^D), that is in›R"=Z_2[[x]]/(x^3) (here D=3) and our›length three sequence (101) is hashed›to (111)=1+x+x^2.››To dehash this, we multiply (1+x+x^2)›by p (mod (x^3)) so we only need to›take p=(1+x+x^2)) to get (mod x^3 in›Z_2, that is doing the calculations›mod 2 for the coefficients),›p*(1+x+x^2)=1+x^2 mod(x^3), or we›de-hash (1,1,1) to (1,0,1).››If we take R=Z_10 (mod 10, so we are›looking at sequences of base ten›digits) and want to hash a sequence›of at most L digits where L=8, then›we want power series p,q in Z_10[[x]]›with p*q=1 but, if we are willing to›limit ourselves to D<=L=8, we need›only find polynomials (not the full›power series) p,q with p*q=1 in›R"=Z_10[[x]]/(x^L), but:››(1+7x+3x^2+9x^3)*(1+3x+6x^2+5x^4+x^5+›8x^6+6x^7)=1+5x^8+4x^10=1 mod(x^8)››NOTE: As each of these polys. are›units in Z_10[[x]], the power series›ring, we can take either as q and for›any value of L find a power series›for the other with p*q=1 in›Z_10[[x]].››This is the hash coding that is used›in the VCR+ to convert a raw code to›a hashed code (in the C-source code I›have seen for the coding, this is the›algorithm used in the first two›subroutines... it is the value used›and is correct for sequences of at›least six digits, base ten, however I›do NOT know what the hash series is›for longer sequences than six›digits).››                -----››Such coding (treating a code as a›polynomial, using a hash series which›is invertible in the power series›ring, R[[x]], and doing the›calculations modulo x^D where›D=deg(a)+1, multiplying by the lowest›power of the polynomial that›preserves the degree mod x^D is what›I will call polynomial hashing of›sequences which hashes a sequence of›D-digits to another of the same›length and is invertible by finding›the inverse of the hash series (which›can be done mod x^D so we really›don't have to worry about power›series rings... in fact we can do all›the work in R[[x]]/(x^L) if we limit›ourselves to sequences of at most›L-digits).››For arbitrary length series we go to›the power series ring, R[[x]] and use›p and q (power series) with p*q=1 in›R[[x]] (as long as q(0) is a unit in›R, we can always find an inverse, and›can use this as hash coding›mod(x^(deg(a)+1))... of course, in›that case we only need the power›series modulo x^D, and if we have a›bound on D (say D<=L) only need work›mod x^L rather than with power›series.››I suppose that the VCR coding may›actually give a power series enabling›one to hash arbitrary length›sequences, but the values given above›for p,q are the ones used in the›C-source code for limited VCR+›coding/decoding which works for codes›of up to six digits (since we are›limited in the knowledge of the›time/duration codes to those of six›digits, the algorithm given in this›ARChive ONLY works for six digit›codes, and we can actually limit L to›six and use 1+7x+3x^2+9x^3 and›1+3x+6x^2+5x^4+x^5 which are inverses›in Z_10[[x]]/(x^6)... heck, if we are›only going to work with sequences of›six digits, why use any term of›degree higher than five in p or q?).››Let me call a function whose input is›a polynomial, and which uses a›parameter D (which HAPPENS to be one›more than the degree of the›polynomial) HA1 whose output is›q*a... if a is a polynomial input,›then the output polynomial is›HA1(a)=q*a mod[x^D] and HASH1 is our›hash algorithm which changes a to a›new polynomial (I will also store it›in a) given by:››HASH1:››LABEL:›   a:=HA1(a)›   if the D-1 coefficient of a is›zero, then goto LABEL›››Let me use HA1I(a) for the inverse›(using p rather than q as the›multiplier) and HASH1I for the›[I]inverse routine.›