Even-Mansour เป็นแบบจำลองเชิงทฤษฎีเพื่อพิสูจน์ผลลัพธ์ด้านความปลอดภัย เราจะต้องสุ่มตัวอย่างการเรียงสับเปลี่ยนของ $n$ บิตพูดสำหรับ $n=128,$ เนื่องจากพื้นที่ผลลัพธ์ของ $N=2^n$ วัตถุจะมีขนาดใหญ่เกินไปที่จะเก็บหรือจัดการ สิ่งนี้คล้ายกับความจริงที่ว่าไม่มีใครใช้การแจกแจงแบบสุ่มอย่างหมดจดและ i.i.d. ลำดับของบิตเป็นคีย์สตรีมในโหมด OTP ในการเข้ารหัสสมัยใหม่ มันช้าเกินไป
อย่างไรก็ตาม อัลกอริทึมต่อไปนี้ให้การเปลี่ยนลำดับแบบสุ่ม $\{1,2,\ldots, N\}.$ ไม่มีการเรียกร้องประสิทธิภาพที่เหมาะสมที่สุดที่นี่
รหัสสำหรับการเรียงสับเปลี่ยนแบบสุ่มของรายการขนาดเล็ก
ป้อนข้อมูล: รายการ $A=[1,2,\ldots, N]$ ของ $N=2^n$ รายการ
งาน: เปลี่ยนค่าเป็น $A$ สุ่ม.
อนุญาต $S:=\{u: u \in A\}.$ อนุญาต $B:=A$
แต่ละ $i=1,\ldots,N$ ทำ
$\สี่เหลี่ยม$ เลือกจำนวนเต็มแบบสุ่ม $j \ใน S$
$\สี่เหลี่ยม$ เปลี่ยนอาร์เรย์ $B$ ทาง $B[j]:=A[i]$
$\สี่เหลี่ยม$ ลบ $เจ$ จากชุด $S$
จบสำหรับ
อัลกอริทึมนี้เลือก $N,$ แล้ว $N-1$, แล้ว $N-2$ ฯลฯ วัตถุที่เหมือนกันและสามารถสร้างการเรียงสับเปลี่ยนแต่ละครั้งด้วยความน่าจะเป็นที่เท่ากัน เนื่องจากมันสร้าง $N\!$ ทางเลือก
เอาท์พุต: รายการ $A$ ตอนนี้เป็นแบบสุ่ม
มีวิธีที่มีประสิทธิภาพมากขึ้นในการสุ่มตัวอย่างการเรียงสับเปลี่ยนแบบสุ่ม ดูตัวอย่าง Jens Gustedt, "Efficient sampling ofrandom permutations", วารสารอัลกอริทึมที่ไม่ต่อเนื่องฉบับ 6 ฉบับที่ 1 ปี 2549 ลองดู Fisher-Yates shuffle และ Knuth Shuffle ด้วย Google คือเพื่อนของคุณ
อัลกอริทึมด้านล่างยังไปไม่ถึง ขอบคุณ @kelalaka สำหรับการแก้ไข
ป้อนข้อมูล: รายการ $A=\{1,2,\ldots, N\}$ ของ $N=2^n$ รายการ
งาน: เปลี่ยนค่าเป็น $A$ สุ่ม.
แต่ละ $i=0,\ldots,N-1$ ทำ
$\สี่เหลี่ยม$ เลือกจำนวนเต็มแบบสุ่ม $เจ$ กับ $i<j<N.$
$\สี่เหลี่ยม$ สลับรายการ $เอ[i]$ และ $ก[ญ].$
จบสำหรับ
เอาท์พุต: รายการ $A$ ตอนนี้เป็นแบบสุ่ม