ฟังก์ชันแฮชสร้างวงจรด้วยความยาวสูงสุดที่คาดไว้

Marcin Król

10/2/23 02:38

มีฟังก์ชันแฮชที่รู้จักหรือไม่ $H_k: X\ถึง X$ ดังนั้น: $\forall{x\in{X}},\exists{n\in{\mathbb{N}}}, n<k \land H^n(x)=x$

=== แก้ไข ===

โดย ฟังก์ชันแฮช ฉันหมายความว่าวิธีอื่นในการค้นหาพรีอิมเมจของ $x \ใน X$ มากกว่าการวนซ้ำ $H_k$ เป็นไปไม่ได้ในทางคำนวณหรืออย่างน้อยก็ยากกว่ามาก

แรงจูงใจของฉันคือการใช้ฟังก์ชันเช่น Sequential POW

0 + 0

การออกแบบอัลกอริทึม

ต้านทานการชน

fgrieu

10/2/23 06:42

คุณกำลังใช้คำจำกัดความของ "ฟังก์ชันแฮช" อะไรกันแน่ หากเราเพิกเฉยต่อ "แฮช" ตัวอย่างที่ชัดเจนคือ $H_k$ ฟังก์ชันระบุตัวตน คำแนะนำ: พิสูจน์ว่า $H_k$ ใดๆ ดังกล่าวเป็นการเรียงสับเปลี่ยนของชุด $X$ ดังนั้นจึงป้องกันการชนได้อย่างสมบูรณ์แบบ และพรีอิมเมจ (ตัวแรกและตัวเดียว) ของ $x\in X$ ใดๆ สามารถพบได้ด้วยค่าสูงสุด $k- การประเมิน 1$ ของ $H_k$ ซึ่งจำกัดความต้านทานพรีอิมเมจ แต่ถ้า $k$ และ $|C|$ สามารถเติบโตอย่างทวีคูณด้วยพารามิเตอร์ความปลอดภัยสำหรับการต้านทานพรีอิมเมจ บางทีเราอาจสร้างตัวเลือก $H_k$ ได้ หากต้องการคำตอบที่สมบูรณ์ โปรดโน้มน้าวเราว่านี่ไม่ใช่การบ้านหรือคุณทำอยู่

ตอบกลับ

Kulap

คำถามนี้เป็นภาษาอื่นๆ:

EN: Hash function producing cycles with expected max length

TH: ฟังก์ชันแฮชสร้างวงจรด้วยความยาวสูงสุดที่คาดไว้

RO: Funcția hash care produce cicluri cu lungimea maximă așteptată

RU: Хэш-функция, создающая циклы с ожидаемой максимальной длиной

VI: Hàm băm tạo chu kỳ với độ dài tối đa dự kiến

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา