이 질문은 언어 독립적입니다. 그래서 저는 지적인 프로그래머 여러분 모두에게 어떻게 든 도와 주실 것입니다.많은 수의 요소가 주어지면 | M | | m |의 일정한 길이로, 어떤 알고리즘이 | M |을 색인 할 수있다. 길이가 <| m |?
주어진 M의 요소 집합은 | M | = 2^128 요소. 모든 요소 "m"은 128 비트의 비트 길이를가집니다.
길이가 128 비트 인 메시지를 보내려고합니다. 이 메시지에서 M의 요소 중 하나와 일부 정보 "n"을 통합하려고합니다. 즉, "m"과 "n"은 길이가 128 바이트 (메시지 길이) 인 <이어야합니다.
상대방은 모든 요소가 포함 된 완전한 세트 "M"을 가지고 있지만 사용해야 할 요소를 알려줘야합니다. 이 지침은 하나의 안주에 적합해야하며 여러 메시지를 나눌 수 없습니다.
그래서 f (m) = index_of_m이되도록 index_of_m이 < 128 비트가되도록 알트 미트 f()로 요소를 인덱싱하려고합니다.
즉, 알고리즘은 요소 길이 (128 비트)보다 적은 비트로 표현되는 인덱스에 128 비트 길이의 2^128 요소를 매핑해야합니다. 포멀 다시
:
세트 : 모든 m1...mn: 128 bits.
메시지 "n" < 128 bit의
M=(m1,m2,...mn) with n = 2^128
길이. 메시지 길이는 가변적이며 1 비트가 될 수 있습니다.
인덱싱/맵핑 함수 : F()
f(m1)=i1 Index 1 of element m1 with the length of i1 < 128 bit., so i1+n=128bit
Wanted: Function f().
아이디어 :
-Hashes는 64 비트 출력을 할 수있는 '인코딩으로 해시 같은 요소를 해싱하는 단순한 방식으로 작동하지 않을 2^128 요소. 128 비트 출력의 해시는 전체 메시지를 사용하며 "n"을위한 공간이 없습니다.
-Indexing 1 to 2^128은 작동하지 않습니다. 예를 들어, 2^128은 전체 메시지를 사용합니다. "세트"로 한 세트를 의미하는 경우
2 : 128 요소에 고유 한 1 : 1 매핑을 원한다면 왜 2^128의 인덱스가 최소가 아닌지 알 수 없습니다. 이 이론 뒤에 내가 놓친 이론이 있습니까? –