Преобразование Уолша — Адамара
Быстрое преобразование, вычисляющее корреляцию сразу со всеми линейными функциями, — рабочая лошадка линейного криптоанализа.
Булева функция от n входов задаётся вектором из 2n значений, а преобразование возвращает вектор того же размера, где каждый элемент показывает, насколько функция коррелирует с одной конкретной линейной функцией. «В лоб» это стоит 22n операций. Быстрый вариант, похожий на БПФ, справляется за n·2n.
Название происходит от Жака Адамара и Джозефа Уолша, оба работали с ортогональными системами между концом XIX и началом XX века. В анализе S-блоков это повседневный инструмент поиска сильнейших линейных приближений. Кто считал это без него, прекрасно знает, зачем он нужен.