มีฟังก์ชันอินเจกทีฟที่จับคู่ชุดจำนวนเต็มขนาดใหญ่กับชุดที่เล็กกว่าได้หรือไม่ในขณะที่ "รับรู้การชนกัน"

พิจารณาสองชุด:

"ชุดใหญ่" ประกอบด้วยจำนวนเต็มทั้งหมดระหว่าง $0$ และ $2^{160}$ ครั้งเดียว

"ชุดเล็ก" ประกอบด้วยจำนวนเต็มทั้งหมดระหว่าง $0$ และ $2^{32}$ ครั้งเดียว

เนื่องจากจำนวนสมาชิกใน "ชุดใหญ่" มากกว่าสมาชิกใน "ชุดเล็ก" จึงไม่สามารถมีฟังก์ชันฉีดได้ $f(n_b) = n_s$ การจับคู่อินพุตใด ๆ ที่เป็นสมาชิกของ "ชุดใหญ่" $n_b$ ไปยังเอาต์พุตที่เป็นสมาชิกของ "ชุดเล็ก" $n_s$. ถ้าฟังก์ชั่นนั้น $f$ มีอยู่มันจะเป็นคำตอบของคำถาม

ด้วยเหตุผลในทางปฏิบัติ เราสันนิษฐานว่ายังคงสามารถสร้าง/อัลกอริทึมที่มีฟังก์ชันที่ใช้งานได้จริงได้ $f_p$ โดยที่ผลลัพธ์ของการป้อนเข้าทั้งหมด $f_p(n_b)$ เป็นสมาชิกของ "ชุดเล็ก" และแต่ละตัว $n_b$ ชี้ให้เห็นความแตกต่าง $n_s$.

หากขาดความเข้าใจเกี่ยวกับแนวคิดการเข้ารหัส ฉันจะเรียกคุณสมบัตินี้ว่า "collision-aware" เช่น. เพื่อดำเนินการก่อสร้างนี้โดยสมมติว่ามีความจุของขนาด $2^{256}$ (จำนวนเต็มที่ไม่มีเครื่องหมาย 256 บิต) มีฟังก์ชันหรือไม่ $f_p$ หรืออัลกอริทึมสำหรับใดๆ $n_b$ ส่งคืน "การชนกัน" ("การชนกันที่ทราบ") หรือสมาชิกที่แตกต่างกันของ $n_s$?

สิ่งที่เกี่ยวกับ:- $$ n_s = \mathcal{H}(n_b) \& (2^{32} - 1) $$ ที่ไหน $n_b \ใน N_b$ฯลฯ? $\คณิตศาสตร์แคล{H}$ สามารถเป็นฟังก์ชันแฮชที่คุณเลือกได้ เนื่องจากนี่เป็นไซต์ crypto ฉันขอแนะนำ SHA-256 $\&$ หมายถึง AND แต่สามารถแทนที่ด้วยการเลื่อนไปทางขวาหรือซ้ายตามจำนวนบิตที่เหมาะสม (128 ในกรณีของ SHA-256) อาจจะช้าเกินไป (?)

ฟังก์ชันแฮชการเข้ารหัสคือ เสแสร้งซึ่งหมายความว่าผลลัพธ์ของพวกเขาจะชนกันในบางครั้ง อัตราการชนนั้นจะเพิ่มขึ้นอย่างมากหากคุณตัดทอน $\คณิตศาสตร์แคล{H}$ ถึง 32 บิต ยิ่งไปกว่านั้นผลของการ หลักการหลุมนกพิราบ. คุณจะได้ตั้งค่า $N_b$ เติมด้วยตัวเลขที่กระจายอย่างสม่ำเสมอให้ $n_b \ถึง n_s$ จากโดเมนถึงโคโดเมน

ฉันไม่รู้เกี่ยวกับ Ethereum แต่ 160 ดูเหมือนผลลัพธ์ของ SHA-1 อย่างน่าสงสัย หากเป็นเช่นนั้น ให้ตัดบัญชี/ที่อยู่เป็น 32 บิตเนื่องจากมีการกระจายอย่างสม่ำเสมอแล้ว

หากเข้าใจข้อกำหนดแล้ว สิ่งที่คุณถามไม่ใช่ "ฟังก์ชัน" ตามนิยามปกติ ดูเหมือนว่าคุณต้องการบางอย่าง $f$ ที่ให้ลำดับของอินพุต ${x_i}$ จะส่งกลับค่าที่กำหนด $y_i$ หรือสัญลักษณ์แสดงข้อผิดพลาดหากมีการส่งคืนแล้ว $y_i$. แต่สมมุติว่า $x_k$ เป็นอินพุตแรกที่ส่งคืนข้อผิดพลาด จะเกิดอะไรขึ้นถ้าคุณโทร $f$ โดยมีลำดับเริ่มจาก $x_k$? ฉันคิดว่าคุณคงต้องการให้ไม่ส่งคืนข้อผิดพลาด ดังนั้นค่าของ $ฉ(x_k)$ ไม่ได้กำหนดไว้อย่างดี

วิธีแก้ไขนั้นในทางคณิตศาสตร์คือเปลี่ยนนิยามของ $f$ เพื่อยอมรับลำดับ แต่ในทางปฏิบัติ สิ่งที่อาจหมายถึงคือการให้ระบบของคุณบันทึกอินพุตทั้งหมดที่ถูกเรียกใช้ และคุณจะพบว่าถ้าคุณทำเช่นนั้น คุณก็อาจจะกลับมาได้เช่นกัน $0, ..., n-1$ สำหรับอินพุตแรกที่แตกต่างกัน และข้อผิดพลาดสำหรับทุกอย่างที่ตามมา