Walsh–Hadamard-transformen
En snabb transform som räknar ut korrelationen mot alla linjära funktioner samtidigt, och verktyget bakom mycket av linjär kryptoanalys.
En Boolesk funktion med n indata ges som en vektor med 2n värden, och transformen ger ett lika stort svar där varje position beskriver hur väl funktionen korrelerar med en viss linjär funktion. Naivt kostar det 22n operationer. Den snabba varianten, som liknar FFT, klarar det i n·2n.
Namnet kommer från Jacques Hadamard och Joseph Walsh, som båda arbetade med ortogonala system mellan slutet av 1800-talet och början av 1900-talet. I S-box-analys är transformen det vardagliga verktyget för att hitta de starkaste linjära approximationerna. Den som gjort uträkningen utan den vet varför den finns.