Explain the fast Walsh–Hadamard transform in simple steps or pseudocode

I've read that the fast Walsh–Hadamard transform is a way to efficiently calculate the linearity/non-linearity of an S-box. Can I get a description of it in simple steps or pseudocode that is restricted to simpler notation and terminology?

• Maybe you could take this inquiry as motivation to study and figure out how to work with linear algebra in finite fields? – Squeamish Ossifrage Dec 29 '17 at 4:18

The fast Walsh-Hadamard transform algorithm generally applies to Hadamard matrices $H_n$ which are of dimension $2^n\times 2^n, n\geq 1$. Using row and column transpositions, $H_n$ can be arranged so that it is of the form $$H_n = \left[\begin{matrix}H_{n-1}& H_{n-1}\\H_{n-1}& -H_{n-1}\end{matrix}\right].$$ As a special case, note that $$H_1 = \left[\begin{matrix}+1& +1\\+1& -1\end{matrix}\right].$$

Now, the Hadamard transform of the (row) vector $\mathbf x$ of length $2^n$ is the row vector $\mathbf xH$ where, if we partition $\mathbf x$ as the concatenation of $2^{n-1}$-vectors $\mathbf x_L$ and $\mathbf x_R$ $\bigr($that is, $\mathbf x = \big[\mathbf x_L, \mathbf x_R\big]\bigr)$, then we can write $$\mathbf xH = \big[\mathbf x_L, \mathbf x_R\big]\left[\begin{matrix}H_{n-1}& H_{n-1}\\H_{n-1}& -H_{n-1}\end{matrix}\right] = \big[\mathbf x_LH_{n-1}+\mathbf x_RH_{n-1}, \mathbf x_LH_{n-1} - \mathbf x_RH_{n-1}\big].$$ This suggests that if we have already computed $\mathbf x_LH_{n-1}$ and $\mathbf x_RH_{n-1}$, we can compute $\mathbf xH$ in $2^n$ more additions/subtractions. So, we can proceed recursively, partitioning $\mathbf x_L$ into $\big[\mathbf x_{LL}, \mathbf x_{LR}\big]$ and $\mathbf x_R$ into $\big[\mathbf x_{RL}, \mathbf x_{RR}\big]$, and repeat the above calculations with shorter vectors,....

Pseudocode would be something like

recursive function FHT$(\mathbf x)$
begin
partition $\mathbf x$ into two equal-length parts $\mathbf x_L$ and $\mathbf x_R$
$\mathbf y_L$ = FHT$(\mathbf x_L)$; $\mathbf y_R$ = FHT$(\mathbf x_R)$
return $\big[\mathbf y_L+\mathbf y_R,\mathbf y_L-\mathbf y_R\big]$.
end

The total number of additions/subtractions is $n2^n$; there are no multiplications needed

• I probably should have qualified "simple" to exclude matrices. – Melab Dec 22 '17 at 5:53
• @Melab OK. Don’t read the first part of my answer (everything before the sentence beginning with “Pseudocode”). What is left has no mention of matrices whatsoever. Oh, you don’t understand vectors or arrays or the concept of dividing an array into a left half and a right half either? Well, in that case, ignore my entire answer and wait for someone else to give you the answer in terms that suit you. – Dilip Sarwate Dec 22 '17 at 15:33
• Sorry if I offended you. I understand arrays. I also understand matrices, but not the ways they are typically used in cryptography. – Melab Dec 22 '17 at 18:07
• Is this the same as only evaluating for equal input and output masks? – Melab Dec 22 '17 at 19:29