Хороший результат. Значит, есть определенная зависимость между бент-функциями от N и (N+1) переменных.

Думаю, что представление булевой функции в виде целого числа — довольно тривиальная процедура, любому математику она понятна, а для не-математика… Можно привести картинку с таблицей истинности и превращением ее последнего столбца в двоичный вектор :)

И все же мне было бы интересно поисследовать на кластере не отдельные функции, а блоки замен. У нас со Славой сейчас вырисовывается одна задачка, которую на ПК уже точно не решишь. Можно рассчитывать на Вашу помощь в реализации наших тестов для кластера? Если да, то я подготовлю условие задачи и что требуется найти, какую статистику…

Все бы хорошо, только бент-функции в ГОСТе неприменимы… :)

я думал, что тут может возникнуть не дифференциация (математик)-(не математик), а (программист)-(не программист) :)

Насчёт помощи: постараюсь, но зависит от трудоёмкости. До нового года у меня, наверно, и на свои работы уже почти не будет времени. Потом наверно легче будет. А у Славы это будет тема для диплома? Он этим летом защищаться будет? Если сделаете описание задачи, то можно будет выложить и обсуждать его здесь, если никто из вас не против.

А что там с ГОСТом? Там надо использовать равновесные с высокой нелинейностью? Если так, то могу сказать, что функции с нелинейностью, близкой к максимальной кучкуются вокруг бент-функций. Это я тоже на своих результатах заметил.

Ну для не-программиста и не-математика, действительно, могут возникнуть трудности :) Именно в этих целях я в дипломе картинку с табличкой рисовал.

Ну, собственно, речь и идет о работе после Нового Года, когда Слава сдаст сессию и сможет полноценно над дипломом работать. Да, у меня диплом будет органичным продолжением моего. Защищается летом.

Хорошо, описание я подготовлю и выложу сюда.

Да, именно равновесные с высокой нелинейностью. Более того, там самостоятельно конструировать имеет смысл только для 4 переменных, а потом уже нужно смотреть, как они влияют на преобразования данных в ходе шифрования… Так что подход немного иной.
То есть задача стоит не сгенерировать высоко нелинейную функцию, а оценить нелинейность функций, описывающих процесс шифрования, при разных значениях элементов ключевой информации.

Думаю, что когда сделаю описание, станет понятнее, о чем речь :)

Хорошо, я и сам собирался начать исследовать распределение по весам и попробовать увязать его с распределением значений нелинейности. Так что совместим полезное с полезным :)

> Да, у меня диплом будет органичным продолжением моего

оговорка по Фрейду, однако :)

Пардон, пальцы за мыслями не успевают :)

Первая цель исследования, указанной в заключении статьи: проверить, входят ли все максимально нелинейные функции в подмножества функций, выбранные описанным образом. Для этого надо вычислить нелинейность 27387136*2^32 булевых функций от 6 переменных.
На момент написания статьи перебор 2^32 функций занимал примерно 2,5 часа. Понятно, что с такой скоростью перебрать 27387136*2^32 > 117*10^15 функций — слишком большая задача даже при одновременном использовании 100/1000/2000 процессорных ядер (примерно столько я и могу использовать). Поэтому я решил взяться за оптимизацию такого перебора, а именно — поискать, что же можно оптимизировать в таких местах как вычисление нелинейности одной функции и перебор подмножества из 2^32 функций (т.к. перебор выполняется именно такими частями).
Удалось в итоге время того же перебора 2^32 функций сократить до 20 минут. Если кому интересно, то могу вкратце описать, за счет чего удалось добиться ускорения.
Однако и этого недостаточно. Я посчитал, что для того, чтобы перебрать столько функций за 2 недели с использованием 1280 процессорных ядер, надо чтобы 2^32 функций перебирались за 1 минуту. Так что следующим моим шагом в этом направлении будет попытка разобраться как же вычислять нелинейность вычислять нелиненйость одной функции с помощью преобразования Уолша-Адамара. Уже немного посмотрел и вроде от одного преобразования в чистом виде большого ускорения, видимо, не получить. Придется смотреть в сторону быстрого преобразования Уолша-Адамара и различных свойств коэффициентов Уолша.

Если можно, опишите в двух словах, за счет чего удалось добиться ускорения в 7-8 раз (с 2,5 ч до 20 мин).
И получилось ли уже что-нибудь с методом Уолша-Адамара?

Мы со своей стороны пока работаем в другом направлении — с маленькими значениями разрядности, но не с отдельными функциями, а с блоками замен, как я описывал в «Задачах для кластерных вычислений».

Так как надо было оптимизировать перебор 2^32 функций, то я экспериментировал на переборе всего множества функций от 5 переменных. Пробовал несколько оптимизаций:

1) изначально у меня проход по всем аффинным функциям был сокращён вдвое за счёт того, что для каждой такой функции есть другая аффинная, которая является обратной (все биты инвертированы). Поэтому при вычислении расстояния до одной афф. функции я тут же без xor'а вычислял расстояние до обратной примерно так:
distance = HammingDistance(...);
min = Math.min(min, distance);
min = Math.min(min, 32-distance);
Я обратил внимание, что в обеих операциях вычисления минимального используется (на запись) переменная min. Поэтому они могут быть выполнены только последовательно. Я стал вычислять расстояние до обратных функций параллельно с использованием отдельной переменной:
min2 = Math.min(min2, 32-distance);
и в конце только один раз делаю сравнение:
min = Math.min(min, min2);
Это сразу ускорило перебор примерно до 30 минут.

2) Говорят, использование математической библиотеки (класса) Math может замедлить выполнение программы (слышал такое про разные языки). Поэтому, если его можно избежать, то лучше не использовать. Я заменил вызовы Math.min() на обычные сравнения. Однако время увеличилось. Так что, видимо, для C# этот класс уже хорошо оптимизирован.

3) Так как цель: проверить сколько максимально нелинейных функций среди определённого множества функций, то собственно точные расстояния можно и не вычислять. Я решил просто проверять является функция максимально линейной или нет.
…
if(distance < maxNLvalue) return false;
…
return true;

maxNLvalue для N=5 — 12, для N=6 — 28.
После этого перебор стал занимать кажется что-то около минуты.
Однако, когда я эти оптимизации переносил в программу перебора множества функций для N=6, то время оказывалось значительно больше. Видимо дело в том, что функция для N=5 занимает 32 бита — и влазит в одно число типа uint. А для N=6 — уже в две таких переменных, и приходится xor'ить уже массивы uint'ов, а потом ещё считать в них кол-во единичных битов. Хоть и небольшие массивы, но видимо это замедляет. Поэтому была придумана такая оптимизация:

3) Как я уже говорил, множества функций, которые перебираются, выглядят следующим образом: [xxxxxxxxh 00000000h]-[xxxxxxxxh ffffffffh]. Где xxxxxxxxh — некая функция от 5-ти переменных. То есть при переборе 2^32 функций старшая часть всех функций совпадает. Множество аффинных функций тоже совпадает. Получается xor'ы старших половин всех таких функций со старшими половинами афф. функций будут совпадать. Поэтому я перед перебором предвычисляю эти расстояния (для старших половин функций). Получается массив 2^N чисел. А при вычислении нелинейности каждой функции я вычисляю уже только расстояния между младшими половинами и добавляю соответствующие известные значения расстояний для старших частей.
После этого время перебора 2^32 функций от 6 переменных стало примерно 20 минут. Пока рекорд.

Спасибо за подробные комментарии.
Первым приемом я, разумеется, тоже пользовался в реализации на ПЭВМ, он очевиден.
А вот приемы 3 и 4 не такие тривиальные. В этом смысле Ваша работе имеет ценность не только как исследование нелинейности функций, но и как нахождение способов оптимизации параллельных вычислений с булевыми функциями :)

Про Уолша-Адамара нашёл пару книг с описанием. Одну на русском, одну на английском. Пока не разобрался.