HASH3››      Another sequential mixing›      -------------------------››Given a ring, R (finite, communative›with identity) and a polynomial›P(x)=P(n)x^n+...+P(0) (with P(0)<>0)›and an integer D and a DAY (<>0)›value and a YEAR value... consider›the function that creates a new›polynomial, HA3(P) given by (all this›being done in R[[x]]):››HA3(P)=P*(1-x)^(-(YEAR+1)) + DAY[(1-x›)^(-(YEAR+1))-1]/x mod[x^D]››(as this is just polynomial›multiplication, once we write down›the coefficients of›(1-x)^(-(YEAR+1)), we just use the›routine to multiply power series in›R[[x]] as we have in the routines for›HASH1... the coefficients in the›multiplier of DAY are just those of›the multiplier of P shifted one›place... note that as this is done in›R[[x]], if we add 5x^2+3x+2 to›7x^2+7x+4 and R=Z_10, the sum is›2x^2+6 as we do everything in›Z_10[[x]] and add our coefficients›MODULO TEN)››(this depends on P, D, DAY and YEAR)››(the OUTPUT (HA3(P)) IS A›POLYNOMIAL!)››Note that›HA3(P)(0)=P(0)+DAY*C(YEAR+1,1)››(note that the coefficient of DAY IS›a power series with constant term›C(YEAR+1,1) where›C(n,m)=n!/m!/(n-m)!, the binomial›coefficient in R)››Consider the hash programme:››HASH3››H(x) = HA3(P)(x)››IF H(0)=0 then H=HA3(H)››(H is HASH3(P,DAY,YEAR) and depends›on D)››(NOTE that IF HA3(P)(0)=0 then›P(0)+DAY*C(YEAR+1,1)=0, in that case,›HA3(HA3(P))(0)=HA3(P)(0)+DAY*C(YEAR+1›,1)=DAY*C(YEAR+1,1)=-P(0) which is›NON-ZERO)››(NOTE that in HA3, D is a constant›independent of which iteration we are›using)››The output H is the HASH3 of P, YEAR›and DAY (H=HASH3(P,DAY,YEAR))›(NOTE: if D=0, all the modulo [x^D]›yields a result of zero for H, thus›if D=0, then H:=0).››Given the HASH3, H, we can take the›new function which uses D (which must›be obtained otherwise), DAY and YEAR›as:››HA3I(H)=[H-DAY[(1-x)^(-(YEAR+1))-1)/x›](1-x)^(YEAR+1) mod[x^D]››and››P=HA3I(H): IF P(0)=0 then P=HA3I(P)››This inverts the HASH3 function›above.››            ------------››Besides H we need OFF which is›calculated as follows... NOTE THESE›following calculations are integer›calculations, NOT in R=Z_10! That is,›in doing the calculations in HASH3,›x+9x=0 (in Z_10[[x]], where I am›using R[x] for the polynomial ring›over R and R[[x]] for the power›series ring), but IN THESE FOLLOWING›CALCULATIONS 1+9=10... THIS IS NOT A›POLYNOMIAL CALCULATION! IT IS NOT IN›Z_10 BUT AS INTEGERS:››First, OFF=the sum of the›coefficients of P... if P==0, then›OFF=0 and we are done!››Next, with N=D-1, we add to OFF the›Sum of the Nth coefficients of›HA3(P,DAY,J) for J=0 to YEAR.››We set H1=HA3(P,DAY,YEAR) and if›H1(0)<>0 we have H=H1, but if H1(0)=0›we have H=HA3(H1) (the HASH3) (and›remember, D remains the same) and in›this case we add to OFF the Sum of›the Nth coefficients of HA3(H1,DAY,J)›for J=0 to YEAR as well.›