ウォルシュ–アダマール変換
すべての線形関数との相関を一度に計算する高速な変換。線形解読法の主力道具である。
n入力のブール関数は2n個の値のベクトルで与えられる。この変換は同じ大きさのベクトルを返し、各要素が関数と特定の線形関数との相関の強さを示す。素直に計算すると22n回の演算が必要だが、FFTによく似た高速版ならn·2n回で済む。
名前はジャック・アダマールとジョセフ・ウォルシュに由来し、二人とも19世紀末から20世紀初頭に直交系を研究した。S-boxの解析では、最も強い線形近似を探す日常的な道具である。これ無しで計算した経験のある人なら、この変換が存在する理由を身をもって知っている。