Может ли существовать инъективная функция, которая отображает большой набор целых чисел в меньший набор, будучи «осведомленной о столкновениях»

Рассмотрим два набора:

«Большой набор» содержит все целые числа между $0$ и $2^{160}$ ровно один раз.

«Малый набор» содержит все целые числа между $0$ и $2^{32}$ ровно один раз.

Учитывая, что количество элементов в «большом наборе» больше, чем в «малом наборе», не может быть инъективной функции. $f(n_b) = n_s$ сопоставление любого ввода, являющегося членом «большого набора» $n_b$ к выходу, который является членом «небольшого набора» $n_s$. Если эта функция $ф$ существовало, это был бы ответ на вопросы.

По практическим соображениям мы предполагаем, что все еще может существовать конструкция/алгоритм с практической функцией $f_p$ где результаты всех входов в $f_p(n_b)$ являются членами «малого множества» и каждый $n_b$ указывает на отчетливое $n_s$.

Из-за отсутствия понимания криптографических концепций я назову это свойство «осведомленным о коллизиях». Например. реализовать эту конструкцию, предполагая емкость хранилища размером $2^{256}$ (256-битное целое без знака), есть ли функция $f_p$ или алгоритм, который для любого $n_b$ либо возвращает «столкновение» («с учетом столкновений»), либо отдельный член $n_s$?

Как насчет:- $$ n_s = \mathcal{H}(n_b) \& (2^{32} - 1) $$ куда $n_b \в N_b$, и т.д? $\mathcal{Н}$ может быть хеш-функцией по вашему выбору. Поскольку это крипто-сайт, я предлагаю SHA-256. $\&$ означает побитовое И, но может быть заменено правым или левым сдвигом соответствующего количества битов (128 в случае SHA-256). Возможно, слишком медленно (?)

Криптографические хэш-функции сюръективный, что означает, что их выходы иногда сталкиваются. Эта частота столкновений значительно увеличится, если вы урежете $\mathcal{Н}$ до 32 бит. Тем более будет эффект от принцип голубиной дыры. Итак, вы установили $N_b$ заполнение равномерно распределенными числами, давая $n_b \до n_s$ с домена на кодомен.

Не знаю насчет Ethereum, но 160 подозрительно похоже на результат SHA-1. Если это так, просто усеките учетную запись/адрес до 32 бит, поскольку они уже распределены равномерно.

Если я понимаю требования, то, о чем вы просите, не является «функцией» в соответствии с обычным определением. Похоже, вы хотите немного $f$ что при заданной последовательности входных данных ${x_i}$ вернет либо детерминированное значение $y_i$ или символ ошибки, если он уже вернулся $y_i$. Но предположим $x_k$ это первый ввод, возвращающий ошибку. Что должно произойти, если вы позвоните $f$ с последовательностью, начинающейся с $x_k$? Я думаю, вы бы хотели, чтобы он не возвращал ошибку, поэтому значение $f(x_k)$ не является четко определенным.

Чтобы разрешить это математически, нужно изменить определение $f$ принять последовательность. Но на практике это, вероятно, означает, что ваша система записывает все входные данные, которые были вызваны. И вы обнаружите, что если вы это сделаете, вы можете просто вернуться $0,...,n-1$ для первых отдельных входов и ошибок для всего последующего.