11institutetext: Brno University of Technology, Czech Republic
11email: {hrdina<EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext: Technische Universität Darmstadt, Darmstadt, 64297, Germany
22email<EMAIL_ADDRESS>33institutetext: Federal University of
ABC, Sao Bernardo, Brazil 33email<EMAIL_ADDRESS>44institutetext:
:em engineering methods AG, Darmstadt, Germany 44email:
<EMAIL_ADDRESS>55institutetext: University of Campinas,
Campinas, Brazil 55email<EMAIL_ADDRESS>
# Quantum Register Algebra: the mathematical language for quantum
computing††thanks: Supported by FAPESP and CNPq.

Hrdina  J 11 0000-0003-2460-7571 Hildenbrand D 22 0000-0002-6384-4345
Návrat A 11 0000-0002-8100-4032 Steinmetz C 44 -
Alves R 33 0000-0002-3171-9339 Lavor C 44 0000-0002-8105-3627
Vašík P 11 0000-0001-6725-7378 Eryganov I 11 0000-0003-2203-882X

###### Abstract

We introduce Quantum Register Algebra (QRA) as an efficient tool for quantum
computing. We show the direct link between QRA and Dirac formalism. We present
GAALOP (Geometric Algebra Algorithms Optimizer) implementation of our
approach. Using the QRA basis vectors definitions given in Section 4 and the
framework based on the de Witt basis presented in Section 5, we are able to
fully describe and compute with QRA in GAALOP using the geometric product. We
illustrate the intuitiveness of this computation by presenting the QRA form
for the well known SWAP operation on a two qubit register.

###### Keywords:

quantum computing geometric algebra quantum register algebra

##  1 Introduction

Geometric Algebra proved in recent years that it is a mathematical system
covering many other mathematical systems as conventionally used in engineering
and physical science, [4, 5, 6, 9]. Examples are linear algebra, quaternions,
Dirac and Pauli matrices, Plucker coordinates to mention only a few. This
means, the big advantage of Geometric Algebra is that you do not have to learn
different mathematical systems in order to handle various application areas.
You simply have to learn only one mathematical system to handle them. Another
simplification based on Geometric Algebra is that both objects and operations
are handled in one algebra, means you do not have to distinguish, for
instance, between points or vectors as objects and matrices for the
description of operations on them.

Now, the question is: can Geometric Algebra also advantageously be used for
quantum computing? Quantum computing, currently, is based on working with
complex numbers, matrices of complex numbers and tensor computing in order to
handle operations with arbitrary numbers of qubits.

Some papers on geometric algebras and quantum computing demonstrate
application of geometric algebras $\mathbb{G}_{4,1}$ (relativistic case) and
$\mathbb{G}_{3,0}$ (nonrealtivistic case), [3], geometric algebra
$\mathbb{G}_{n,n}$, [1] and finally a complex Clifford algebra
$\mathbb{C}_{n}$,[2].

In this paper, we show that quantum computing can simply be based on a
Geometric Algebra called QRA (quantum register algebra). In Sect. 2, we show
that complex numbers can easily be identified within Geometric Algebra.

The Dirac formalism is a very useful formalism to describe quantum computing.
Although it is originally based on complex matrices (see Sect. 3), we show in
our definition of QRA according to Sect. 4 and Sect. 5, that it can still be
used with QRA.

In order to compute with QRA, we use GAALOP, a stand alone geometric algebra
algorithm optimizer [Ref for GAALOP]. We extended the GAALOP tool presented in
[1] for the QRA support based on the definitions presented in Sections 4 and
5. The full implementation is shown in Sect. 6. In order to simplify the
computing as much as possible, we also integrated it in our online tool
GAALOPWeb. In Sect. 7, we present how easy it is to compute with QRA using
GAALOP, for this we present the QRA form for the SWAP gate. The big advantage
for quantum computing beginners is that they only have to know Geometric
Algebra in order to describe the objects and operations of quantum computing.

##  2 From complex numbers to geometric algebras and back again

The algebra of complex numbers $\mathbb{C}$ is an essential tool for quantum
computing. Qubits are realised by vectors in complex vector space
$\mathbb{C}^{n}$ and the gates by matrices $n\times n$ over the complex
numbers. In our approach, the complex linear algebra is the language for
quantum computing. More precisely, we are using the natural concept of complex
geometric algebras with the complex numbers as one of their instances. In the
sequel, we investigate these concepts in a more detailed way.

Formally, geometric algebra $\mathbb{G}_{p,q}$ is a free, associative,
distributive and unitary algebra over the set of abstract elements
$\\{e_{1},\dots,e_{n}\\}$ endowed with the following identities:

$\displaystyle e_{i}e_{j}$ $\displaystyle=-e_{j}e_{i}\text{, where }i\neq j,$
$\displaystyle e_{i}^{2}$ $\displaystyle=1\text{, where }i=1,\dots,p,$ (1)
$\displaystyle e_{i}^{2}$ $\displaystyle=-1\text{, where }i=p+1,\dots,n.$

In computer science notation, we understand $\mathbb{G}_{p,q}$ as a vector
space where vectors are built as words over the alphabet
$\\{e_{1},\dots,e_{n}\\}$, including an empty word, using the following
equivalency. Two words are equivalent (they are different representations of
the same object) if the first can be rewritten into the second and vice versa
with the help of identities (2), distributivity and associativity.

For example, let us consider geometric algebra $\mathbb{G}_{1,1}$, so we have
words over the alphabet $\\{e_{1},e_{2}\\}$ and identities $e_{1}^{2}=1,\
e_{2}^{2}=-1$ together with anti–commutativity $e_{1}e_{2}=-e_{2}e_{1}$. Then
the vector space basis is of the form

$\displaystyle\\{1,e_{1},e_{2},e_{1}e_{2}\\}.$ (2)

Hence, for example the word $e_{2}e_{1}e_{2}e_{1}e_{1}e_{2}e_{2}$ can by
rewritten to $-e_{1}$ with the help of identities (2) in the following way:

$\displaystyle
e_{2}e_{1}e_{2}e_{1}e_{1}e_{2}e_{2}=e_{2}e_{1}e_{2}(1)(-1)=e_{1}e_{2}e_{2}=e_{1}(-1)=-e_{1}.$

The element $e_{1}$ is in the basis (2). We can see that the elements of
geometric algebra $\mathbb{G}_{1,1}$ are the linear combinations over the
basis (2), i.e.

$\displaystyle\mathbb{G}_{1,1}=\\{x_{1}+x_{2}e_{1}+x_{3}e_{2}+x_{4}e_{1}e_{2}|x_{i}\in\mathbb{R}\\}$
(3)

together with multiplication given by identities (2). For example

$\displaystyle(e_{1}+2e_{1}e_{2})(1+e_{1}-3e_{2})$
$\displaystyle=e_{1}(1+e_{1}-3e_{2})+2e_{1}e_{2}(1+e_{1}-3e_{2})$
$\displaystyle=e_{1}+e_{1}e_{1}-e_{1}3e_{2}+2e_{1}e_{2}+2e_{1}e_{2}e_{1}-2e_{1}e_{2}3e_{2}$
$\displaystyle=e_{1}+(1)-3e_{1}e_{2}+2e_{1}e_{2}-2e_{2}e_{1}e_{1}-6e_{1}(-1)$
$\displaystyle=1+e_{1}-e_{1}e_{2}-2e_{2}(1)+6e_{1}$
$\displaystyle=1+7e_{1}-2e_{2}-e_{1}e_{2}\in\mathbb{G}_{1,1}.$

In any geometric algebra $\mathbb{G}(p,q)$ such that $p>1$ or $q>1$ we can
find a subalgebra isomorphically equivalent to $\mathbb{C}$ in the following
way: if $p>1$ we have two elements $e,f\in\mathbb{G}(p,q)$ such that
$e^{2}=f^{2}=1$ and $ef=-fe$, so

$(ef)^{2}=efef=-eeff=-e^{2}f^{2}=-1$

and

$\mathbb{C}\cong\bar{\mathbb{C}}=\\{a+b(ef)|a,b\in\mathbb{R}\\}\subset\mathbb{G}(p,q).$

In the same way, if we have $q>1$ then we have two elements $e,f$ such that
$e^{2}=f^{2}=-1$ and $ef=-fe$, so

$(ef)^{2}=efef=-eeff=-e^{2}f^{2}=-1(-1)(-1)=-1.$

Note that the element $ef$ commutes with the other basis elements in both
cases.

###### Remark 1

The complex numbers $\mathbb{C}$ are in fact isomorphically equivalent
geometric algebra $\mathbb{G}_{0,1}$. Indeed, $\mathbb{G}_{0,1}$ is a space

$\displaystyle\mathbb{G}_{0,1}=\\{x_{1}+x_{2}e_{1}|x_{i}\in\mathbb{R}\\}$ (4)

such that $e_{1}^{2}=-1$ which is the vector space isomorphically equivalent
to $\mathbb{C}$. The specific concept for the imaginary unit used in QRA is
described in Sect. 4.

##  3 Matrices vs. Dirac formalism

In this section, we show the direct link between Dirac formalism and geometric
algebras. Original quantum mechanics is based on Dirac formalism, but quantum
computing can be built up of matrices because the Hilbert space of qubits’
states is finite. We briefly recall the link between matrices and Dirac
formalism, [10].

  * •

the $n$-qubit (ket)

$\displaystyle|i\rangle=|a_{1}\cdots a_{n-1}a_{n}\rangle,\text{ where
}a_{i}\in\\{0,1\\}\text{ and }i=a_{1}2^{n-1}+\cdots+a_{n}2^{0}$
$\displaystyle\Longleftrightarrow\begin{pmatrix}0\\\ \vdots\\\ 1\\\ \vdots\\\
0\end{pmatrix},\text{ where }1\text{ is on {i+1} position, 0 otherwise}.$

  * •

the dual $n$-qubit (bra)

$\displaystyle\langle i|=\langle a_{1}\cdots a_{n-1}a_{n}|,\text{ where
}a_{i}\in\\{0,1\\}\text{ and }i=a_{1}2^{n-1}+\cdots+a_{n}2^{0}$
$\displaystyle\Longleftrightarrow\begin{pmatrix}0&\cdots&1&\cdots
0\end{pmatrix},\text{ where }1\text{ is on {i+1} position, 0 otherwise}.$

The $n$-qubit gates are matrices $A=(a_{ij})$, where $i,j=1,\dots,2^{n}$. So
if a matrix $A$ acts on coordinates in canonical basis, then its element
$a_{ij}$ sends the $j$–th element of canonical basis to $i$–th element of
canonical basis in the same way as Dirac expression $|i-1\rangle\langle j-1|$,
so

$\begin{pmatrix}a_{11}&\dots&a_{1n}\\\ \vdots&&\vdots\\\
a_{n1}&\dots&a_{nn}\end{pmatrix}\Longleftrightarrow\sum_{i,j=1}^{n}a_{ij}|i-1\rangle\langle
j-1|.$

For example, the representations of 1-qubits (ket and bra) are

$|0\rangle\Longleftrightarrow\begin{pmatrix}1\\\
0\end{pmatrix},|1\rangle\Longleftrightarrow\begin{pmatrix}0\\\
1\end{pmatrix},\langle
0|\Longleftrightarrow\begin{pmatrix}1&0\end{pmatrix},\langle
1|\Longleftrightarrow\begin{pmatrix}0&1\end{pmatrix}$

and the NOT gate is of the form

$\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}\Longleftrightarrow|0\rangle\langle
1|+|1\rangle\langle 0|.$

##  4  Definition of QRA

Recall that a Geometric Algebra $\mathbb{G}_{n}=\mathbb{G}_{n,0}$ is a free,
associative, unitary algebra over the set of anti–commuting generators
$\\{e_{1},\dots,e_{n}\\}$ such that $e_{i}^{2}=1,i\in\\{1,\dots,n\\}.$ Now we
finally define the Quantum Register Algebra (QRA). First, let us consider a
geometric algebra $\mathbb{G}_{n+2}$ with its basis elements
$\\{e_{1},\dots,e_{n},r_{1},r_{2}\\}$ together with the following identities

$\displaystyle e_{1}^{2}$
$\displaystyle=e_{2}^{2}=\cdots=e_{n}^{2}=r_{1}^{2}=r_{2}^{2}=1.$ (5)

Then we define a bivector

$\iota=r_{1}r_{2}$

and show that the set $\tilde{\mathbb{C}}=\\{a+b\iota|a,b\in\mathbb{R}\\}$ is
isomorphic to an algebra $\mathbb{C}$, so $\iota$ plays the role of a complex
unit. The set $\tilde{\mathbb{C}}$ is closed with respect to addition and
multiplication. The element $\iota$ is in square equal to $-1$. Indeed,

$\iota^{2}=r_{1}r_{2}r_{1}r_{2}=-r_{1}^{2}r_{2}^{2}=-1,$

so $\tilde{\mathbb{C}}\cong\mathbb{C}$. Now we define QRA as a geometric
subalgebra $\mathbb{G}_{n}$ with the coefficients in $\tilde{\mathbb{C}}$,
i.e.

$\mathrm{QRA}=\\{a_{0}g_{0}+\cdots+a_{n}g_{n}|a_{i}\in\tilde{\mathbb{C}},g_{i}\in\mathbb{G}_{n}\\}\subset\mathbb{G}_{n+2}.$

Hence for any element $A\in\mathbb{G}_{n}$ we have $\iota A=A\iota$ because
$\iota$ is a bivector and $\iota\notin\mathbb{G}_{n}.$

##  5  QC in the QRA framework

To use QRA to model quantum computing we choose a different basis of QRA based
on geometric algebra $\mathbb{G}_{2n}$. This basis is called Witt basis and it
is formed by elements
$\\{f_{1},f_{1}^{\dagger},\dots,f_{n},f_{n}^{\dagger}\\}$ satisfying

$\displaystyle f_{i}$ $\displaystyle=\frac{1}{2}(e_{i}+\iota e_{i+n}),$ (6)
$\displaystyle f_{i}^{\dagger}$ $\displaystyle=\frac{1}{2}(e_{i}-\iota
e_{i+n}),$ (7)

where $\iota=r_{1}r_{2}$. Now, we define an element
$I=f_{1}f_{1}^{\dagger}\cdots f_{n}f_{n}^{\dagger}$ satisfying

$\displaystyle I^{2}$ $\displaystyle=I,$ (8) $\displaystyle f_{i}I$
$\displaystyle=0,$ (9) $\displaystyle f_{i}f_{i}^{\dagger}I$ $\displaystyle=I$
(10)

then we have a straightforward identification of bra and ket vectors with the
elements of QRA as follows:

$\displaystyle\langle a_{1}\dots a_{n}|\hookrightarrow
I(f_{n})^{a_{n}}\dots(f_{1})^{a_{1}},\text{ where }a_{i}\in\\{0,1\\},$ (11)
$\displaystyle|a_{1}\dots
a_{n}\rangle\hookrightarrow(f_{1}^{\dagger})^{a_{1}}\dots(f_{n}^{\dagger})^{a_{n}}I,\text{
where }a_{i}\in\\{0,1\\}.$ (12)

For example, let us consider the space of 2–qubit states. Then the
identification (11) and (12) for the ket vectors reads

$\displaystyle\begin{split}|00\rangle&\mapsto(f_{1}^{\dagger})^{0}(f_{2}^{\dagger})^{0}I=I,\\\
|01\rangle&\mapsto(f_{1}^{\dagger})^{0}(f_{2}^{\dagger})^{1}I=f_{2}^{\dagger}I,\\\
|10\rangle&\mapsto(f_{1}^{\dagger})^{1}(f_{2}^{\dagger})^{0}I=f_{1}^{\dagger}I,\\\
|11\rangle&\mapsto(f_{1}^{\dagger})^{1}(f_{2}^{\dagger})^{1}I=f_{1}^{\dagger}f_{2}^{\dagger}I.\end{split}$
(13)

So the ket vectors in 2-qubit state space are linear combinations of the basis
$\\{f_{1},f_{1}^{\dagger},\dots,f_{n},f_{n}^{\dagger}\\}$ elements:

$|\psi\rangle=(\psi_{00}+\psi_{01}f_{2}^{\dagger}+\psi_{10}f_{1}^{\dagger}+\psi_{11}f_{1}^{\dagger}f_{2}^{\dagger})I.$
(14)

To define the quantum gates we have to identify the bra vectors in the similar
way:

$\displaystyle\begin{split}\langle 00|&\mapsto I(f_{2})^{0}(f_{1})^{0}=I,\\\
\langle 01|&\mapsto I(f_{2})^{1}(f_{1})^{0}=If_{2},\\\ \langle 10|&\mapsto
I(f_{2})^{0}(f_{1})^{1}=If_{1},\\\ \langle 11|&\mapsto
I(f_{2})^{1}(f_{1})^{1}=-If_{1}f_{2}.\end{split}$ (15)

Thus the bra vectors in 2-qubit state space are combinations of the basis
$\\{f_{1},f_{1}^{\dagger},\dots,f_{n},f_{n}^{\dagger}\\}$ elements as follows:

$\langle\psi|=I(\psi_{00}+\psi_{10}f_{1}+\psi_{01}f_{2}-\psi_{11}f_{1}f_{2}).$

To demonstrate our approach we show the design of the SWAP gate [8]. Recall
that in Dirac notation, the SWAP gate is represented by

$|00\rangle\langle 00|+|01\rangle\langle 10|+|10\rangle\langle
01|+|11\rangle\langle 11|.$

Using the identification (13) and (15), the SWAP gate may be rewritten as:

SWAP $\displaystyle=|00\rangle\langle 00|+|01\rangle\langle
10|+|10\rangle\langle 01|+|11\rangle\langle 11|$
$\displaystyle=f_{1}f_{1}^{\dagger}f_{2}f_{2}^{\dagger}+f_{1}^{\dagger}f_{2}-f_{1}f_{2}^{\dagger}+f_{1}^{\dagger}f_{1}f_{2}^{\dagger}f_{2}.$
(16)

Before we present how the gate acts on 2-qubits, let us mention the rules for
calculations with the Witt basis $\\{f_{i},f_{i}^{\dagger}\\}$ elements in the
form of a list of properties which can be verified by straightforward
computations:

$\displaystyle(f_{i})^{2}$ $\displaystyle=(f_{i}^{\dagger})^{2}=0$ (17)
$\displaystyle f_{i}f_{j}$ $\displaystyle=-f_{j}f_{i},\quad
f_{i}^{\dagger}f_{j}^{\dagger}=-f_{j}^{\dagger}f_{i}^{\dagger}$ (18)
$\displaystyle f_{i}f_{i}^{\dagger}f_{i}$ $\displaystyle=f_{i},\qquad
f_{i}^{\dagger}f_{i}f_{i}^{\dagger}=f_{i}^{\dagger}$ (19)

We present the SWAP gate functionality on 2-qubits step by step. Thus we can
calculate:

$\displaystyle\text{SWAP}|\boldsymbol{\psi}\rangle=$
$\displaystyle=(f_{1}f_{1}^{\dagger}f_{2}f_{2}^{\dagger}+f_{1}^{\dagger}f_{2}-f_{1}f_{2}^{\dagger}+f_{1}^{\dagger}f_{1}f_{2}^{\dagger}f_{2})(\psi_{00}+\psi_{01}f_{2}^{\dagger}+\psi_{10}f_{1}^{\dagger}+\psi_{11}f_{1}^{\dagger}f_{2}^{\dagger})I$
$\displaystyle=f_{1}f_{1}^{\dagger}f_{2}f_{2}^{\dagger}(\psi_{00}+\cancel{\psi_{01}f_{2}^{\dagger}}+\cancel{\psi_{10}f_{1}^{\dagger}}+\cancel{\psi_{11}f_{1}^{\dagger}f_{2}^{\dagger}})I\text{
by \eqref{p1}}$
$\displaystyle\phantom{=}+f_{1}^{\dagger}f_{2}(\cancel{\psi_{00}}+\psi_{01}f_{2}^{\dagger}+\cancel{\psi_{10}f_{1}^{\dagger}}+\cancel{\psi_{11}f_{1}^{\dagger}f_{2}^{\dagger}})I\text{
by \eqref{r1} and \eqref{p1}}$
$\displaystyle\phantom{=}-f_{1}f_{2}^{\dagger}(\cancel{\psi_{00}}+\cancel{\psi_{01}f_{2}^{\dagger}}+\psi_{10}f_{1}^{\dagger}+\cancel{\psi_{11}f_{1}^{\dagger}f_{2}^{\dagger}})I\text{
by \eqref{r1} and \eqref{p1}}$
$\displaystyle\phantom{=}+f_{1}^{\dagger}f_{1}f_{2}^{\dagger}f_{2}(\cancel{\psi_{00}}+\cancel{\psi_{01}f_{2}^{\dagger}}+\cancel{\psi_{10}f_{1}^{\dagger}}+\psi_{11}f_{1}^{\dagger}f_{2}^{\dagger})I\text{
by \eqref{r1} and \eqref{p1}}$
$\displaystyle=\underline{(f_{1}f_{1}^{\dagger}f_{2}f_{2}^{\dagger})}(\psi_{00})I+(f_{1}^{\dagger}\underline{f_{2}})(\psi_{01}\underline{f_{2}^{\dagger}})I\text{
by \eqref{r2}}$
$\displaystyle\phantom{=}+f_{2}^{\dagger}\underline{f_{1}}\psi_{10}\underline{f_{1}}^{\dagger}I+(f_{1}^{\dagger}f_{1}f_{2}^{\dagger}f_{2})(\psi_{11}f_{1}^{\dagger}f_{2}^{\dagger})I$
$\displaystyle=(\psi_{00}+\psi_{01}f_{1}^{\dagger}+\psi_{10}f_{2}^{\dagger}+\psi_{11}(f_{1}^{\dagger}f_{1}f_{1}^{\dagger})(f_{2}^{\dagger}f_{2}f_{2}^{\dagger}))I\text{
the last step by \eqref{r2}}$
$\displaystyle=(\psi_{00}+\psi_{01}f_{1}^{\dagger}+\psi_{10}f_{2}^{\dagger}+\psi_{11}f_{1}^{\dagger}f_{2}^{\dagger})I,$

where $\cancel{g}$ and $\underline{g}$ stand for $g=0$ and $g=1$. Finally, by
means of (13), the final 2-qubit can be rewritten in Dirac notation as

$(\psi_{00}|00\rangle+\psi_{01}|10\rangle+\psi_{10}|01\rangle+\psi_{11}|11\rangle)I$

which is the expected result.

The other gates may be interpreted in the very same way and thus we showed how
quantum computation in QRA is realized. We used the Witt basis axioms
(17)–(19) together with additional axioms (9) and (10). The use of the
additional axioms may seem redundant and complicated but they only simplify
the written form of calculations and thus the functionality is easier for
demonstration. Indeed, these rules may be avoided completely for which we
point out the following two reasons:

  * •

If we interpret the element $I$ as $f_{1}f_{1}^{\dagger}\cdots
f_{n}f_{n}^{\dagger}$, the rules (9) and (10) do not apply because they are
simple consequences of (17)–(19). Only the expressions will be longer.

  * •

We are using the axioms (17)–(19) for calculations in the Witt basis which
naturally corresponds to Dirac formalism. But Witt basis is just a different
set of generators for QRA elements. Thus the axioms (17)–(19) are derived from
geometric algebra axioms (5) which are very simple.

Our approach is based on the fact that QRA and the Witt basis provide nice
language for written QC schemes. The expressions are very similar to Dirac
formalism, so they are very simple to understand for people not familiar with
geometric algebra. But unlike abstract Dirac formalism, our objects are
elements of QRA which is a geometric algebra based on very simple axioms and,
furthermore, it is very easy for implementation as shown in the following
section.

##  6  GAALOP implementation

The integration of QRA into GAALOP is done based on the file Definition.csv
according to Chapt. 9 of [7]. Listing 1 shows the file for the definition of
one qubit.

Listing 1: Definition.csv for QRA for one qubit

⬇

11,e1,e2,er1,er2

2

31,e1,e2,er1,er2

4e1=1,e2=1,er1=1,er2=1

In general, this file consists of 5 lines for the definition of the algebra.
In the case of QRA, the lines 2 and 5 are left blank since the used basis in
Line 1 and the standard basis in Line 3 are the same and no transformations
between the two bases are needed. The basis is defined by the basis vectors
e1, e2, er1 and er2 according to $e_{1},e_{2},r_{1},r_{2}$ as defined in the
previous sections. All their squares are defined to 1 according to line 4.

For each additional qubit we need two additional basis vectors, while er1 and
er2 are always the same. The definition of a register with two qubits is shown
in Listing 2.

Listing 2: Definition.csv for QRA based on two qubits

⬇

11,e1,e2,e3,e4,er1,er2

2

31,e1,e2,e3,e4,er1,er2

4e1=1,e2=1,e3=1,e4=1,er1=1,er2=1

For the second qubit we need the additional basis vectors e3 and e4. For this
paper, we also made a new version of
GAALOPWeb111http://www.gaalop.de/gaalopweb/. It allows online computations
with a number of n qubits without the installation of a specific software.

##  7 Example in GAALOP

As an example we implemented the SWAP gate on GAALOP for a register with two
qubits. Following the Equations (6) and (7), the vectors $f_{i}$ and
$f_{i}^{+}$ as

$\displaystyle f_{1}=\frac{1}{2}(e_{1}+\iota e_{3}),\quad
f_{1}^{\dagger}=\frac{1}{2}(e_{1}-\iota e_{3})$ $\displaystyle
f_{2}=\frac{1}{2}(e_{2}+\iota e_{4}),\quad
f_{2}^{\dagger}=\frac{1}{2}(e_{2}+\iota e_{4})$ ,

where $\iota=r_{1}r_{2}$. Then, we use the definitions in (13) to implement
the basis elements, Equation (14) for $|\psi\rangle$ and (16) to define the
operator of the SWAP gate. We apply the SWAP operator on the element
$|\psi\rangle$. But first, let us see the coordinates of each ket vector basis
when they are multiplied by $I$ separately:

Listing 3: SWAP gate in QRA for two qubits.

⬇

1// Imaginary unit

2i = er1*er2;

3// Witt basis

4f1 = 0.5*(e1+i*e3);

5f1T = 0.5*(e1-i*e3);

6f2 = 0.5*(e2+i*e4);

7f2T = 0.5*(e2-i*e4);

8// Element "I"

9Id = f1*f1T*f2*f2T;

10// ket basis vectors multiplied by "Id"

11?ket00 = 1*Id;

12?ket01 = f2T*Id;

13?ket10 = f1T*Id;

14?ket11 = f1T*f2T*Id;

This is important to show which coordinates correspond to each vector in order
to see the amplitudes interchanging when SWAP is applied to some linear
combination of these vectors. The output for this code is shown bellow:

Listing 4: Basic elements multiplied by $I$.

⬇

1ket00[0] = 0.25; // 1.0

2ket00[42] = 0.25; // e1 ^ (e2 ^ (e3 ^ e4))

3ket00[50] = -0.25; // e1 ^ (e3 ^ (er1 ^ er2))

4ket00[55] = -0.25; // e2 ^ (e4 ^ (er1 ^ er2))

5ket01[2] = 0.25; // e2

6ket01[26] = -0.25; // e1 ^ (e3 ^ e4)

7ket01[41] = -0.25; // e4 ^ (er1 ^ er2)

8ket01[59] = 0.25; // e1 ^ (e2 ^ (e3 ^ (er1 ^ er2)))

9ket10[1] = 0.25; // e1

10ket10[32] = 0.25; // e2 ^ (e3 ^ e4)

11ket10[40] = -0.25; // e3 ^ (er1 ^ er2)

12ket10[60] = -0.25; // e1 ^ (e2 ^ (e4 ^ (er1 ^ er2)))

13ket11[7] = 0.25; // e1 ^ e2

14ket11[16] = -0.25; // e3 ^ e4

15ket11[51] = -0.25; // e1 ^ (e4 ^ (er1 ^ er2))

16ket11[54] = 0.25; // e2 ^ (e3 ^ (er1 ^ er2))

We remark that all identities given in (17)-(10) can be observed in GAALOP.
Now, let us choose a vector $|\psi\rangle$ 222The vector $|\psi\rangle$ is not
normalized, so the final result should be divided by $\sqrt{29}$.given by:

$\displaystyle|\psi\rangle$ $\displaystyle=$
$\displaystyle(|00\rangle+2|01\rangle+3|10\rangle+4|11\rangle)I$
$\displaystyle=$
$\displaystyle(1+3f_{2}^{\dagger}+3f_{1}^{\dagger}+4f_{1}^{\dagger}f_{2}^{\dagger})I,$

and apply the SWAP gate on it. The expected result is given by:

$\displaystyle|\bar{\psi}\rangle$ $\displaystyle=$
$\displaystyle(1+3f_{2}^{\dagger}+2f_{1}^{\dagger}+4f_{1}^{\dagger}f_{2}^{\dagger})I$
$\displaystyle=$
$\displaystyle(|00\rangle+3|01\rangle+2|10\rangle+4|11\rangle)I.$

We add 3 lines to the code in 3:

Listing 5: Definition and application of the SWAP gate on GAALOP.

⬇

1//SWAP

2SWAP=(f1*f1T*f2*f2T)+(f1T*f2)-(f1*f2T)+(f1T*f1*f2T*f2);

3?psi = ket00 + 2*ket01 + 3*ket10 + 4*ket11;

4?SwapPsi = SWAP*psi;

The output is shown below and then we analyze the result.

Listing 6: Output of the application of the SWAP gate on GAALOP.

⬇

1psi[0] = 0.25; // 1.0

2psi[1] = 0.75; // e1

3psi[2] = 0.5; // e2

4psi[7] = 1.0; // e1 ^ e2

5psi[16] = -1.0; // e3 ^ e4

6psi[26] = -0.5; // e1 ^ (e3 ^ e4)

7psi[32] = 0.75; // e2 ^ (e3 ^ e4)

8psi[40] = -0.75; // e3 ^ (er1 ^ er2)

9psi[41] = -0.5; // e4 ^ (er1 ^ er2)

10psi[42] = 0.25; // e1 ^ (e2 ^ (e3 ^ e4))

11psi[50] = -0.25; // e1 ^ (e3 ^ (er1 ^ er2))

12psi[51] = -1.0; // e1 ^ (e4 ^ (er1 ^ er2))

13psi[54] = 1.0; // e2 ^ (e3 ^ (er1 ^ er2))

14psi[55] = -0.25; // e2 ^ (e4 ^ (er1 ^ er2))

15psi[59] = 0.5; // e1 ^ (e2 ^ (e3 ^ (er1 ^ er2)))

16psi[60] = -0.75; // e1 ^ (e2 ^ (e4 ^ (er1 ^ er2)))

17SwapPsi[0] = 0.25; // 1.0

18SwapPsi[1] = 0.5; // e1

19SwapPsi[2] = 0.75; // e2

20SwapPsi[7] = 1.0; // e1 ^ e2

21SwapPsi[16] = -1.0; // e3 ^ e4

22SwapPsi[26] = -0.75; // e1 ^ (e3 ^ e4)

23SwapPsi[32] = 0.5; // e2 ^ (e3 ^ e4)

24SwapPsi[40] = -0.5; // e3 ^ (er1 ^ er2)

25SwapPsi[41] = -0.75; // e4 ^ (er1 ^ er2)

26SwapPsi[42] = 0.25; // e1 ^ (e2 ^ (e3 ^ e4))

27SwapPsi[50] = -0.25; // e1 ^ (e3 ^ (er1 ^ er2))

28SwapPsi[51] = -1.0; // e1 ^ (e4 ^ (er1 ^ er2))

29SwapPsi[54] = 1.0; // e2 ^ (e3 ^ (er1 ^ er2))

30SwapPsi[55] = -0.25; // e2 ^ (e4 ^ (er1 ^ er2))

31SwapPsi[59] = 0.75; // e1 ^ (e2 ^ (e3 ^ (er1 ^ er2)))

32SwapPsi[60] = -0.5; // e1 ^ (e2 ^ (e4 ^ (er1 ^ er2)))

Note that the groups of coordinates $\\{0,42,50,55\\}$ and $\\{7,16,51,54\\}$,
which refer to the coefficients of $|00\rangle$ and $|11\rangle$ respectively,
remained unchanged from `psi` to `SwapPsi`, as expected. However, note that
the coefficients in the coordinates $\\{2,26,41,59\\}$ of `psi` that
corresponds to $|01\rangle$ was exactly 2 times the coefficients of `ket01`
given by 4 and, in `SwapPsi`, they became 3 times those same coefficients. On
the other hand, the coordinates $\\{1,32,40,60\\}$ changed from 3 (in `psi`)
to 2 (in `SwapPsi`) times the coefficients of `ket10` in 4, that corresponds
to $|10\rangle.$ So, the output vector `SwapPsi` is exactly the vector
$|\bar{\psi}\rangle$.

##  8 Conclusion

In this paper, we presented how natural Geometric Algebra can be used for
quantum computing. Based on the newly developed QRA and its support by the
extended GAALOP tool, the handling of quantum computing is strongly
simplified, especially for beginners. The big advantage for quantum computing
beginners is that they only have to know Geometric Algebra in order to
describe the objects and operations of quantum computing. We hope that this
can be the reason for Geometric Algebra to become ”the” language for quantum
computing in the future.

## References

  * [1] Alves, R., Hildenbrand, D., Hrdina, J. et al.: _An Online Calculator for Quantum Computing Operations Based on Geometric Algebra_ Adv. Appl. Clifford Algebras 32, 4 (2022)
  * [2] Hrdina J., Navrat A., Vasik P.: Quantum computing based on complex Clifford algebras, accepted in Quantum Information Processing, arXiv(quant-ph):2201.02246 (2022)
  * [3] Cafaro, C., Mancini, S. _A Geometric Algebra Perspective on Quantum Computational Gates and Universality in Quantum Computing_. Adv. Appl. Clifford Algebras 21, 493–519 (2011). https://doi.org/10.1007/s00006-010-0269-x
  * [4] Chris Doran, Anthony Lasenby, Geometric Algebra for Physicists, Cambridge University Press (2003) DOI:https://doi.org/10.1017/CBO9780511807497
  * [5] Dorst, L.: Geometric Algebra for Computer Science, An Object-Oriented Approach to Geometry. Morgan Kauffmann, San Francisco (2007).
  * [6] Hildenbrand, D.: _Foundations of Geometric Algebra Computing_. Springer Science & Business Media (2013).
  * [7] Hildenbrand, D.: _The Power of Geometric Algebra Computing_. CRC Press, Taylor & Francis Group, (2022).
  * [8] Nielsen, M., Chuang, I.: _Quantum Computation and Quantum Information: 10th Anniversary Edition_. Cambridge: Cambridge University Press (2010) doi:10.1017/CBO9780511976667
  * [9] Perwass, Ch.: _Geometric Algebra with Applications in Engineering_ (1st edn). Springer Verlag, (2009).
  * [10] de Lima Marquezino Franklin, Portugal R., Lavor C.: A Primer on Quantum Computing. Springer Publishing Company (2019)


# Strongly universal string hashing is fast

Owen Kaser<EMAIL_ADDRESS>Daniel Lemire<EMAIL_ADDRESS>Dept. of
CSAS, University of New Brunswick, 100 Tucker Park Road, Saint John, NB,
Canada LICEF, Université du Québec à Montréal (UQAM), 100 Sherbrooke West,
Montreal, QC, H2X 3P2 Canada

###### Abstract

We present fast strongly universal string hashing families: they can process
data at a rate of 0.2 CPU cycle per byte. Maybe surprisingly, we find that
these families—though they requires a large buffer of random numbers—are often
faster than popular hash functions with weaker theoretical guarantees.
Moreover, conventional wisdom is that hash functions with fewer
multiplications are faster. Yet we find that they may fail to be faster due to
operation pipelining. We present experimental results on several processors
including low-powered processors. Our tests include hash functions designed
for processors with the Carry-Less Multiplication (CLMUL) instruction set. We
also prove, using accessible proofs, the strong universality of our families.

###### keywords:

String Hashing , Superscalar Computing , Barrett Reduction , Carry-less
multiplications , Binary Finite Fields

##  1 Introduction

For 32-bit numbers, random hashing with good theoretical guarantees can be
just as fast as popular alternatives [1]. In turn, these guarantees ensure the
reliability of various algorithms and data structures: frequent-item mining
[2], count estimation [3, 4], and hash tables [5, 6]. We want to show that we
can also get good theoretical guarantees over larger objects (such as strings)
without sacrificing speed. For example, we consider variable-length strings
made of 32-bit characters: all data structures can be represented as such
strings, up to some padding.

We restrict our attention to hash functions mapping strings to $L$-bit
integers, that is, integer in $[0,2^{L})$ for some positive integer $L$. In
random hashing, we select a hash function at random from a family [7, 8]. The
hash function can be chosen whenever the software is initialized. While random
hashing is not yet commonplace, it can have significant security benefits [9]
in a hash table: without randomness, an attacker can more easily exploit the
fact that adding $n$ keys hashing to the same value typically takes quadratic
time ($\Theta(n^{2})$). For this reason, random hashing was adopted in the
Ruby language as of version 1.9 [10] and in the Perl language as of version
5.8.1.

A family of hash functions is $k$-wise independent if the hash values of any
$k$ distinct elements are independent. For example, a family is pairwise
independent—or strongly universal—if given any two distinct elements $s$ and
$s^{\prime}$, their hash values $h(s)$ and $h(s^{\prime})$ are independent:

$\displaystyle P(h(s)=y|h(s^{\prime})=y^{\prime})=P(h(s)=y)$

for any two hash values $y,y^{\prime}$. When a hashing family is not strongly
universal, it can still be universal if the probability of a collision is no
larger than if it were strongly universal: $P(h(s)=h(s^{\prime}))\leq 1/2^{L}$
when $2^{L}$ is the number of hash values. If the collision probability is
merely bounded by some $\epsilon$ larger than $1/2^{L}$ but smaller than $1$
($P(h(s)=h(s^{\prime}))\leq\epsilon<1$), we have an almost universal family.
However, strong universality might be more desirable than universality or
almost universality:

  * 1.

We say that a family is uniform if all hash values are equiprobable
($P(h(s)=y)=1/2^{L}$ for all $y$ and $s$): strongly universal families are
uniform, but universal or almost universal families may fail to be uniform. To
see that universality fails to imply uniformity, consider the family made of
the two functions over 1-bit integers (0,1): the identity and a function
mapping all values to zero. The probability of a collision between two
distinct values is exactly $1/2$ which ensures universality even though we do
not have uniformity since $P(h(0)=0)=1$.

  * 2.

Moreover, if we have strong universality over $L$ bits, then we also have it
over any subset of bits. The corresponding result may fail for universal and
almost universal families: we might have universality over $L$ bits, but fail
to have almost universality over some subset of bits. Consider the non-uniform
but universal family $\\{h(x)=x\\}$ over $L$-bit integers: if we keep only the
least significant $L^{\prime}$ bits ($0<L^{\prime}<L$), universality is lost
since $h(0)\bmod{2^{L^{\prime}}}=h(2^{L^{\prime}})\bmod{2^{L^{\prime}}}$.

There is no need to use slow operations such as modulo operations, divisions
or operations in finite fields to have strong universality. In fact, for short
strings having few distinct characters, Zobrist hashing requires nothing more
than table look-ups and bitwise exclusive-or operations, and it is more than
strongly universal (3-wise independent) [11, 12]. Unfortunately, it becomes
prohibitive for long strings as it requires the storage of $nc$ random numbers
where $n$ is the maximal length of a string and $c$ is the number of distinct
characters.

A more practical approach to strong universality is Multilinear hashing (§ 2).
Unfortunately, it normally requires that the computations be executed in a
finite field. Some processors have instructions for finite fields (§ 4) or
they can be emulated with a software library (§ 5.3). However, if we are
willing to double the number of random bits, we can implement it using regular
integer arithmetic. Indeed, using an idea from Dietzfelbinger [13], we
implement it using only one multiplication and one addition per character (§
3). We further attempt to speed it up by reducing the number of
multiplications by half. We believe that these families are the fastest
strongly universal hashing families on current computers. We evaluate these
hash families experimentally (§ 5):

  * 1.

Using fewer multiplications has often improved performance, especially on low-
power processors [14]. Yet trading away the number of multiplications fails to
improve (and may even degrade) performance on several processors according to
our experiments—which include low-power processors. However, reducing the
number of multiplications is beneficial on other processors (e.g., AMD), even
server-class processors.

  * 2.

We also find that strongly universal hashing may be computationally
inexpensive compared to common hashing functions, as long as we ignore the
overhead of generating long strings of random numbers. In effect—if memory is
abundant compared to the length of the strings—the strongly universal
Multilinear family is faster than many of the commonly used alternatives.

  * 3.

We consider hash functions designed for hardware supported carry-less
multiplications (§ 4). This support should drastically improve the speed of
some operations over binary finite fields ($GF(2^{L})$). Unfortunately, we
find that the carry-less hash functions fail to be competitive (§ 5.4).

##  2 The Multilinear family

The Multilinear hash family is one of the simplest strongly universal family
[7]. It takes the form of a scalar product between random values (sometimes
called keys) and string components, where operations are over a finite field:

$\displaystyle h(s)=m_{1}+\sum_{i=1}^{n}m_{i+1}s_{i}.$

The hash function $h$ is defined by the randomly generated values
$m_{1},m_{2},\dots$ It is strongly universal over fixed-length strings. We can
also apply it to variable-length strings as long as we forbid strings ending
with zero. To ensure that strings never end with zero, we can append a
character value of one to all variable-length strings.

An apparent limitation of this approach is that strings cannot exceed the
number of random values. In effect, to hash 32-bit strings of length $n$, we
need to generate and store $32(n+1)$ random bits using a finite field of
cardinality $2^{32}$. However, Stinson [15] showed that strong universality
requires at least $1+a(b-1)$ hash functions where $a$ is the number of strings
and $b$ is the number of hash values. Thus, if we have 32-bit strings mapped
to 32-bit hash values, we need at least $\approx 2^{32(n+1)}$ hash functions:
Multilinear is almost optimal.

Hence, the requirement to store many random numbers cannot be waived without
sacrificing strong universality. Note that Stinson’s bound is not affected by
manipulations such as treating a length $n$ string of $W$-bit words as a
length $n/2$ string of $2W$-bit words.

If multiplications are expensive and we have long strings, we can attempt to
improve speed by reducing the number of multiplications by half [16, 17]:

$\displaystyle h(s)=m_{1}+\sum_{i=1}^{n/2}(m_{2i}+s_{2i-1})(m_{2i+1}+s_{2i}).$
(1)

While this new form assumes that the number of characters in the string is
even, we can simply pad the odd-length strings with an extra character with
value zero. With variable-length strings, the padding to even length must
follow the addition of a character value of one.

Could we reduce the number of multiplications further? Not in general: the
computation of a scalar product between two vectors of length $n$ requires at
least $\lceil n/2\rceil$ multiplications [18, Corollary 4]. However, we could
try to avoid generic multiplications altogether and replace them by squares
[14]:

$\displaystyle h(s)=m_{1}+\sum_{i=1}^{n}(m_{i+1}+s_{i})^{2}.$

Indeed, squares can be sometimes be computed faster. Unfortunately, this
approach fails in binary finite fields ($GF(2^{L})$) because

$\displaystyle(m_{i+1}+s_{i})^{2}$ $\displaystyle=$ $\displaystyle
m_{i+1}^{2}+m_{i+1}s_{i}+m_{i+1}s_{i}+s_{i}^{2}$ $\displaystyle=$
$\displaystyle m_{i+1}^{2}+s_{i}^{2}$

since every element is its own additive inverse. Thus, we get

$\displaystyle h(s)=m_{1}+\sum_{i=1}^{n}m_{i+1}^{2}+\sum_{i=1}^{n}s_{i}^{2}$

which is a poor hash function (e.g., $h(\texttt{ab})=h(\texttt{ba})$).

There are fast algorithms to compute multiplications [19, 20, 21] in binary
finite fields. Yet these operations remain much slower than a native operation
(e.g., a regular 32-bit integer multiplication). However, some recent
processors have support for finite fields. In such cases, the penalty could be
small for using finite fields, as opposed to regular integer arithmetic (see §
4 and § 5.4). (Though they are outside our scope, there are also fast
techniques for computing hash functions over a finite field having prime
cardinality [22].)

##  3 Making Multilinear strongly universal in the ring
$\mathbb{Z}/2^{K}\mathbb{Z}$

On processors without support for binary finite fields, we can trade memory
for speed to essentially get the same properties as finite fields on _some_ of
the bits using fast integer arithmetic. For example, Dietzfelbinger [13]
showed that the family of hash functions of the form

$\displaystyle h_{A,B}(x)=\left(Ax+B\mod{2^{K}}\right) \div 2^{L-1}$

where the integers $A,B\in[0,2^{K})$ and $x\in[0,2^{L})$ is strongly universal
for $K>L-1$. (For fewer parentheses, we adopt the convention that
$Ax+B\mod{2^{K}}\equiv(Ax+B)\bmod{2^{K}}$. The symbol $\div$ denotes integer
division: $x\div y=\lfloor x/y\rfloor$ for positive integers.) We generalize
Dietzfelbinger hashing from the linear to the multilinear case.

The main difference between a finite field and common integer arithmetic (in
the integer ring $\mathbb{Z}/2^{K}\mathbb{Z}$) is that elements of fields have
inverses: given the equation $ax=b$, there is a unique solution $x=a^{-1}b$
when $a\neq 0$. However, the same is “almost” true in integer rings used for
computer arithmetic as long as the variable $a$ is small. For example, when
$a=1$, we can solve for $ax=b$ exactly ($x=b$). When $a=2$, then there are at
most two solutions to the equation $ax=b$. We build on these observations to
derive a stronger result.

We let $\tau=\textrm{trailing}(a)$ be the number of trailing zeros of the
integer $a$ in binary notation. For example, we have that
$\textrm{trailing}(2^{j})=j$.

###### Proposition 1

Given integers $K,L$ satisfying $K\geq L-1\geq 0$, consider the equation

$\displaystyle\left(ax+c\mod{2^{K}}\right)\div 2^{L-1}=b$

where $a$ is an integer in $[1,2^{L})$, $b$ is an integer in $[0,2^{K-L+1})$
and $c$ an integer in $[0,2^{K})$. Given $a$, $b$ and $c$, there are exactly
$2^{L-1}$ integers $x$ in $[0,2^{K})$ satisfying the equation.

Proof. Let $\tau=\textrm{trailing}(a)$. We have $\tau\leq L-1$ since
$a\in[1,2^{L})$. Because $a$ is non-zero, we have that $a^{\prime}=a\div
2^{\tau}$ is odd and $a=2^{\tau}a^{\prime}$.

We have
$\left((ax+c)\bmod{2^{K}}\right)\div
2^{L-1}=\left((2^{\tau}a^{\prime}x+c)\bmod{2^{K}}\right)\div 2^{L-1}$

$\displaystyle=$ $\displaystyle\left(2^{\tau}[a^{\prime}x+(c\div
2^{\tau})]+(c\bmod{2^{\tau}})\mod{2^{K}}\right)\div 2^{L-1}.$

We show that the term $(c\bmod{2^{\tau}})$ can be removed. Indeed, the $\tau$
least significant bits of $2^{\tau}[a^{\prime}x+(c\div 2^{\tau})]+(c\bmod
2^{\tau})$ are those of $c\mod{2^{\tau}}$ whereas the more significant bits
are those of $2^{\tau}[a^{\prime}x+(c\div 2^{\tau})]$. The final division by
${2^{L-1}}$ will dismiss the $L-1$ least significant bits, and $\tau\leq L-1$,
so that the term $(c\bmod{2^{\tau}})$ can be ignored.

Hence, we have
$\left(ax+c\mod{2^{K}}\right)\div 2^{L-1}=(2^{\tau}[a^{\prime}x+(c\div
2^{\tau})]\mod{2^{K}})\div 2^{L-1}$

$\displaystyle=$ $\displaystyle\left(2^{\tau}\left[a^{\prime}x+(c\div
2^{\tau})\mod{2^{K-\tau}}\right]\right)\div 2^{L-1}$ $\displaystyle=$
$\displaystyle\left(a^{\prime}x+(c\div 2^{\tau})\mod{2^{K-\tau}}\right)\div
2^{L-1-\tau}$ $\displaystyle=$
$\displaystyle\left(a^{\prime}(x\bmod{2^{K-\tau}})+(c\div
2^{\tau})\mod{2^{K-\tau}}\right)\div 2^{L-1-\tau}.$

Setting $x^{\prime}=x\bmod{2^{K-\tau}}$ and $c^{\prime}=c\div 2^{\tau}$, we
finally have

$\displaystyle\left(ax+c\mod{2^{K}}\right)\div
2^{L-1}=\left(a^{\prime}x^{\prime}+c^{\prime}\mod{2^{K-\tau}}\right)\div
2^{L-1-\tau}.$

Let $z$ be an integer such that $z\div 2^{L-1-\tau}=b$. Consider
$a^{\prime}x^{\prime}+c^{\prime}\mod{2^{K-\tau}}=z$. We can rewrite it as
$a^{\prime}x^{\prime}\bmod{2^{K-\tau}}=z-c^{\prime}\bmod{2^{K-\tau}}$. Because
$a^{\prime}$ is odd, $a^{\prime}$ and $2^{K-\tau}$ are coprime (their greatest
common divisor is 1). Hence, there is a unique integer
$x^{\prime}\in[0,2^{K-\tau})$ such that
$a^{\prime}x^{\prime}\bmod{2^{K-\tau}}=z-c^{\prime}\bmod{2^{K-\tau}}$ [23,
Cor. 31.25].

Given $b$, there are $2^{L-1-\tau}$ integers $z$ such that $z\div
2^{L-1-\tau}=b$. Given $x^{\prime}$, there are $2^{\tau}$ integers $x$ in
$[0,2^{K})$ such that $x^{\prime}=x\bmod{2^{K-\tau}}$. It follows that there
are $2^{L-1-\tau}\times 2^{\tau}=2^{L-1}$ integers $x$ in $[0,2^{K})$ such
that $\left(a^{\prime}x^{\prime}+c^{\prime}\mod{2^{K-\tau}}\right)\div
2^{L-1-\tau}=b$ holds. $\square$

###### Example 1

Consider the equation $(6x+10\bmod 64)\div 4=5$. By Proposition 1, there must
be exactly 4 solutions to this equation (setting $K=6,L=3$). We can find them
using the proof of the lemma. The integer $6$ has 1 trailing zero in binary
notation ($110$) so that $\tau=1$. We can write $6=2\times 3$ so that
$a^{\prime}=3$. Similarly, $c^{\prime}=10\div 2=5$. Hence we must consider the
equation $3x^{\prime}+5\bmod{2^{5}}=z$ for values of $z$ such that $z\div
2=5$. There are two such values: $z=10$ and $z=11$. We have that

$\displaystyle 3x^{\prime}+5\bmod{32}=10\Rightarrow
3x^{\prime}\bmod{32}=5\Rightarrow x^{\prime}=23\text{~{}and}$ $\displaystyle
3x^{\prime}+5\bmod{32}=11\Rightarrow 3x^{\prime}\bmod{32}=6\Rightarrow
x^{\prime}=2.$

It remains to solve for $x$ in $x^{\prime}=x\bmod 32$ with the constraint that
$x$ is an integer in $[0,64)$. When $x^{\prime}=2$, we have that
$x\in\\{2,34\\}$. When $x^{\prime}=23$, we have that $x\in\\{23,55\\}$. Hence,
the solutions are 2, 23, 34 and 55.

Using Proposition 1, we can show that fast variations of Multilinear are
strongly universal even though we use regular integer arithmetic, not finite
fields.

###### Theorem 1

Given integers $K,L$ satisfying $K\geq L-1\geq 0$, consider the families of
$(K-L+1)$-bit hash functions

  * 1.

Multilinear:

$\displaystyle
h(s)=\left(\left(m_{1}+\sum_{i=1}^{n}m_{i+1}s_{i}\right)\mod{2^{K}}\right)\div
2^{L-1}$

  * 2.

Multilinear-HM:

$\displaystyle
h(s)=\left(\left(m_{1}+\sum_{i=1}^{n/2}(m_{2i}+s_{2i-1})(m_{2i+1}+s_{2i})\right)\mod{2^{K}}\right)\div
2^{L-1}$

which assumes that $n$ is even.

Here the $m_{i}$’s are random integers in $[0,2^{K})$ and the string
characters $s_{i}$ are integers in $[0,2^{L})$. These two families are
strongly universal over fixed-length strings, or over variable-length strings
that do not end with the zero character. We can apply the second family to
strings of odd length by appending an extra zero element so that all strings
have an even length.

Proof. We begin with the first family (Multilinear). Given any two distinct
strings $s$ and $s^{\prime}$, consider the equations $h(s)=y$ and
$h(s^{\prime})=y^{\prime}$ for any two hash values $y$ and $y^{\prime}$.
Without loss of generality, we can assume that the strings have the same
length. If not, we can pad the shortest string with zeros without changing its
hash value. We need to show that $P(h(s)=y\land
h(s^{\prime})=y^{\prime})=2^{2(L-K-1)}$. Because the two strings are distinct,
we can find $j$ such that $s_{j}\neq s^{\prime}_{j}$. Without loss of
generality, assume that $s^{\prime}_{j}-s_{j}\in[0,2^{L})$.

We want to solve the equations

$\displaystyle\left(\left(m_{1}+\sum_{i=1}^{n}m_{i+1}s_{i}\right)\mod{2^{K}}\right)\div
2^{L-1} $ $\displaystyle=$ $\displaystyle y,$ (2)
$\displaystyle\left(\left(m_{1}+\sum_{i=1}^{n}m_{i+1}s^{\prime}_{i}\right)\mod{2^{K}}\right)\div
2^{L-1} $ $\displaystyle=$ $\displaystyle y^{\prime}$ (3)

for integers $m_{1},m_{2},\ldots$ in $[0,2^{K})$.

Consider the following equation

$\displaystyle\left(m_{1}+\sum_{i=1}^{n}m_{i+1}s_{i}\right)\mod{2^{K}} $
$\displaystyle=$ $\displaystyle z.$

There is a bijection between $m_{1}$ and $z\in[0,2^{K})$. That is, for every
value of $m_{1}$, there is a unique $z$, and vice versa. Specifically, we have

$\displaystyle m_{1} $ $\displaystyle=$ $\displaystyle
z-\sum_{i=1}^{n}m_{i+1}s_{i}\mod{2^{K}}.$

If we choose $z$ such that $z\div 2^{L-1}=y$, we effectively solve Equation 2.
By substitution in Equation 3, we have

$\displaystyle\left(m_{j+1} (s^{\prime}_{j}-s_{j})+z+\sum_{i\neq
j,i=1}^{n}m_{i+1}(s^{\prime}_{i}-s_{i})\mod{2^{K}}\right)\div
2^{L-1}=y^{\prime}.$

This equation is independent of $m_{1}$. By Proposition 1, there are exactly
$2^{L-1}$ solutions $m_{j+1}$ to this last equation. (Indeed, in the statement
of Proposition 1, substitute $m_{j+1}$ for $x$, $s^{\prime}_{j}-s_{j}$ for
$a$, $z+\sum_{i\neq j,i=1}^{n}m_{i+1}(s^{\prime}_{i}-s_{i})\mod{2^{K}}$ for
$b$ and $y^{\prime}$ for $b$.)

Meanwhile, there are $2^{L-1}$ possible values $z$ such that $z\div
2^{L-1}=y$. Because there is a bijection between $m_{1}$ and $z$, there are
also $2^{L-1}$ possible values for $m_{1}$.

So, focusing only on $m_{1}$ and $m_{j+1}$, there are $2^{L-1}\times 2^{L-1}$
values satisfying $h(s)=y$ and $h(s^{\prime})=y^{\prime}$. Yet there are
$2^{K}\times 2^{K}$ possible pairs $m_{1},m_{j+1}$. Thus the probability that
$h(s)=y$ and $h(s^{\prime})=y^{\prime}$ is $\frac{2^{L-1}\times
2^{L-1}}{2^{K}\times 2^{K}}=2^{2(L-K-1)}$ which completes the proof for the
first family.

The proof that the second family (Multilinear-HM) is strongly universal is
similar. As before, set $z$ in $[0,2^{K})$ such that $z\div 2^{L-1}=y$. Solve
for $m_{1}$ from the first equation:

$\displaystyle
m_{1}=\left(z-\sum_{i=1}^{n/2}(m_{2i}+s_{2i-1})(m_{2i+1}+s_{2i})\right)\mod{2^{K}}.$

Then by substitution, we get

$\displaystyle\Bigg{(}\Bigg{(}\sum_{i=1}^{n/2}(m_{2i}+s^{\prime}_{2i-1})(m_{2i+1}+s^{\prime}_{2i})$
$\displaystyle-$ $\displaystyle(m_{2i}+s_{2i-1})(m_{2i+1}+s_{2i})$
$\displaystyle+$ $\displaystyle z\Bigg{)}\mod 2^{K}\Bigg{)}\div
2^{L-1}=y^{\prime}.$

We can rewrite this last equation, as either
$((m_{j}(s^{\prime}_{j}-s_{j})+\rho+z\mod 2^{K})\div 2^{L-1}=y^{\prime}$ if
$j$ is even or as $((m_{j+1}(s^{\prime}_{j}-s_{j})+\rho+z\mod 2^{K})\div
2^{L-1}=y^{\prime}$ if $j$ is odd, where $\rho$ is independent of either
$m_{j}$ ($j$ even) or $m_{j+2}$ ($j$ odd). As before, by Proposition 1, there
are exactly $2^{L-1}$ solutions for $m_{j}$ ($j$ even) or $m_{j+2}$ ($j$ odd)
if $z$ is fixed. As before, there are $2^{L-1}$ distinct possible values for
$z$, and $2^{L-1}$ distinct corresponding values for $m_{1}$. Hence, the pair
$m_{1},m_{j}$ can take $2^{L-1}\times 2^{L-1}$ distinct values out of
$2^{K}\times 2^{K}$ values, which completes the proof. $\square$

To apply Theorem 1 to variable-length strings, we can append the character
value one to all strings so that they never end with the character value zero,
as in § 2. If we use Multilinear-HM, we should add the character value one
before padding odd-length strings to an even length.

Theorem 1 is both more general (because it includes strings) and more specific
(because the cardinality of the set of hash values is a power of two) than a
similar result by Dietzfelbinger [13, Theorem 4]. However, we believe our
proof is more straightforward: we mostly use elementary mathematics.

While Dietzfelbinger did not consider the multilinear case, others proposed
variations suited to string hashing. Pǎtraşcu and Thorup [24] state without
proof that Multilinear-HM over strings of length two is strongly universal for
$K=64,L=32$. They extend this approach to strings, taking characters two by
two:

$\displaystyle
h(s)=\left(\left(\bigoplus_{i=1}^{n/2}(m_{3i-2}+s_{2i-1})(m_{3i-1}+s_{2i})+m_{3i}\right)\mod{2^{K}}\right)\div
2^{L}$

where $\bigoplus$ is the bitwise exclusive-or operation and $n$ is even.
Unfortunately, their approach uses more operations and requires 50% more
random numbers than Multilinear-HM. They also refer to an earlier reference
[25] where a similar scheme was erroneously described as universal, and
presented as folklore:

$\displaystyle
h(s)=\left(\left(\bigoplus_{i=1}^{n/2}(m_{2i+1}+s_{2i+1})(m_{2i+2}+s_{2i+2})\right)\mod{2^{K}}\right)\div
2^{L}$

where $n$ is even. To falsify the universality of this last family, we can
verify numerically that for $K=6,L=3$, the strings $0,0$ and $2,6$ collide
with probability $\frac{576}{4096}>\frac{1}{2^{3}}$. In any case, we see no
benefit to this last approach for long strings because Multilinear-HM is
likely just as fast, and it is strongly universal.

###  3.1 Implementing Multilinear

If 32-bit values are required, we can generate a large buffer of 64-bit
unsigned random integers $m_{i}$. The computation of either

$\displaystyle
h(s)=\left(m_{1}+\sum_{i=1}^{n}m_{i+1}s_{i}\mod{2^{64}}\right)\div 2^{32}$

or

$\displaystyle
h(s)=\left(m_{1}+\sum_{i=1}^{n/2}(m_{2i}+s_{2i-1})(m_{2i+1}+s_{2i})\mod{2^{64}}\right)\div
2^{32}$

is then a simple matter using unsigned integer arithmetic common to most
modern processors. The division by $2^{32}$ can be implemented efficiently by
a right shift (`>>`32).

One might object that according to Theorem 1, 63-bit random numbers are
sufficient if we wish to hash 32-bit characters to a 32-bit hash value. The
division by $2^{32}$ should then be replaced by a division by $2^{31}$.
However, we feel that such an optimization is unlikely to either save memory
or improve speed.

Multilinear is essentially an inner product and thus can benefit from
multiply-accumulate CPU instructions: by processing the multiplication and the
subsequent addition as one machine operation, the processor may be able to do
the computation faster than if the computations were done separately. Several
processors have such integer multiply-accumulate instructions (ARM, MIPS,
Nvidia and PowerPC). Comparatively, we do not know of any multiply-xor-
accumulate instruction in popular processors.

Unfortunately, some languages—such as Java—fail to support unsigned integers.
With a two’s complement representation, the de facto standard in modern
processors, additions and multiplications give identical results, up to
overflow flags, as long as no promotion is involved: e.g., multiplying 32-bit
integers using 32-bit arithmetic, or 64-bit integers using 64-bit arithmetic.
However, we must still be careful: promotions and divisions differ when we use
signed integers:

  * 1.

If we store string characters using 32-bit integers (int) and random values as
64-bit integers (long), Java will sign-extend the 32-bit integer to a 64-bit
integer when computing $\texttt{m}_{i+1}*\texttt{s}_{i}$, giving an unintended
result for negative string characters. Use
$\texttt{m}_{i+1}*(\texttt{s}_{i}\&\texttt{0xFFFFFFFFl})$ instead.

  * 2.

Unsigned and signed divisions differ. Correspondingly, for the division by
$2^{32}$—to retrieve the 32 most significant bits—the unsigned right-shift
operator (`>>>`) must be used in Java, and not the regular right shift (`>>`).

Because we assume that the number of bits is a constant, the computational
complexity of Multilinear is linear ($O(n)$). Multilinear uses $n$
multiplications, $n$ additions, and one shift, whereas Multilinear-HM uses
$n/2$ multiplications, $3n/2$ additions, and one shift. In both cases we use
$2n+1$ operations, although there may be benefits to having fewer
multiplications. (Admittedly, Single Instruction, Multiple Data (SIMD)
processors can do several instructions at once.)

Consider that we need at least $\approx 32(n+1)$ random bits for strongly
universal 32-bit hashing of $32n$ bits [15]. That is, we must aggregate
$\approx 64n+32$ bits into a 32-bit hash value. Assume that we only allow
unary and binary operations. A 32-bit binary operation maps 64 bits to 32
bits, a reduction of 32 bits. Hence, we require at least $2n$ 32-bit
operations for strongly universal hashing. Alternatively, we require at least
$n$ 64-bit operations. Hence, for $n$ large, Multilinear and Multilinear-HM
use at most twice the minimal number of operations.

###  3.2 Word size optimization

The number of required bits is application dependent: for a hash table, one
may be able to bound the maximum table size. In several languages such as
Java, 32-bit hash values are expected. Meanwhile the key parameters of our
hash functions Multilinear and Multilinear-HM are $L$ (the size of characters)
and $K$ (the size of the operations), and these two hash functions deliver
$K-L+1$ usable bits.

However, both $K$ and $L$ can be adjusted given a desired number of usable
random bits. Indeed, a length $n$ string of $L$-bit characters can be
reinterpreted as a length $n\lceil L/L^{\prime}\rceil$ string of
$L^{\prime}$-bit characters, for any non-zero $L^{\prime}$. Thus, we can
either grow $L$ and $K$ or reduce $L$ and $K$, for the same number of usable
bits.

To reduce the need for random bits, we should use large values of $K$.
Consider a long input string that we can represent as a string of 32-bit or
96-bit characters. Assume we want 32-bit hash values. Assume also that our
random data only comes in strings of 64-bit or 128-bit characters. If we
process the string as a 32-bit string, we require 64 random bits per
character. The ratio of random strings to hashed strings is two. If we process
the string as a 96-bit string, we require 128 random bits per character and
the ratio of random strings to hashed strings is $128/96=4/3\approx 1.33$.
What if we could represent the string using 224-bit characters and have random
bits packaged into characters of 256 bits? We would then have a ratio of
$8/7\approx 1.14$.

We can formalize this result. Suppose we require $z$ pairwise independent bits
and that we have $M$ input bits. Stinson [15] showed that this requires at
least $1+2^{M}(2^{z}-1)$ hash functions or, equivalently,
$\log(1+2^{M}(2^{z}-1))$ random bits. Thus, given any hashing family, the
ratio of its required number of random bits to the Stinson limit (henceforth
Stinson ratio) must be greater or equal to one. The $M$ input bits can be
represented as an $L$-bit $n$-character string for $M=nL$. Under Multilinear
(and Multilinear-HM), we must have $z=K-L+1$. Thus we use
$K(n+1)=(z+L-1)(\lceil M/L\rceil+1)$ random bits. We have that $(z+L-1)(\lceil
M/L\rceil+1)\leq(z+L-1)(M/L+2)$ which is minimized when

$L=\sqrt{(z-1)\frac{M}{2}}.$ (4)

Rounding $L=\sqrt{(z-1)M/2}$ up and substituting it back into $(z+L-1)(\lceil
M/L\rceil+1)$, we get an upper bound on the number of random bits required by
Multilinear. This bound is nearly optimal when $\lceil M/L\rceil\approx M/L$,
that is, when $M$ is large. Unfortunately, this estimate fails to consider
that word sizes are usually prescribed. For example, we could be required to
choose $K\in\\{8,16,32,64\\}$. That is, we have to choose
$L\in\\{9-z,17-z,33-z,65-z\\}$. Fig. 1 shows the corresponding Stinson ratios.
When there are many input bits ($M\gg 1$), the ratio of Multilinear converges
to one. That is, as long as we can decompose input data into strings of large
characters (having $\approx\sqrt{(z-1)M/2}$ bits), Multilinear requires almost
a minimal number of bits. This may translate into an optimal memory usage.
(The result also holds for Multilinear-HM except that it is slightly less
efficient for strings having an odd number of characters.) If we restrict the
word sizes to common machine word sizes ($K\in\\{8,16,32,64\\}$), the ratio is
$\approx 2$ for large input strings. We also consider the case where we could
use 128-bit words ($K\in\\{8,16,32,64,128\\}$). It improves the ratio
noticeably ($\approx 1.33$), as expected.

Figure 1:  For large inputs, Multilinear requires an almost optimal number of
random bits when arbitrary word sizes ($K$) are allowed. It has lower
efficiency when the word size is constrained. The plot was generated for
32-bit hash values ($z=32$).

We can also choose the word size ($K$) to optimize speed. On a 64-bit
processor, setting $K=64$ would make sense. We can compare this default with
two alternatives:

  1. 1.

We can try to support much larger words using fast multiplication algorithms
such as Karatsuba’s. We could merely try to minimize the number of random
bits. However, this ignores the growing computation cost of multiplications
over many bits, e.g., Karatsuba’s algorithm is in $\Omega(n^{1.58})$. For
simplicity, suppose that the cost of $K$-bit multiplication costs $K^{a}$ time
for $a>1$. Roughly speaking, to hash $M$ bits, we require $\lceil M/L\rceil$
multiplications. When we have long strings ($M\gg L$), we can simplify $\lceil
M/L\rceil\approx M/L$. If we desire $z$-bit hash values, then we need to use
multiplication on $K=z+L-1$ bits. Thus, the processing cost can be (roughly)
approximated as $\frac{M(z+L-1)^{a}}{L}$. Starting from $L=1$, this function
initially decreases to a minimum at

$L=\frac{z-1}{a-1}$ (5)

before increasing again as $L^{a-1}$. (When $a=1.5$ and $z=32$, we have
$\frac{z-1}{a-1}=62$.) See Fig. 2. Hence, while we can minimize the total
number of random bits by using many bits per character ($L$ large), we may
want to keep $L$ relatively small to take into account the superlinear cost of
multiplications.

  2. 2.

We can support 128-bit words on a 64-bit processor, with some overhead.
(Recent GNU GCC compilers have the __uint128 type, as a C-language extension.)
A single 128-bit multiplication may require up to three 64-bit
multiplications. However, it processes more data: with $z=32$ hashed bits,
each 128-bit multiplication hashes 97 input bits. Comparatively, setting
$K=64$, we require a single 64-bit multiplication, but we process only 32 bits
of data. (Formally, we could process 33 bits of data, but for convenient
implementation, we process data in powers of two.) Hence, it is unclear which
approach is faster: three 64-bit multiplications and 128 bits of random data
to process 97 input bits, or a single 64-bit multiplication and 64 bits of
random data, to process 33 input bits. However, the 128-bit approach will use
33% fewer random bits. Going to 256-bit word sizes would only reduce the
number of random bits by 14%: using larger and larger words leads to
diminishing returns.

We assess these two alternatives experimentally in § 5.5.

Figure 2:  Modeled computational cost per bit as a function of the number of
bits per character ($\frac{(z+L-1)^{a}}{L}$) for 32-bit hashing values
($z=32$) and $a=1.5$.

##  4 Fast Multilinear with carry-less multiplications

To help support fast operations over binary finite fields ($GF(2^{L})$), AMD
and Intel introduced the Carry-less Multiplication (CLMUL) instruction set
[26]. Given the binary representations of two numbers,
$a=\sum_{i=1}^{L}a_{i}2^{i-1}$ and $b=\sum_{i=1}^{L}b_{i}2^{i-1}$, the carry-
less multiplication is given by $c=\sum_{i=1}^{2L-1}c_{i}2^{i-1}$ where
$c_{i}=\bigoplus_{j=1+i}^{2L-1}a_{j}b_{j-i}$. (We write $a\star b=c$.) If we
represent the two $L$-bit integers $a$ and $b$ as polynomials in GF(2)[$x$],
then the carry-less multiplication is equivalent to the usual polynomial
multiplication:

$\displaystyle\left(\sum_{i=1}^{L}a_{i}x^{i-1}\right)\left(\sum_{i=1}^{L}b_{i}x^{i-1}\right)=\sum_{i=1}^{2L-1}c_{i}2^{i-1}.$

With a fast carry-less computation, we can compute Multilinear efficiently.
Given any irreducible polynomial $p(x)$ of degree $L$, the field
GF(2)[$x$]/$p(x)$ is isomorphic to GF$(2^{L})$. Hence, we want to compute
$h(s)=m_{1}+\sum_{i=1}^{n}m_{i+1}s_{i}$ over GF(2)[$x$]/$p(x)$. (Similarly, we
can use Equation 1 to reduce the number of multiplications by half.) Computing
all multiplications over GF(2)[$x$]/$p(x)$ would still be expensive given fast
carry-less multiplication. Instead, we first compute
$m_{1}+\sum_{i=1}^{n}m_{i+1}s_{i}$ over GF(2)[$x$] and then return the
remainder of the division of the final result by $p(x)$. Indeed, think of the
values $m_{1},m_{2},\ldots$ and $s_{1},s_{2},\ldots$ as polynomials of degree
at most $L$ in GF(2)[$x$]. Each of the $n$ multiplications in GF(2)[$x$] is
equivalent to a carry-less multiplication over $L$-bit integers which results
in a $2L-1$-bit value. Similarly, each of the $n$ additions in GF(2)[$x$] is
an exclusive-or operation. That is, we want to compute the $2L-1$-bit integer

$\displaystyle\bar{h}(s)=m_{1}\oplus\left(\bigoplus_{i=1}^{n}m_{i+1}\star
s_{i}\right).$ (6)

Finally, considering $\bar{h}(s)$ as an element of GF(2)[$x$], noted $q(x)$,
we must compute $q(x)/p(x)$. The remainder (as an $L$-bit integer) is the
final hash value $h(s)$.

If done naively, computing the remainder of the division by an irreducible
polynomial may remain relatively expensive, especially for short strings since
they require few multiplications. A common technique to quickly compute the
remainder is the Barrett reduction algorithm [27]. The adaptation of this
reduction to GF(2)[$x$] is especially convenient [28] when we choose the
irreducible polynomial $p(x)$ such that $\textrm{degree}(p(x)-x^{L})\leq L/2$,
that is, when we can write it as $p(x)=\sum_{i=0}^{\lfloor
L/2\rfloor}a_{i}x_{i}+x^{L}$. (There are such irreducible polynomials for
$L\in\\{1,2,\ldots,400\\}$ [29] and we conjecture that such a polynomial can
be found for any $L$ [30].) In this case, the remainder of $q(x)/p(x)$ is
given by

$\displaystyle((((q\div 2^{L})\star p)\div 2^{L})\star p)\oplus q)\mod 2^{L}$

where $q$ and $p$ are the $2L-1$-bit and $L+1$-bit integers representing
$q(x)$ and $p(x)$. (See B for implementation details.) We expect the two
carry-less multiplications to account for most of the running time of the
reduction.

Unfortunately, in its current Intel implementation, carry-less multiplications
have significantly reduced throughput compared to regular integer
multiplications. Indeed, with pipelining, it is possible to complete one
regular multiplication per cycle, but only one carry-less multiplication every
8 cycles [31]. However, using a result from § 2, we can reduce the number of
multiplications by half if we compute

$\displaystyle\bar{h}(s)=m_{1}\oplus\left(\bigoplus_{i=1}^{n/2}(m_{2i}+s_{2i-1})\star(m_{2i+1}+s_{2i})\right)$

instead. (Henceforth, we refer to last variation as GF Multilinear-HM whereas
we refer to version based on Equation 6 as GF Multilinear.) Yet even a fast
implementation of Barrett reduction will still be much slower than merely
selecting the left-most $L$ bits as in Multilinear.

However, the carry-less approach might still be preferable to the schemes
described in § 3 (e.g., Multilinear) because fewer random bits are required.
Indeed, to generate $L$-bit hash values from $n$-character strings, the carry-
less scheme used $(n+1)L$ random bits, whereas Multilinear requires
$2L+n(2L-1)$ random bits.

##  5 Experiments

Our experiments show the following results:

  * 1.

It is best to implement Multilinear with loop unrolling. With this
optimization, Multilinear is just as fast (on Intel processors) as
Multilinear-HM, even though it has twice the number of multiplications. In
general, processor microarchitectural differences are important in determining
which method is fastest. (§ 5.2)

  * 2.

In the absence of processor support for carry-less multiplication (see § 4),
hashing using Multilinear over binary finite fields is an order of magnitude
slower than Multilinear even when using a highly optimized library. (§ 5.3)

  * 3.

Even with hardware support for carry-less multiplication, hashing using
Multilinear over binary finite fields remains nearly an order of magnitude
slower than Multilinear. (§ 5.4)

  * 4.

Given a 64-bit processor, it is noticeably faster to use a word size of 64
bits even though a larger word size (128 bits) uses fewer random bits (33%
less). Use of multiprecision arithmetic libraries can further reduce the
overhead from accessing random bits, but they are also not competitive with
respect to speed, though they can halve the number of required random bits. (§
5.5)

  * 5.

Multilinear is generally faster than popular string-hashing algorithms. (§
5.6)

###  5.1 Experimental setup

We evaluated the hashing functions on the platforms shown in Table 1. Our
software is freely available online [32]. For Intel and AMD processors, we
used the processor’s time stamp counter (rdtsc instruction [33]) to estimate
the number of cycles required to hash each byte. Unfortunately, the ARM
instruction set does not provide access to such a counter. Hence, for ARM
processors (Apple A4 and Nvidia Tegra), we estimated the number of cycles
required by dividing the wall-clock time by the documented processor clock
rate (1 GHz).

Table 1: Platforms used. Processor | Bits | GCC version | Flags, besides -O3 -funroll-loops
---|---|---|---
64-bit processors
Intel Core 2 Duo | 64 | GNU GCC 4.6.2 | -march=core2 -mno-sse2
Intel Xeon X5260 | 64 | GNU GCC 4.1.2 | -march=nocona
Intel Core i7-860 | 64 | GNU GCC 4.6.2 | -march=corei7 -mno-sse2
Intel Core i7-2600 | 64 | GNU GCC 4.6.2 | -march=corei7 -mno-sse2
Intel Core i7-2677M | 64 | GNU GCC 4.6.2 | -march=corei7 -mno-sse2
AMD Sempron 3500+ | 64 | GNU GCC 4.4.3 | -march=k8 -mno-sse2
AMD V120 | 64 | GNU GCC 4.4.3 | –march=amdfam10 -mno-sse2
32-bit processors
Intel Atom N270 | 32 | GNU GCC 4.5.2 | -march=atom
Apple A4 | 32 | GNU GCC 4.2.1 | -march=armv7
Nvidia Tegra 2 | 32 |  GNU GCC 4.4.3111From the Android NDK, configured for the android-9 platform, and used on a Motorola XOOM. |
VIA Nehemiah | 32 | GNU GCC 3.3.4 | -march=i686

For the 64-bit machines, 64-bit executables were produced and all operations
were executed using 64-bit arithmetic except where noted. All timings were
repeated three times. For the 32-bit processors, 32-bit operations were used
to process 16-bit strings. Therefore, results between 32- and 64-bit
processors are not directly comparable. Good optimization flags were found by
a trial-and-error process. We note that using profile-guided optimizations did
not improve this code any more than simply enabling loop unrolling (-funroll-
loops). With (only) versions 4.4 and higher of GCC, it was important for speed
to forbid use of SSE2 instructions when compiling Multilinear and Multilinear-
HM.

We found that the speed is insensitive to the content of the string: in our
tests we hashed randomly generated strings. We reuse the same string for all
tests. Unless otherwise specified, we hash randomly generated 32-bit strings
of 1024 characters.

In addition to Multilinear and Multilinear-HM we also implemented Multilinear
(2-by-2) which is merely Multilinear with 2-by-2 loop unrolling (see A for
representative C implementations).

Our timings should represent the best possible performance: the performance of
a function may degrade [21] when it is included in an application because of
bandwidth and caching.

###  5.2 Reducing the multiplications or unrolling may fail to improve the
speed

We ran our experiments over both the 32-bit and 64-bit processors. For the
32-bit processors, we generated both 16-bit and 32-bit hash values. Our
experimental results are given in Table 2.

Table 2: Estimated CPU cycles per byte for fast Multilinear hashing  | Multilinear | 2-by-2 | Multilinear-HM
---|---|---|---
64-bit processors and 32-bit hash values and characters
Intel Core 2 Duo | 0.54 | 0.52 | 0.52
Intel Xeon X5260 | 0.50 | 0.50 | 0.50
Intel Core i7-860 | 0.42 | 0.42 | 0.42
Intel Core i7-2600 | 0.34 | 0.27 | 0.28
Intel Core i7-2677M | 0.25 | 0.20 | 0.20
AMD Sempron 3500+ | 0.63 | 0.60 | 0.40
AMD V120 | 0.63 | 0.63 | 0.40
64-bit arithmetic and 32-bit hash values and characters on 32-bit processors
Intel Atom N270 | 4.2 | 4.2 | 3.6
Apple A4 | 3.0 | 2.7 | 3.3
Nvidia Tegra 2 | 3.3 | 3.0 | 4.9
VIA Nehemiah | 12 | 12 | 8.2
32-bit processors and 16-bit hash values and characters
Intel Atom N270 | 2.1 | 3.5 | 2.6
Apple A4 | 1.9 | 2.6 | 1.7
Nvidia Tegra 2 | 1.8 | 2.2 | 1.9
VIA Nehemiah | 5.2 | 5.2 | 3.6

We see that over 64-bit Intel processors ( except for the i7-2600 ), there is
little difference between Multilinear, Multilinear (2-by-2) and Multilinear-
HM, even though Multilinear and Multilinear (2-by-2) have twice the number of
multiplications. We believe that Intel processors use aggressive pipelining
techniques well suited to these computations. On AMD processors, Multilinear-
HM is the clear winner, being at least 33% faster.

For the 32-bit processors, we get different vastly different results depending
on whether we generate 16-bit or 32-bit hash values.

  * 1.

As expected, it is roughly twice as expensive to generate 32-bit hash values
than to generate 16-bit values.

  * 2.

For the VIA processor, Multilinear-HM is 45% faster than Multilinear and
Multilinear (2-by-2). We suspect that the computational cost is tightly tied
to the number of multiplications.

  * 3.

When the 32-bit ARM-based processors generate 32-bit hash values, Multilinear
(2-by-2) is preferable. We are surprised that Multilinear-HM is the worse
choice. We believe that this is related to the presence of a multiply-
accumulate instruction in ARM processors. When generating 16-bit hash values,
Multilinear (2-by-2) becomes the worse choice. There is no significant benefit
to using Multilinear-HM as opposed to Multilinear.

  * 4.

The Intel Atom processor benefits from Multilinear-HM when generating 32-bit
hash value, but Multilinear is preferable to generate 16-bit hash values. As
with the ARM-based processors, Multilinear (2-by-2) is a poor choice for
generating 16-bit hash values.

###  5.3 Binary-finite-field libraries are not competitive

We obtained the $\texttt{mp}\mathbb{F}_{b}$ library from INRIA. This code is
reported [34] to be generally faster than popular alternatives such as NTL and
Zen, and our own tests found it to be more than twice as fast as Plank’s
library [35].

We computed Multilinear in $GF(2^{32})$, using the version with half the
number of multiplications (see Equation 1) because the library does much more
work in multiplication than addition. Even so, on our Core 2 Duo, hashing
32-bit strings of 1024 characters was an order of magnitude slower than
Multilinear: averaged over a million attempts, the code using
$\texttt{mp}\mathbb{F}_{b}$ required an average of 7.69 $\mu s$ per string,
compared with 0.78 $\mu s$ for Multilinear. While our implementation of
Multilinear uses twice as many random bits as Multilinear in $GF(2^{32})$,
this gain is offset by the memory usage of the finite-field library.

###  5.4 Hardware-supported carry-less multiplications are not fast enough

Intel reports a throughput of one carry-less product every 8 cycles [31] on a
processor such as the Intel Core i7-2600. Consider GF Multilinear-MH: it uses
one carry-less multiplication for every two 32-bit characters. Hence, it
requires at least 4 cycles to process each character. Hence, in the best
scenario possible, GF Multilinear-MH will be four times slower than
Multilinear-MH which requires only 1.1 cycles per 32-bit character ( 0.28
cycle per byte).

To assess the actual performance, we implemented both GF Multilinear and GF
Multilinear-MH in C (§ B). Of the processors we tested, only the i7-2600 has
support for the CLMUL instruction set. If we use the flags -O3 -funroll-loops
-Wall -maes -msse4 -mpclmul, we get 12.5 CPU cycles per 32-byte character with
GF Multilinear and only 7.2 CPU cycles with GF Multilinear-MH. We might be
able to improve our implementation: e.g., we expect that much time is spent
loading data into XMM registers. However, the throughput of the carry-less
multiplication limits the character throughput of GF Multilinear and GF
Multilinear-MH to 8 and 4 cycles. On the bright side, GF Multilinear and GF
Multilinear-MH require half the number of random bits.

###  5.5 The sweet-spot for multiprecision arithmetic is not sweet enough

To implement the techniques of § 3.2, we used the GMP library [36] version
5.0.2 to implement Multilinear (2-by-2). As usual, we are hashing 4 kB of
data, though data to be hashed are read in large chunks (up to 2048 bits). The
hash output is always 32 bits ($z=32$). Results show a benefit as the chunk
size $L$ goes from 32 to 512 bits, but thereafter the situation degrades. See
Fig. 3. In the best case, using 512-bit arithmetic, we require almost 13
$\mu$s per string on the Core 2 Duo platform. For comparison, we find that the
fewest random bits would be needed when $L=1024$ (§ 3.2). As expected, the
running time is minimized for a lower value of $L$ to account for the
superlinear running cost of multiplications.

Unfortunately, we can do 12 times better without the GMP library (0.78 $\mu s$
for 64-bit Multilinear) so it is not practical to use 512-bit arithmetic, even
though it uses fewer random bits (nearly half as many).

Figure 3:  Microseconds to hash 4 kB using various word sizes and GMP.

As a lightweight alternative to a multiprecision library, we experimented with
the __uint128 type provided as a GCC extension for 64-bit machines. We used
128-bit random numbers and processed three 32-bit words with each 128-bit
operation. Since __uint128 multiplications are more expensive than __uint128
additions, we tested the Multilinear-HM scheme. On our Core 2 Duo machine, the
result was 38% slower than Multilinear (2-by-2) using 64-bit operations. This
poor results is mitigated by the fact that we use 128 random bits per 96 input
bits, versus 64 random bits per 32 input bits (a saving of nearly 33% for long
strings). Investigation using hardware performance counters showed many
“unaligned loads” from retrieving 128-bit quantities when we step through
memory with 96-bit steps. To reduce this, we tried processing only two 32-bit
words with each 128-bit operation, since we retrieved aligned 64-bit
quantities. However, the result was 61% slower than Multilinear (2-by-2) using
64-bit operations.

###  5.6 Strongly universal hashing is inexpensive?

In a survey, Thorup [1] concluded that strongly universal hash families are
just as efficient, or even more efficient, than popular hash functions with
weaker theoretical guarantees. However, he only considered 32-bit integer
inputs. We consider strings.

In Table 2, we compare the fastest Multilinear (Multilinear-HM) with two non-
universal fast 32-bit string hash functions, Rabin-Karp [37] and SAX [38].
(They are similar to hash functions found in programming languages such as
Java or Perl.) Even though these functions were designed for speed and lack
strong theoretical guarantees, they are far slower than Multilinear on desktop
processors (AMD and Intel). Only for ARM processors (Apple A4 and Nvidia Tegra
2) with 32-bit hash values are they much faster. We suspect that this good
result on ARM processors is due to the multiply-accumulate instruction.
Clearly, such a multiply-accumulate operation greatly benefits simple hashing
functions such as Rabin-Karp and SAX.

Table 3: A comparison of estimated CPU cycles per byte between fast Multilinear hashing and common hash functions  | Rabin-Karp | SAX | best Multilinear
---|---|---|---
32-bit hash values and characters on 64-bit processors
Intel Core 2 Duo | 1.3 | 1.3 | 0.52
Intel Xeon X5260 | 1.4 | 1.6 | 0.50
Intel Core i7-860 | 1.4 | 1.6 | 0.42
Intel Core i7-2600 | 0.89 | 1.1 | 0.27
Intel Core i7-2677M | 0.64 | 0.82 | 0.20
AMD Sempron 3500+ | 1.0 | 1.5 | 0.40
AMD V120 | 1.0 | 1.5 | 0.40
32-bit hash values and characters on 32-bit processors
Intel Atom N270 | 1.1 | 2.0 | 4.2
Apple A4 | 0.88 | 1.2 | 2.7
Nvidia Tegra 2 | 0.85 | 1.2 | 3.0
VIA Nehemiah | 2.0 | 3.0 | 8.2
16-bit hash values and characters on 32-bit processors
Intel Atom N270 | 2.1 | 4.1 | 2.2
Apple A4 | 1.8 | 2.1 | 1.8
Nvidia Tegra 2 | 1.6 | 2.4 | 1.7
VIA Nehemiah | 5.0 | 6.6 | 3.6

Crosby and Wallach [9] showed that almost universal hashing could be as fast
as common deterministic hash functions. One of their most competitive almost
universal schemes is due to Black et al. [17]. Their fast family of hash
functions is called NH:

$\displaystyle h(s)=\sum_{i=1}^{n/2}(m_{2i-1}+s_{2i-1}\mod
{2^{L/2}})(m_{2i}+s_{2i}\mod {2^{L/2}})\mod{2^{L}}.$

NH is almost universal over fixed-length strings, or over variable-length
strings that do not end with the zero character; we can apply it to strings
having odd length by appending a character with value zero. It fails to be
uniform: the value

$\displaystyle(m_{1}+s_{1}\mod {2^{L/2}})(m_{2}+s_{2}\mod {2^{L/2}})$

is zero whenever either $m_{1}+s_{1}\mod {2^{L/2}}$ or $m_{2}+s_{2}\mod
{2^{L/2}}$ is zero, which occurs with probability
$\frac{2^{L/2+1}-1}{2^{L}}>\frac{1}{2^{L}}$ over all possible values of
$m_{1},m_{2}$. Moreover, the least significant bits may fail to be almost
universal: e.g., for $L=6$, there are 96 pairs of distinct strings colliding
with probability 1 over the least two significant bits. When processing 32-bit
characters, it generates 64-bit hash values with collision probability of
$1/2^{32}$. Hence, in our tests over 32-bit characters, NH generates 64-bit
hash values whereas the Multilinear families generate 32-bit hash values, but
both have a collision probability bounded by $1/2^{32}$. Thus, while NH saves
memory because it uses nearly half the number of random bits compared to our
fast Multilinear families, Multilinear families may save memory in a system
that stores hash values because their hash values have half the number of
bits. Table 4 shows that the 64-bit NH on 64-bit processors runs at about the
same speed as the best Multilinear on most processors. Only on some Intel Core
i7 processors (2600 and 2677M), NH’s running time is 60% of Multilinear when
we enable SSE support. In other words, sacrificing theoretical guarantees does
not always translate into better speed.

Table 4: A comparison of estimated CPU cycles per byte between fast Multilinear hashing and the almost universal hash function NH from Black et al. [17] for 32-bit hash values using 64-bit arithmetic. When running NH tests, we remove the -mno-sse2 flag where it is present for better results.  | NH [17] | best Multilinear
---|---|---
Intel Core 2 Duo | 0.53 | 0.52
Intel Xeon X5260 | 0.50 | 0.50
Intel Core i7-860 | 0.42 | 0.42
Intel Core i7-2600 | 0.16222We use the -march=corei7-avx flag for best results. | 0.27
Intel Core i7-2677M | 0.12 | 0.20
AMD Sempron 3500+ | 0.38 | 0.40
AMD V120 | 0.38 | 0.40

Overall, these numbers indicate that strongly universal string hashing is
computationally inexpensive on most Intel and AMD processors. To gain good
results with the various 64-bit processors, we recommend Multilinear-HM.
Unfortunately—over long strings—strongly universal hashing requires many
random numbers. Generating and storing these random numbers is the main
difficulty. Whether this is a problem depends on the memory available, the CPU
cache, the application workload and the length of the strings. (Intel
researchers reported the generation of true random numbers in hardware at high
speed (4 Gbps) [39].) In practice, unexpectedly long strings may require the
generation of new random numbers while hashing a given string [9]. This
overhead should be relatively inexpensive if we know the length of each string
before we process it.

##  6 Conclusion

Over moderately long 32-bit strings ($\approx$1024 characters), current
desktop processors can achieve strongly universal hashing with no more than
0.5 CPU cycle per byte, and sometimes as little as 0.2 CPU cycle per byte.
Meanwhile, at least twice as many cycles are required for Rabin-Karp hashing
even though it is not even universal.

While it uses half the number of multiplications, we have found that
Multilinear-HM is often no faster than Multilinear on Intel processors.
Clearly, Intel’s pipelining architecture has some benefits.

For AMD processors, Multilinear-HM was faster ($\approx$ 33%), as expected
because it uses fewer multiplications. Yet another alternative, Multilinear
(2-by-2), was slightly faster ($\approx$ 15%) for 32-bit hashing on the mobile
ARM-based processors even though it requires twice as many multiplication as
Multilinear-HM. These mobile ARM-based processors also computed 32-bit Rabin-
Karp hashing with fewer cycles per byte than many desktop processors. We
believe that this is related to the presence of a multiply-accumulate in the
ARM instruction set.

## Acknowledgments

The authors are grateful for related online discussions with P. L. Bannister,
V. Khare, V. Venugopal, J. S. Culpepper. This work is supported by NSERC grant
261437.

## References

  * Thorup [2000] M. Thorup,  Even strongly universal hashing is pretty fast,  in: Proc. 11th ACM-SIAM Symp. on Discrete algorithms, SODA ’00, Society for Industrial and Applied Mathematics, 2000, pp. 496–497.
  * Cormode and Hadjieleftheriou [2010] G. Cormode, M. Hadjieleftheriou,  Methods for finding frequent items in data streams,  VLDB J. 19 (2010) 3–20.
  * Gibbons and Tirthapura [2001] P. B. Gibbons, S. Tirthapura,  Estimating simple functions on the union of data streams,  in: Proc. 13h ACM Symp. on Parallel algorithms and architectures, SPAA ’01, ACM, 2001, pp. 281–291.
  * Bar-Yossef et al. [2002] Z. Bar-Yossef, T. S. Jayram, R. Kumar, D. Sivakumar, L. Trevisan,  Counting distinct elements in a data stream,  in: Proc. 6th Int. Workshop on Randomization and Approximation Techniques, RANDOM ’02, Springer-Verlag, 2002, pp. 1–10.
  * Pagh and Rodler [2004] R. Pagh, F. Rodler,  Cuckoo hashing,  J. Algorithms 51 (2004) 122–144.
  * Dietzfelbinger and Schellbach [2009] M. Dietzfelbinger, U. Schellbach,  On risks of using cuckoo hashing with simple universal hash classes,  in: Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, SODA ’09, Society for Industrial and Applied Mathematics, 2009, pp. 795–804.
  * Carter and Wegman [1979] L. Carter, M. N. Wegman,  Universal classes of hash functions,  J. Comput. Syst. Sci. 18 (1979) 143–154.
  * Wegman and Carter [1981] M. Wegman, L. Carter,  New hash functions and their use in authentication and set equality,  J. Comput. Syst. Sci. 22 (1981) 265–279.
  * Crosby and Wallach [2003] S. A. Crosby, D. S. Wallach,  Denial of service via algorithmic complexity attacks,  in: Proc. 12th conference on USENIX Security Symposium - Volume 12, USENIX, 2003, pp. 3–3. See also http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf, last checked 2012-01-12.
  * Klink and WäldeAsanovic [2011] A. Klink, J. WäldeAsanovic, Denial of Service through hash table multi-collisions, Technical Report oCERT-2011-003, Open Source Computer Security Incident Response Team, 2011.
  * Zobrist [1970] A. L. Zobrist, A New Hashing Method With Application for Game Playing, Technical Report 88, Computer Sciences Department, University of Wisconsin, 1970\. http://www.cs.wisc.edu/techreports/viewreport.php?report=88, last checked on 2011-11-25.
  * Zobrist [1990] A. Zobrist,  A new hashing method with application for game playing,  ICCA J. 13 (1990) 69–73.
  * Dietzfelbinger [1996] M. Dietzfelbinger,  Universal hashing and k-wise independent random variables via integer arithmetic without primes,  in: Proc. 13th Symp. on Theoretical Aspects of Computer Science, STACS ’96, Springer-Verlag, 1996, pp. 569–580.
  * Etzel et al. [1999] M. Etzel, S. Patel, Z. Ramzan,  Square hash: Fast message authenication via optimized universal hash functions,  in: Proc. 19th Int. Cryptology Conf. on Advances in Cryptology, CRYPTO ’99, Springer-Verlag, 1999, pp. 234–251.
  * Stinson [1994] D. R. Stinson,  Universal hashing and authentication codes,  Des. Codes Cryptogr. 4 (1994) 369–380.
  * Motzkin [1955] T. S. Motzkin,  Evaluation of polynomials and evaluation of rational functions,  Bull. Amer. Math. Soc. 61 (1955) 163.
  * Black et al. [1999] J. Black, S. Halevi, H. Krawczyk, T. Krovetz, P. Rogaway,  UMAC: Fast and secure message authentication,  in: Proc. 19th Int. Cryptology Conf. on Advances in Cryptology, CRYPTO ’99, Springer-Verlag, 1999, pp. 216–233.
  * Winograd [1970] S. Winograd,  On the number of multiplications necessary to compute certain functions,  Comm. Pure Appl. Math 23 (1970) 165–179.
  * Brent et al. [2008] R. P. Brent, P. Gaudry, E. Thomé, P. Zimmermann,  Faster multiplication in $GF(2)[x]$,  in: Proc. 8th Int. Conf. on Algorithmic Number Theory, ANTS-VIII’08, Springer-Verlag, 2008, pp. 153–166.
  * Lemire and Kaser [2010] D. Lemire, O. Kaser,  Recursive n-gram hashing is pairwise independent, at best,  Comput. Speech Lang. 24 (2010) 698–710.
  * Greenan et al. [2007] K. M. Greenan, E. L. Miller, T. Schwarz, Analysis and Construction of Galois Fields for Efficient Storage Reliability, Technical Report UCSC-SSRC-07-09, University of California, Santa Cruz, 2007.
  * Krovetz and Rogaway [2001] T. Krovetz, P. Rogaway,  Fast universal hashing with small keys and no preprocessing: The PolyR construction,  Lecture Notes in Computer Science 2015 (2001) 73–89.
  * Cormen et al. [2009] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, Third Edition, The MIT Press, 3rd edition, 2009\.
  * Pǎtraşcu and Thorup [2011] M. Pǎtraşcu, M. Thorup,  The power of simple tabulation hashing,  in: Proc. 43rd ACM Symp. on Theory of computing, STOC ’11, ACM, 2011, pp. 1–10.
  * Thorup [2009] M. Thorup,  String hashing for linear probing,  in: Proc. 20th ACM-SIAM Symp. on Discrete Algorithms, SODA ’09, Society for Industrial and Applied Mathematics, 2009, pp. 655–664.
  * Gueron and Kounavis [2010] S. Gueron, M. Kounavis,  Efficient implementation of the Galois Counter Mode using a carry-less multiplier and a fast reduction algorithm,  Inform. Process. Lett. 110 (2010) 549 – 553.
  * Barrett [1987] P. Barrett,  Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor,  in: Proc. Advances in Cryptology, CRYPTO ’86, Springer-Verlag, 1987, pp. 311–323.
  * Knežević et al. [2008] M. Knežević, K. Sakiyama, J. Fan, I. Verbauwhede,  Modular reduction in $GF(2^{n})$ without pre-computational phase,  in: Proc. 2nd Int. Workshop on Arithmetic of Finite Fields, WAIFI ’08, Springer-Verlag, 2008, pp. 77–87.
  * Arndt [2003] J. Arndt, Minimal weight primitive polynomials over $GF(2)$, http://www.jjj.de/mathdata/minweight-primpoly.txt, last checked on 2011-11-25, 2003.
  * Cohen [2004] S. Cohen,  Primitive polynomials over small fields,  in: Finite Fields and Applications, volume 2948 of LNCS, Springer Berlin / Heidelberg, 2004, pp. 65–75.
  * Intel Corporation [2011] Intel Corporation, Intel 64 and IA-32 architectures optimization reference manual, 2011.
  * Kaser and Lemire [2012] O. Kaser, D. Lemire, A variable-length string hashing library in C/C++, http://code.google.com/p/variablelengthstringhashing/, last checked on 2012-02-06, 2012.
  * Paoloni [2010] G. Paoloni, How to benchmark code execution times on Intel IA-32 and IA-64 instruction set architectures, White paper, Intel Corporation, 2010.
  * Gaudry and Thomé [2007] P. Gaudry, E. Thomé,  The $\texttt{mp}\mathbb{F}_{b}$ library and implementing curve-based key exchanges,  in: SPEED: Software Performance Enhancement for Encryption and Decryption, ECRYPT, 2007, pp. 49–64.
  * Plank [2007] J. S. Plank, Fast Galois field arithmetic library in C/C++, Technical Report UT-CS-07-593, University of Tennessee, 2007\. http://web.eecs.utk.edu/~plank/plank/papers/CS-07-593.html, last checked on 2011-11-25.
  * Free Software Foundation [2011] Free Software Foundation, The GNU MP Bignum library, http://gmplib.org, last checked on 2011-11-25, 2011.
  * Karp and Rabin [1987] R. M. Karp, M. O. Rabin,  Efficient randomized pattern-matching algorithms,  IBM J. of Res. Dev. 31 (1987) 249–260.
  * Ramakrishna and Zobel [1997] M. V. Ramakrishna, J. Zobel,  Performance in practice of string hashing functions,  in: Proc. Int. Conf. on Database Systems for Advanced Applications, World Scientific Press, 1997\.
  * Srinivasan et al. [2009] S. Srinivasan, S. Mathew, V. Erraguntla, R. Krishnamurthy,  A 4 Gbps 0.57 pJ/bit process-voltage-temperature variation tolerant all-digital true random number generator in 45 nm CMOS,  in: Proc. 22nd Int. Conf. on VLSI Design, IEEE Computer Society, 2009, pp. 301–306.

##  Appendix A Implementations in C

We implemented the following hash functions:

  * 1.

Multilinear: $h(s)=m_{1}+\sum_{i=1}^{n}m_{i+1}s_{i}$

  * 2.

Multilinear (2-by-2):
$h(s)=m_{1}+\sum_{i=1}^{n/2}m_{2i}s_{2i-1}+s_{2i}m_{2i+1}$

  * 3.

Multilinear-HM:
$h(s)=m_{1}+\sum_{i=1}^{n/2}(m_{2i}+s_{2i-1})(s_{2i}+m_{2i+1})$

For simplicity we assume that the number of characters ($n$) is even.
Following a common convention, we write the unsigned 32-bit and 64-bit integer
data types as uint32 and uint64. The variable p is a pointer to the initial
value of the string whereas endp is a pointer to the location right after the
last 32-bit character of the _string_. The variable m is a pointer to the
64-bit random numbers. (When using 63-bit random numbers as allowed by Theorem
1, the right shifts should be by 31 instead. In practice, we use 64-bit
numbers.) On some compilers and processors, it was useful to disable SSE2:
under GNU GCC we can achieve this result with function attributes (e.g. by
preceding the function declaration by `__attribute__ ((__target__ ("no-
sse2")))`).

#### Multilinear

⬇

uint32 hash(uint64 * m, uint32 * p, uint32 * endp) {

uint64 sum = *(m++);

for(;p!=endp;++m,++p) {

sum+= *m * *p;

}

return sum>>32;

}

####  Multilinear (2-by-2)

⬇

uint32 hash(uint64 * m, uint32 * p, uint32 * endp) {

uint64 sum = *(m++);

for(; p!= endp; m+=2,p+=2 ) {

sum+= (*m * *p) + (*(m + 1) * *(p+1));

}

return sum>>32;

}

#### Multilinear-HM

⬇

uint32 hash(uint64 * m, uint32 * p, uint32 * endp) {

uint64 sum = *(m++);

for(;p!=endp;m+=2,p+=2 ) {

sum += (*m + *p) * (*(m+1) + *(p+1));

}

return sum>>32;

}

##  Appendix B Implementations with carry-less multiplications

We implemented Multilinear in $GF(2^{32})$ in C using the Carry-less
Multiplication (CLMUL) instruction set [26] supported by recent Intel and AMD
processors. We also implemented the counterpart to Multilinear-HM which
executes half the number of multiplications.

We use the same conventions as in A regarding the variables p and m except
that the later is a pointer to 32-bit random numbers. We wrote our C programs
using SSE intrinsics: they are functions supported by several major compilers
(including GNU GCC, Intel and Microsoft) that generate SIMD instructions.

The Barrett reduction algorithm is adapted from Knežević et al. [28]. The
variable C contains the chosen irreducible polynomial. We initialize it as

C $\displaystyle=$ _mm_set_epi64x(0,1UL\+ (1UL<<2)\+ (1UL<<6)
$\displaystyle\texttt{+~{}(1UL<<7)}\texttt{+~{}(1UL<<32));}.$

#### Barrett reduction

⬇

uint32 barrett( __m128i A) {

__m128i Q1 = _mm_srli_epi64 (A, n);

__m128i Q2 = _mm_clmulepi64_si128( Q1, C, 0x00);

__m128i Q3 = _mm_srli_epi64 (Q2, n);

__m128i f = _mm_xor_si128 (A, _mm_clmulepi64_si128( Q3, C, 0x00));

return _mm_cvtsi128_si64(f) ;

}

#### GF Multilinear

⬇

uint32 hash(uint32 * m, uint32 * p, uint32 * endp) {

__m128i sum = _mm_set_epi64x(0,*(m++));

for(;p!=endp;++m,++p ) {

__m128i t = _mm_set_epi64x(*m,*p);

__m128i c = _mm_clmulepi64_si128( t, t, 0x10);

sum = _mm_xor_si128 (c,sum);

}

return barret(sum);

}

#### GF Multilinear-MH

⬇

uint32 hash(uint32 * m, uint32 * p, uint32 * endp) {

__m128i sum = _mm_set_epi64x(0,*(m++));

for(;p!=endp;m+=2,p+=2 ) {

__m128i t1 = _mm_set_epi64x(*m,*(m+1));

__m128i t2 = _mm_set_epi64x(*p,*(p+1));

__m128i t = _mm_xor_si128(t1,t2);

__m128i c = _mm_clmulepi64_si128( t, t, 0x10);

sum = _mm_xor_si128 (c,sum);

}

return barret(sum);

}