Có thể có một hàm nội suy ánh xạ một tập hợp số nguyên lớn thành một tập hợp nhỏ hơn trong khi "nhận biết va chạm" không

Xét hai tập hợp:

"Tập hợp lớn" chứa tất cả các số nguyên giữa $0$ và $2^{160}$ chính xác một lần.

"Tập hợp nhỏ" chứa tất cả các số nguyên giữa $0$ và $2^{32}$ chính xác một lần.

Cho rằng số lượng phần tử trong "tập hợp lớn" nhiều hơn số phần tử trong "tập hợp nhỏ", không thể tồn tại hàm nội xạ $f(n_b) = n_s$ ánh xạ bất kỳ đầu vào nào là thành viên của "tập hợp lớn" $n_b$ đến đầu ra là thành viên của "tập hợp nhỏ" $n_s$. Nếu chức năng đó $f$ tồn tại, nó sẽ là câu trả lời của câu hỏi.

Vì những lý do thực tế, chúng tôi giả định rằng vẫn có thể có một cấu trúc/thuật toán có chức năng thực tế $f_p$ trong đó kết quả của tất cả các đầu vào vào $f_p(n_b)$ là một thành viên của "tập hợp nhỏ" và mỗi $n_b$ chỉ ra một sự khác biệt $n_s$.

Đối với sự thiếu hiểu biết về các khái niệm mật mã, tôi sẽ gọi thuộc tính này là "nhận biết va chạm". Ví dụ. để thực hiện việc xây dựng này, giả sử dung lượng lưu trữ có kích thước bằng $2^{256}$ (số nguyên không dấu 256 bit), có chức năng nào không $f_p$ hoặc một thuật toán cho bất kỳ $n_b$ hoặc trả về một "va chạm" ("nhận biết va chạm") hoặc một thành viên riêng biệt của $n_s$?

Thế còn:- $$ n_s = \mathcal{H}(n_b) \& (2^{32} - 1) $$ ở đâu $n_b \in N_b$, vân vân? $\mathcal{H}$ có thể là một hàm băm do bạn chọn. Vì đây là một trang web về tiền điện tử nên tôi đề xuất SHA-256. $\&$ có nghĩa là bit AND, nhưng có thể được thay thế bằng dịch chuyển phải hoặc trái của số bit thích hợp (128 trong trường hợp của SHA-256). Có lẽ quá chậm (?)

Hàm băm mật mã là surjective, nghĩa là đầu ra của chúng thỉnh thoảng xung đột. Tỷ lệ va chạm đó sẽ tăng lên rất nhiều nếu bạn cắt bớt $\mathcal{H}$ đến 32 bit. Thậm chí nhiều hơn như vậy sẽ ảnh hưởng của nguyên tắc lỗ chim bồ câu. Vì vậy, bạn sẽ có thiết lập $N_b$ lấp đầy với các số được phân phối đồng đều, cho $n_b \đến n_s$ từ miền này sang tên miền khác.

Tôi không biết về Ethereum, nhưng 160 trông giống như đầu ra của SHA-1 một cách đáng ngờ. Nếu vậy, chỉ cần cắt ngắn tài khoản/địa chỉ thành 32 bit vì nó đã được phân phối đồng đều.

Nếu tôi hiểu các yêu cầu, thì những gì bạn đang yêu cầu không phải là một "chức năng" theo định nghĩa thông thường. Có vẻ như bạn muốn một số $f$ đã đưa ra một chuỗi các đầu vào ${x_i}$ sẽ trả về một giá trị xác định $y_i$ hoặc một biểu tượng lỗi nếu nó đã trở lại $y_i$. Nhưng giả sử $x_k$ là đầu vào đầu tiên trả về lỗi. Điều gì sẽ xảy ra nếu bạn gọi $f$ với trình tự bắt đầu từ $x_k$? Tôi nghĩ bạn sẽ muốn nó không trả về lỗi, vì vậy giá trị của $f(x_k)$ không được xác định rõ.

Cách để giải quyết vấn đề đó về mặt toán học là thay đổi định nghĩa của $f$ để chấp nhận một trình tự. Nhưng trên thực tế, điều đó có thể có nghĩa là hệ thống của bạn ghi lại tất cả các đầu vào đã được gọi. Và bạn sẽ thấy rằng nếu bạn làm điều đó, bạn cũng có thể quay trở lại $0, ..., n-1$ cho các đầu vào riêng biệt đầu tiên và lỗi cho mọi thứ tiếp theo.