Editing Hash function (section)

=== Algebraic coding ===
Algebraic coding is a variant of the division method of hashing which uses division by a polynomial modulo 2 instead of an integer to map {{Mvar|n}} bits to {{Mvar|m}} bits.<ref name="knuth-1973" />{{rp|pages=512–513}} In this approach, {{Math|1=''M'' = 2<sup>''m''</sup>}}, and we postulate an {{Mvar|m}}th-degree polynomial {{Math|1=''Z''(''x'') = ''x''<sup>''m''</sup> + &zeta;<sub>''m''&minus;1</sub>''x''<sup>''m''&minus;1</sup> + &ctdot; + &zeta;<sub>0</sub>}}.  A key {{Math|1=''K'' = (''k''<sub>''n''&minus;1</sub>&mldr;''k''<sub>1</sub>''k''<sub>0</sub>)<sub>2</sub>}} can be regarded as the polynomial {{Math|1=''K''(''x'') = ''k''<sub>''n''&minus;1</sub>''x''<sup>''n''&minus;1</sup> + &ctdot; + ''k''<sub>1</sub>''x'' + ''k''<sub>0</sub>}}. The remainder using polynomial arithmetic modulo 2 is {{Math|1=''K''(''x'') mod ''Z''(''x'') = ''h''<sub>''m''&minus;1</sub>''x''<sup>''m''&minus;1</sup> + &ctdot; ''h''<sub>1</sub>''x'' + ''h''<sub>0</sub>}}. Then {{Math|1=''h''(''K'') = (''h''<sub>''m''&minus;1</sub>&mldr;''h''<sub>1</sub>''h''<sub>0</sub>)<sub>2</sub>}}. If {{Math|''Z''(''x'')}} is constructed to have {{Mvar|t}} or fewer non-zero coefficients, then keys which share fewer than {{Mvar|t}} bits are guaranteed to not collide.

{{Mvar|Z}} is a function of {{Mvar|k}}, {{Mvar|t}}, and {{Mvar|n}} (the last of which is a divisor of {{Math|2<sup>''k''</sup> &minus; 1}}) and is constructed from the [[finite field]] {{Math|GF(2<sup>''k''</sup>)}}.  [[Donald Knuth|Knuth]] gives an example: taking {{Math|1=(''n'',''m'',''t'') = (15,10,7)}} yields {{Math|1=''Z''(''x'') = ''x''<sup>10</sup> + ''x''<sup>8</sup> + ''x''<sup>5</sup> + ''x''<sup>4</sup> + ''x''<sup>2</sup> + ''x'' + 1}}. The derivation is as follows:

Let {{Mvar|S}} be the smallest set of integers such that {{Math|{{mset|1,2,&mldr;,''t''}} &SubsetEqual; ''S''}} and {{Math|(2''j'' mod ''n'') &in; ''S'' &forall;''j'' &in; ''S''}}.<ref group="Notes">For example, for n=15, k=4, t=6, <math>S=\{1,2,3,4,5,6,8,10,12,9\}</math> [Knuth]</ref>

Define <math>P(x)=\prod_{j\in S}(x-\alpha^j)</math> where {{Math|&alpha; &in;<sup>''n''</sup> GF(2<sup>''k''</sup>)}} and where the coefficients of {{Math|''P''(''x'')}} are computed in this field.  Then the degree of {{Math|1=''P''(''x'') = {{abs|''S''}}}}. Since {{Math|&alpha;<sup>2''j''</sup>}} is a root of {{Math|''P''(''x'')}} whenever {{Math|&alpha;<sup>''j''</sup>}} is a root, it follows that the coefficients {{Math|''p<sup>i</sup>''}} of {{Math|''P''(''x'')}} satisfy {{Mvar|1=''p''{{su|p=2|b=''i''}} = ''p''<sub>i</sub>}}, so they are all 0 or 1. If {{Math|1=''R''(''x'') = ''r''<sub>''n''&minus;1</sub>''x''<sup>''n''&minus;1</sup> + &ctdot; + ''r''<sub>1</sub>''x'' + ''r''<sub>0</sub>}} is any nonzero polynomial modulo 2 with at most {{Mvar|t}} nonzero coefficients, then {{Math|''R''(''x'')}} is not a multiple of {{Math|''P''(''x'')}} modulo 2.<ref group=Notes>Knuth conveniently leaves the proof of this to the reader.</ref>  If follows that the corresponding hash function will map keys with fewer than {{Mvar|t}} bits in common to unique indices.<ref name="knuth-1973" />{{rp|pages=542–543}}

The usual outcome is that either {{Mvar|n}} will get large, or {{Mvar|t}} will get large, or both, for the scheme to be computationally feasible.  Therefore, it is more suited to hardware or microcode implementation.<ref name="knuth-1973" />{{rp|pages=542–543}}