Универсальное и идеальное хеширование

[Kib0rg]

Это явно подкорректированный машинный перевод, но почему не указан источник?
Часть формул превратилась в кашу, где-то верхний индекс съехал и 128^80 превратилось в 12880, текст не вычитан… Конечно, я мог бы всё это и в личку написать, но хочется, чтобы авторы таких переводов с бОльшим уважением относились к читателям и приводили текст в порядок перед публикацией.

[maxzhurkin]

А что, если автор — тоже машина?

[MaxRokatansky]

Ага, робокоп)

[White_farz]

Вопрос: зачем использовать хеш-функцию...

Хеш-функции находят множество применений, но существенно более вычислительноёмка (а значит её и следует поручать вычислительным машинам) обратная задача — по заданным свойствам хеша (например, хеш должен быть меньше target) определить исходные данные (или хотя бы какую-то их часть: nonce).
Пример: «фермы» по майнингу биткоинов переводят мегаджоули энергии на то, чтобы подобрать к заголовку блока такие 32 бита, чтоб его хеш (точнее sha256(sha256(BlockHeader) ) стал приемлемым, чтоб стать транзакцией в цепочке блоков (блокчейне).
В изучении путей решения подобных задач, как мне представляется, уже не обойтись без серьёзного понимания вероятностных мер и применения так называемых «многозначных» логик (хочу напомнить, что первоисследователем комплексной логики в нашей стране был Александр Александрович Зиновьев).
Например, nckma, в своей публикации «Вероятностный метод майнинга Bitcoin»
предлагает вместо 32 битных DWORD использовать для каждого бита число с плавающей точкой. Тогда логические и арифметические операции могут нести смысл операций над возможностями осуществления событий. Алгоритм, построенный на такой логике, может моделировать те или иные свойства «матрицы вероятностных предопределённостей».
Так операция
Not(x) выражается в виде 1.0 - x,
And(x,y) — в виде x*y,
Or(x,y) = x + y - x*y, и т.д.
Хочу обратить внимание присутствующих на трудности при реализации вероятностной операции XOr.
Легко убедиться, что
~(x & y) & (x | y) ==
(~x & y) | (x &~y) == x^y.
Между тем, полиномы
Xa(x,y) = (1 - x * y) * (x + y - x * y) == x*x*y*y-x*y*y-x*x*y - x*y+y+x
и
Xe(x,y) = (1-x)*y+(1-y)*x-(1-y)*x*(1-x)*y ==-x*x*y*y+x*y*y+x*x*y-3*x*y+y+x
различны.
Легко заметить, что разница этих полиномов
Xa(x,y) - Xe(x,y) = 2*(x-1)*x*(y-1)*y
на прямых x=0, y=0, x=1, y=1 обращается в ноль,
и достигает максимума 0.125 в точке (0.5, 0.5).
Не здесь ли скрывается причина, замеченного автором упомянутой публикации «дыхания ветерка»?
Предлагается в качестве вероятностного XOr использовать среднее арифметическое этих полиномов:
Xo(x,y) = ( Xa(x,y) + Xe(x,y) ) / 2 == x + y - 2*x*y
Обоснование:
Xo(0.5, 0.5) == 0.5,
да и просто красиво.