Pairwise independent hash family interface

Fix x and a desired u. For each $a\in F$, the equation $ax+b=u$ has the unique solution $b=u-ax$ by additive cancellation. Hence exactly $\mathrm{\mid }F\mathrm{\mid }$ of $\mathrm{\mid }F{\mathrm{\mid }}^2$ seeds give u, proving marginal probability $1\mathrm{/}\mathrm{\mid }F\mathrm{\mid }$. In particular the seed with a=0 is necessary to this full family and is permitted. F is nonempty, indeed has at least two elements by F1.

For distinct x,y and prescribed u,v, subtraction gives $a(x-y)=u-v$. The nonzero $x-y$ has an inverse, so necessarily $a=(u-v)(x-y{)}^{-1}$ and $b=u-ax$. These values work: $ay+b=u-a(x-y)=v$. They are unique by multiplication by the inverse and additive cancellation; uniqueness of an inverse itself follows from $c=c((x-y)d)=(c(x-y))d=d$ when c,d are both inverses. Exactly one seed therefore realizes each ordered output pair, with probability $1\mathrm{/}\mathrm{\mid }F{\mathrm{\mid }}^2$, equal to the product of the marginals from step 1.1. This proves pairwise independence. Equal x,y are intentionally excluded: their values cannot be independently prescribed.