สมมติว่า $x$ เป็นลำดับของ $l$ บิตและ $0 \le n < l$, อนุญาต $R(x, n)$ แสดงถึงผลลัพธ์ของการหมุนตามบิตซ้ายของ $x$ โดย $n$ บิตตัวอย่างเช่น ถ้า $x = 0100110001110000$, แล้ว $$\begin{อาร์เรย์}{l}
R(x,0) = {\rm{0100110001110000}},\
R(x,1) = {\rm{1001100011100000}},\
R(x,2) = {\rm{0011000111000001}},\
\ldots \
R(x,15) = {\rm{0010011000111000}}
\end{อาร์เรย์}$$
อนุญาต $A \oบวก B$ แสดงผลลัพธ์ของการดำเนินการ XOR สำหรับสองลำดับของ $l$ บิต ตัวอย่างเช่น, $$0100110001110000 \oบวก 1010010001000010 = 1110100000110010.$$
อนุญาต $H(x)$ หมายถึงจำนวนบิตที่ไม่ใช่ศูนย์ใน $x$ (กล่าวคือ น้ำหนักทุบ ของ $x$).
สมมติว่า $x$ และ $y$ เป็นสตริงสองบิตที่มีความยาวเท่ากัน $l$, อนุญาต $ฉ(x, y)$ หมายถึงองค์ประกอบขั้นต่ำ (จำนวนที่น้อยที่สุด) ในทูเพิล $$\begin{อาร์เรย์}{l}
(ส(x \oบวก y),\
H(x \oบวก R(y,1)),\
H(x \oบวก R(y,2)),\
\ldots \
H(x \oบวก R(y,l - 1))).
\end{อาร์เรย์}$$
สมมติว่าเรามี TRNG ซึ่งสร้างลำดับของบิตแบบสุ่ม สร้างลำดับของ $L = k \คูณ l$ บิต แยกลำดับนี้เป็น $k$ คำ (ดังนั้นความยาวของคำแต่ละคำคือ $l$): $w_0, w_1, \ldots, w_{k-1}$. จากนั้นคำนวณทูเพิลต่อไปนี้ $T$ จำนวน:
$$\begin{อาร์เรย์}{l}
(ฉ({w_0},{w_1}),\
ฉ({w_0},{w_2}),\
\ldots \
ฉ({w_0},{w_{k - 1}}),\
ฉ({w_1},{w_2}),\
ฉ({w_1},{w_3}),\
\ldots \
ฉ({w_1},{w_{k - 1}}),\
ฉ({w_2},{w_3}),\
\ldots \
ฉ({w_{k - 2}},{w_{k - 1}}))
\end{อาร์เรย์}$$
กล่าวอีกนัยหนึ่งสำหรับ ใดๆ คำคู่ $(w_i, w_j)$ ดังนั้น $i \neq j$คำนวณที่สอดคล้องกัน $f({w_i},{w_j})$.
คำถามที่ 1: ให้ $k$ และ $l$, วิธีคำนวณ ที่คาดหวัง มูลค่าของ น้อยที่สุด ตัวเลข $M_T$ ใน $T$?
คำถามที่ 2: ให้ $k$ และ $l$, วิธีคำนวณ ที่คาดหวัง มูลค่าของ เฉลี่ย ตัวเลข $A_T$ ใน $T$? นี่เบอร์ $A_T$ คำนวณได้ดังนี้: รวมองค์ประกอบทั้งหมดของ $T$แล้วหารผลรวมด้วยจำนวนองค์ประกอบทั้งหมดใน $T$.
เดอะ ที่คาดหวัง จำนวนในที่นี้หมายถึงจำนวนที่มีความน่าจะเป็นสูงสุดตัวอย่างเช่น จำนวนศูนย์บิตที่คาดหวังในลำดับของ $l$ บิตสุ่มคือ $l/2$.